|
Nel 1919 George Polya
congetturò che per ogni numero naturale N, se 2 ≤ N, i numeri naturali tra 2 ed N
con un numero pari di fattori primi [maggiori di 1] fossero meno di quelli con un
numero dispari di fattori primi [maggiori di 1]. Indichiamo con P e D le loro quantità; quindi P+D = N−1 (ho tolto 1 in quanto parto da 2).
La congettura è, dunque, che D > P, ovvero che D/(P+D) > 1/2, ovvero che D/(N−1) > 1/2.
La cosa trovava conferma nelle molte prove che aveva realizzato.
Questo aprì il problema di dimostrare la cosa o di trovarne un controesempio.
Dopo l'avvento dei computer si provò a studiare il problema sperimentalmente utilizzando opportuni programmi.
Fu solo nel 1980 che Minoru Tanaka, con un programma di questo genere,
trovò che la cosa vale solo per i numeri minori di 906 150 257. Prova a realizzare un programma per effettuare tale studio. Ecco, a destra, alcune possibili uscite di un programma di tal genere, che al crescere di N calcola il rapporto R = D/(N−1) e stampa i valori di N e R ogni volta che R diminuisce. Trai spunto dal seguente programma per R più semplice, che determina i fattori primi di 12. |
2 1 4 0.6666667 6 0.6 10 0.5555556 16 0.5333333 26 0.52 40 0.5128205 95 0.5106383 96 0.5052632 566 0.5044248 568 0.5044092 570 0.5043937 572 0.5043783 573 0.5034965 581 0.5034483 583 0.5034364 584 0.5025729 585 0.5017123 586 0.5008547 |
## Algoritmo che scompone n > 1 in numeri primi (se n/k ha un risultato intero
## allora k è un divisore: n=k*h; lo stampo e mi riduco a trovare i primi di h; ...)
n <- 12; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 2 2 3
# IDEA:
# A partire da D=0, per ogni n, da 2 a T, aggiungo 1 se i fattori primi di n sono in
# quantità dispari. Alla fine determino il rapporto tra questo totale D e (T-1)
n <- 2; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 2 - devo calcolare 1/(2-1) = 1
n <- 3; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 3 - devo calcolare (1+1)/(3-1) = 1 (aggiungo 1: 3 ha quantità dispari di fattori primi)
n <- 4; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 2 2 - devo calcolare (1+1)/(4-1) = 2/3 (non aggiungo 1: 4 non ha quantità dispari di …)
n <- 5; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 5 - devo calcolare (1+1+1)/(5-1) = 3/4 (aggiungo …)
n <- 6; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 2 3 - devo calcolare (1+1+1)/(6-1) = 3/5 = 0.6 (non aggiungo …)
n <- 7; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 7 - devo calcolare (1+1+1+1)/(7-1) = 2/3 (aggiungo …)
n <- 8; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 2 2 2 - devo calcolare (1+1+1+1+1)/(8-1) = 5/7 (aggiungo …)
n <- 9; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 3 3 - devo calcolare (1+1+1+1+1)/(9-1) = 5/8 = 0.625 (non aggiungo …)
n <- 10; k <- 2; while(k <= n) if(n/k==floor(n/k)) {n <- n/k; print(k)} else k <- k+1
# 2 5 - devo calcolare (1+1+1+1+1)/(10-1) = 5/9 = 0.55555 (non aggiungo …)
#
# Ecco una possibile realizzazione del programma richiesto:
a <<- 2
for(t in 2:600) { d <- 0; for(n in 2:t) { m <- 0; k <- 2; while(k <= n)
if(n/k==floor(n/k)) {m <- m+1; n <- n/k} else k <- k+1; if(floor(m/2) < m/2) d <- d+1};
if(d/(t-1) < a) {write(c(t,d/(t-1)),file=""); a <- d/(t-1)} }
# In a memorizzo il nuovo valore minimo di R e lo stampo
Questo algortimo (che abbiamo fermato a 600) è molto elementare, ma ci dà un'idea di come si può studiare il problema. Con un algortimo più efficiente, in diverse ore, si potrebbe ottenere che per 906 150 257 R < 1/2.