OliForum Matematico

trovare il numero di numeri primi <= 100

contali! sono 25.

Soluzione ineccepibile...

oltre il contali?

Sono curioso di sentire la tua...

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...

$ \displaystyle \pi(n)=\sum_{i=2}^{n} \Big \lfloor \frac{(i-1)!+1}{i}-\Big\lfloor \frac{(i-1)!}{i} \Big \rfloor \Big \rfloor $

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)

jordan ha scritto:Sono curioso di sentire la tua...

se ho postato forse è perchè avevo bisogno.cmq il santos propone una soluzione a pagina 40,ma non avevo capito un granchè

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?

Definisci espressione analitica.

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?

$ $\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.

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).

Che c'entra?
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.

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.

Secondo te come si calcola $ $n^4 - 2n + e^{\pi} $?