<= 100 primi
<= 100 primi
trovare il numero di numeri primi <= 100
ci sarebbe la funzione $ \pi(n) $ che dà il numero dei numeri primi minori di n. E' una funzione molto importante nella teoria dei numeri, interessante anche dal punto di vista storico soprattutto per un motivo... ancora non si ha un'espressione per $ \pi(n) $! Quindi mi sa proprio che il contarli è l'unico modo...
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Verificandoli a mano si farebbero $ O(n) $ operazioni.
Notiamo che se $ x \in \mathbb{Z} \cap (1,n] $ è tale che $ x \not \in \mathbb{P} $ allora esiste $ q \in \mathbb{P} \cap [2,\sqrt{n}] $ tale che $ q \mid x $. Per cui ci troviamo $ \mathbb{P} \cap [2,\sqrt{n}] $ con $ O\left(\lfloor\sqrt{n}\rfloor\right) $ operazioni e concludiamo il calcolo con il principio di inclusione esclusione, facendo $ O\left(2^{\pi(\lfloor \sqrt{n} \rfloor)}\right) $ operazioni. Ma, anche se in questo caso funziona meglio nel calcolo di $ \pi(n) $, è asintoticamente peggiore di quello manuale (vedi teorema dei numeri primi)
Notiamo che se $ x \in \mathbb{Z} \cap (1,n] $ è tale che $ x \not \in \mathbb{P} $ allora esiste $ q \in \mathbb{P} \cap [2,\sqrt{n}] $ tale che $ q \mid x $. Per cui ci troviamo $ \mathbb{P} \cap [2,\sqrt{n}] $ con $ O\left(\lfloor\sqrt{n}\rfloor\right) $ operazioni e concludiamo il calcolo con il principio di inclusione esclusione, facendo $ O\left(2^{\pi(\lfloor \sqrt{n} \rfloor)}\right) $ operazioni. Ma, anche se in questo caso funziona meglio nel calcolo di $ \pi(n) $, è asintoticamente peggiore di quello manuale (vedi teorema dei numeri primi)
The only goal of science is the honor of the human spirit.
Ma io pensavo che non ci fosse un'espressione analitica di $ \pi(n) $. Ci sono funzioni che la approssimano e che si avvicinano asintoticamente ad essa, ma non possono essere comunque considerate esatte. Gauss per esempio, se nn mi ricordo male, aveva proposto $ f(n)=\displaystyle\frac{n}{\log{n}} $, e poi l'aveva migliorata con un logaritmo integrale in qualche modo (nn prendete come oro colato, rispolvero vecchie memorie! ). Poi ci sono state anche altre approssimazioni sempre migliori, ma non esiste un'espressione analitica ESATTA per $ \pi(n) $. O no?
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
del tipo, non esiste una funzione del tipo $ \pi(n) = f(n) $ in cui $ f $ è una funzione algebrica o trascendente (tipo un polinomio, o una funzione trigonometrica, logaritmica, o mista, o qualunque altra). Non so se mi sono spiegato, ma in generale non penso che ci sia una qualunque espressione in cui "metti dentro" $ n $ e ti dà il valore ESATTO di $ \pi(n) $. Per lo meno, non allo stato attuale delle conoscenze di teoria dei numeri.
O mi sbaglio?
O mi sbaglio?
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
$ $\pi(n) $ è una funzione, e il suo valore esatto è calcolabile per ogni n. I problemi sono altri, per quanto ne so io (cioè poco) la velocità di calcolo e il fatto che si sappia poco sui valori precisi di $ $\pi(n) $, cioè è relativamente facile porre problemi di complessità enormi. Esistono sicuramente scritture equivalenti della stessa funzione, il problema è se danno un aiuto sostanziale o meno nella sua comprensione.
è chiaro che $ \pi(n) $ è una funzione. Quello che intendo è un'altra cosa. Prendi per esempio i polinomi di grado superiore al quarto. Essi HANNO radici che possono essere sempre trovate o approssimate (per esempio con il metodo di Newton o con molti altri), ma NON con metodi algebrici (radici et similia).
Similmente, nn metto assolutamente in dubbio il fatto che $ \pi(n) $ sia una funzione, ma non esiste un'espressione analitica di essa che non faccia uso di metodi ricorsivi (ossia che coinvolgano il "contare").
Un'espressione del tipo $ \pi(n) = n^4 - 2n + e^{\pi} $ giusto per fare un esempio a caso, mi smentirebbe, ma un'espressione del genere non esiste.
Similmente, nn metto assolutamente in dubbio il fatto che $ \pi(n) $ sia una funzione, ma non esiste un'espressione analitica di essa che non faccia uso di metodi ricorsivi (ossia che coinvolgano il "contare").
Un'espressione del tipo $ \pi(n) = n^4 - 2n + e^{\pi} $ giusto per fare un esempio a caso, mi smentirebbe, ma un'espressione del genere non esiste.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"
Che c'entra?Gauss91 ha scritto:Quello che intendo è un'altra cosa. Prendi per esempio i polinomi di grado superiore al quarto. Essi HANNO radici che possono essere sempre trovate o approssimate (per esempio con il metodo di Newton o con molti altri), ma NON con metodi algebrici (radici et similia).
Comunque tra il dire $ $\pm\sqrt{2} $ e "chiamo a,b,c,d,e le cinque radici complesse di $ $p(x) $ polinomio di 5 grado" non c'è molta differenza. La radice è definita come soluzione positiva del polinomio $ $x^2+2 $, che sappiamo esistere per gli assiomi. Poi per calcolare l'espansione decimale di $ $\pm\sqrt{2} $ devi usare sempre metodi di approssimazione, esattamente come per le radici del polinomio.
Secondo te come si calcola $ $n^4 - 2n + e^{\pi} $?Gauss91 ha scritto:Similmente, nn metto assolutamente in dubbio il fatto che $ \pi(n) $ sia una funzione, ma non esiste un'espressione analitica di essa che non faccia uso di metodi ricorsivi (ossia che coinvolgano il "contare").
Un'espressione del tipo $ \pi(n) = n^4 - 2n + e^{\pi} $ giusto per fare un esempio a caso, mi smentirebbe, ma un'espressione del genere non esiste.
Ultima modifica di julio14 il 27 nov 2009, 19:32, modificato 2 volte in totale.