<= 100 primi

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

<= 100 primi

Messaggio da danielf » 26 nov 2009, 20:10

trovare il numero di numeri primi <= 100

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 26 nov 2009, 20:12

contali! :P sono 25.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"

Dani92
Messaggi: 108
Iscritto il: 08 ott 2009, 18:32
Località: Trento

Messaggio da Dani92 » 26 nov 2009, 20:21

Soluzione ineccepibile... :lol:

danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

Messaggio da danielf » 26 nov 2009, 20:33

oltre il contali?

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 26 nov 2009, 21:03

Sono curioso di sentire la tua... :lol:
The only goal of science is the honor of the human spirit.

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 26 nov 2009, 22:56

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à!"

fede90
Messaggi: 287
Iscritto il: 04 apr 2007, 21:36
Località: Udine

Messaggio da fede90 » 27 nov 2009, 00:12

$ \displaystyle \pi(n)=\sum_{i=2}^{n} \Big \lfloor \frac{(i-1)!+1}{i}-\Big\lfloor \frac{(i-1)!}{i} \Big \rfloor \Big \rfloor $ :lol:
Bene, prendiamo un pentagono di [tex]$n$[/tex] lati...

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Messaggio da jordan » 27 nov 2009, 05:27

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) :roll:
The only goal of science is the honor of the human spirit.

danielf
Messaggi: 203
Iscritto il: 17 set 2009, 19:11

Messaggio da danielf » 27 nov 2009, 14:58

jordan ha scritto:Sono curioso di sentire la tua... :lol:
se ho postato forse è perchè avevo bisogno.cmq il santos propone una soluzione a pagina 40,ma non avevo capito un granchè

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 27 nov 2009, 16:36

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! :P ). 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à!"

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 27 nov 2009, 17:02

Definisci espressione analitica.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 27 nov 2009, 17:24

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?
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 27 nov 2009, 17:40

$ $\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.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Gauss91
Messaggi: 240
Iscritto il: 19 set 2009, 16:52
Località: Pisa / Milano

Messaggio da Gauss91 » 27 nov 2009, 19:08

è 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.
"Cos'è l'aritmetica?" "E' quella scienza in cui si impara quello che si sa già!"

Avatar utente
julio14
Messaggi: 1206
Iscritto il: 11 dic 2006, 18:52
Località: Pisa

Messaggio da julio14 » 27 nov 2009, 19:24

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} $?
Ultima modifica di julio14 il 27 nov 2009, 19:32, modificato 2 volte in totale.
"L'unica soluzione è (0;0;0)" "E chi te lo dice?" "Nessuno, ma chi se ne fotte"
[quote="Tibor Gallai"]Alla fine, anche le donne sono macchine di Turing, solo un po' meno deterministiche di noi.[/quote]
Non sono un uomo Joule!!!

Rispondi