VARIANTE TEOREMA DI WILSON

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

VARIANTE TEOREMA DI WILSON

Messaggio da modulocomplicato »

Cortesemente qualcuno sa dirmi come si chiama questa variante del teorema di Wilson:

(che in pratica è la definizione di numero primo...)

Sia M un intero positivo qualsiasi, per M >= 5

(1) Rm= (M-1)!/M

se M è primo (Pi) Rm non è intero
se M non è primo Rm è intero

Chiedo anche lumi sul motivo per cui non sia più "pubblicizzato" il fatto che:

Con la (1) (o Wilson) è quindi possibile identificare "facilmente" i numeri primi per cui

a) Dato un intero P= primo = Pi(x) E' possibile stabilire la sua posizione (x) con un accrocchio matematico che "spazzola" tutti i numeri da 5 a P , quindi per ognuno calcola Rm, azzera gli Rm interi e "tira" ad 1 i non interi, sommandoli ( ci somma anche 2 perchè "manca" 2 e 3) ... per fornire il risultato che è (x).

b) Analogamente, solo con qualche "accrocchio" in più è possibile: dato Pi(x) con x noto, stabilire il valore di Pi(x+1)

Computazionalmente è pesante, quindi "inutile", ma diversamente da Eratostene che è un metodo computazionale che richiede una "memoria", questa è una funzione matematica "esatta"....

Serve solo per sfatare il mito (che ancora resiste ed è diffuso da "vecchi" furbacchioni come Sautoy...) che "i primi sono entità ectoplasmatiche disposte randomicamente..."


Ciao
Stefano

p.s se qualcuno è interessato al "forumulazzo" posso postarlo....

Funny man: il libro di algebra "superiore" di mia moglie, su campi etc.. dopo oniriche lodi dell'astrazione (lascia spesso al lettore la dimostrazione di parti sostanziali... come dire se sei un asino lascia stare...) termina con il più profondo "teorema" dell'algebra "moderna"... che ha come punto centrale della dimostrazione un grafichetto di una funzione in x e y (stampato) in cui si vede che un polinomio "pinco pallo" ha 3 radici reali... quindi le altre due devono essere...
Sarebbe stato più elegante dire dall'inizio che l'astrazione è un metodo potentissimo e "rivoluzionario", ma che nessuno ha da schifarsi se c'è qualche collaudato metodo "manuale" che talgia, di molto ed in modo anche più chiaro, la dimostrazione "dell'antimateria klingon"...
Quindi che una volta capito l'incomprensibile, sarebbe utile chiedersi se non esiste altra dimostrazione "più diretta"....
Scusate lo sfogo da neurodeliri...

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: VARIANTE TEOREMA DI WILSON

Messaggio da modulocomplicato »

... se sto sulla luna (o sul pianeta dei folli....) ditemelo che non "infastidisco" oltre...

Ciao
Stefano

panurgo
Livello 9
Livello 9
Messaggi: 1521
Iscritto il: sab nov 19, 2005 3:45 pm
Località: Padova

Re: VARIANTE TEOREMA DI WILSON

Messaggio da panurgo »

Carissimo, che puoi portarci un po' di luna, sei tre volte benvenuto! :D

Purtroppo il tempo scarseggia ma io sono interessato al formulazzo...
il panurgo

Principio di Relatività: $\mathbb{m} \not \to \mathbb{M} \, \Longleftrightarrow \, \mathbb{M} \not \to \mathbb{m}$
"Se la montagna non va a Maometto, Maometto NON va alla montagna"

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: VARIANTE TEOREMA DI WILSON

Messaggio da modulocomplicato »

Pronti !

L' "oscura" formula che ritorna la posizione del primo:

Immagine

In cui le graffe significano "parte intera di"

Che può essere scritta in modo completo e più comprensibile come (non è lunico modo !):

Immagine

Dalla quale deriva (in modo analogo) il formulazzo che non riesco ancora a postare ora (ma che prometto posterò) e che anticipo funziona così:

Se sai che p.es. 11 è primo e ti chiedi chi sarà il primo successivo, allora il formulazzo, che è un'altra sommatoria solo un po' più incasinata, prende, tutta da sola, 11, si calcola che posizione ha 11: quindi ottiene Pos(11)= 5 , poi sa che il Pos(x) ha posizione= Pos(11)+1 = 6 quindi fa partire da 5 il macinino (una sommatoria) che controlla numero per numero (e alla fine somma il risultato ottenuto):

- se non è un primo tira a zero il valore
- se è un primo calcola la sua posizione: se la posizione è minore di 6 il rapporto ( Posizione calcolata / posizione cercata) è minore di 1 quindi questo rapporto ha parte intera nulla, quindi moltiplicando il numero per la parte intera di un numero minore di 1 si ha zero, quindi somma zero, e va avanti...
- quando è 6 la funzione Int (6/6) =1 quindi 13 * int(6/6) = 13
- se è superiore "tira" nuovamente a zero (questo è stato un po' meno facile perchè i numeri finiscono tutti nel formulazzo e l'operazione all'interno della sommatoria è identica per tutti....)
- arrivati a 11^2 si ferma da solo (infatti se P5=11 allora sarà P6 < P5^2...)

Somma di 0+0+0+..+0+0+0+0+0+ 13 +0+0+0.... = 13 che il numero primo (n pos. 5+1 = 6) cercato.

Ho tribulato un po' a mettere insieme tutte queste condizioni nel formulazzo, ma alla fine si tratta solo di smanettare un po'.

Il "trucco" sta anche nel fatto che il limite superiore a cui arrestare il calcolo può essere grande a piacere... ma con un po' di riminescenze, può anche essere reso non troppo più grande del "probabile" valore del prossimo primo... p.es. 5^2 nel caso... ma i sopraffini sapranno bene come raffinare ancora meglio il limite superiore per ridurre il tempo di calcolo.

Come ho detto è computazionalmente molto lento perchè riconteggia uno ad uno a partire da 5, ma è necessario per far capire che i "primi" non sono ectoplasmi.

Insomma se li distingui, li conti, se puoi contare li conosci tutti...

Grazie per la pazienza...
Ciao
Stefano

...dopo aver letto Sautoy non riuscivo ad arrendermi al fatto che una macchina a controllo numerico non fosse in grado, ad esempio, di fare un foro ad una distanza dal precendete pari al valore del numero primo successivo...

Tomahawk
Nuovo utente
Nuovo utente
Messaggi: 23
Iscritto il: mer set 12, 2012 8:10 pm

Re: VARIANTE TEOREMA DI WILSON

Messaggio da Tomahawk »

vi incollo una cosa che vi potrebbe interessare:

http://wwwusers.di.uniroma1.it/~lpara/L ... pense2.pdf

andate a pagina 20 e 21 quando parla della formula di Willans.
Soprattutto sostiene che un test di primalità basato sul teorema di Wilson è meno veloce di quella basata sul crivello di Eratostene a causa del fattoriale.
Gia che ci siete potete leggerle tutte e 20 le pagine ... sono le dispense di un corso di logica per la facoltà di informatica :)
Ultima modifica di Tomahawk il dom nov 04, 2012 2:53 pm, modificato 1 volta in totale.
([{|Daniele|}])

"Amo le nuvole... le nuvole che passano... là, lontano... le nuvole meravigliose." CB
-
"Mi dispiace maestra, le tabelline le ho imparate in base 2"

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: VARIANTE TEOREMA DI WILSON

Messaggio da modulocomplicato »

Interessante, grazie, non la conoscevo.

... ma è molto più complicata da comprendere di quella che avevo intenzione di postare.... che si basa solo su (Int) e (!), quindi più facile da comprendere.

In oltre è pure più veloce perchè non richiede l'estrazione della radice n-esima... In oltre il fattoriale lo uso solo per evitare forme "fastidiose" del tipo 0/0. Quindi lo uso al denominatore quando rischio di avere uno zero e così lo trasformo in 1: 0! =1 , 1!=1 2!=2 ETC...

Avrei qualcosa da eccepire sul paragone (affatto educativo, ma sbattuto in ogni dove, anche su wiki...): è chiaro che è più veloce, ma Eratostene è un "metodo" che equivale ad un programma e richiede un computer con memoria (e tanta...), queste sono "funzioni", intanto e lavorano con una memoria minima ("ricordano" e "usano" il minimo indispensabile...)

In oltre l'applicazione dell'algebra modulare dovrebbe aver almeno insegnato ad essere più prudenti quando si parla di velocità di calcolo...

Intanto mettiamo giù il conto esatto e rendiamolo comprensibile anche ai bambini... poi non si sa mai che qualcuno (di loro) trovi una scorciatoia...

Ciao
Grazie
Stefano

p.s. come riesco posto il formulazzo (che come abbiamo visto è solo uno dei tanti realizzabili).

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: VARIANTE TEOREMA DI WILSON

Messaggio da Pasquale »

Pan ha scritto : << Carissimo, che puoi portarci un po' di luna, "sei tre volte" benvenuto! >>, che io interpreto come "18 volte" benvenuto, sulla qual cosa convengo.

Tanto premesso, non essendo sicuro come al solito di aver capito tutto alla perfezione, vorrei chiedere:

nella seconda formula, non ci sono troppe parentesi? Se la scrivo come di seguito, non è lo stesso?


$\text \sum_{n=5}^x INT\[\frac{\(n-1\)!}{n} - INT \frac{\(n-1\)!}{n} + 0,2 \] + 2$

Inoltre, salvo errori, avrei tradotto le due formule nei seguenti programmi Decimal Basic, in cui a titolo di esempio ho posto x=11, ma i risultati, se non vi sono errori, mi appaiono strani:


prima formula

LET x=11

LET S=0
FOR n=5 TO x
LET S=S+n*INT(fact(n-2)/n)+2
NEXT N
PRINT S


seconda formula

LET x=11

LET S=0
FOR n=5 TO x
LET S=S+INT(fact(n-1)/n - INT(fact(n-1)/n)+0.2)+2
NEXT N
PRINT S

END

Alla sommatoria S, la prima formula attribuisce un risultato di 409121, mentre dalla seconda formula scaturisce un 17.

Dunque, chiedo lumi.

END
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: VARIANTE TEOREMA DI WILSON

Messaggio da modulocomplicato »

No, non mi pare, anzi a voler fare i puntini sulle i, sarebbe anche meglio "isolare" la sommatoria dal +2, onde evitare che qualcuno pensi che il 2 è parte del termine interno alla sommatoria...

1) La forumulazza "ufficiale" che ho riportato come compare (o compariva) su WIKI è irritante nella forma e l'è una bella fregatura perchè se non leggi sotto (come me e come tutti i comuni mortali non fanno) prendi le sgraffe per graffe, e fai una gaffe...

Cito:
" dove { x } indica la parte frazionaria di x. Questa formula sfrutta il fatto che, per n > 4, \left\{ \frac{\left(n-2\right)!}{n}\right\} è uguale a 0 se n è composto, a \frac{1}{n} se n è primo. Essa risulta comunque inutile nelle applicazioni poiché richiede una mole di calcoli di gran lunga più elevata del crivello di Eratostene, e va quindi considerata solo come una curiosità matematica."

... Bah... ogni tanto mi sento molto più ignorante del solito....

2) La mia, se ho scritto giusto, e se hai scritto giusto il 2° programmino (che verifico come ho tempo), dovrebbe dare zero per ogni non primo mentre da 1 per ogni primo che incontra: Es quando trova 5 fa: [4!/5- int(4!/5)]= 0.8, poi 0.8... poi 0.9... etc....(ma non supera mai 0.9999....), quindi ci sommo 0.2, che fa 1 o più e l'operatore "intero" fuori dalle graffe lo tosa a "1", quindi la sommatoria somma e procede...

Quindi (salvo omissioni del programma, ad esempio excel richiede almeno 0.3 per via delle approssimazioni dopo la vigrola...) dovrebbe dare 1 ad ogni primo che trova...

etc. etc per tutti e soli i primi, mentre per gli altri (n-1)!/n è un intero, quindi (intero-intero di se stesso) =0 e dato che 0.2 o 0.3 <1 l'operatore "Int" fuori dalle graffe ritorna zero, quindi somma zero.


Quindi se metti 11 trova 5,7,11 che danno 1, quindi la somma è (1+1+1) +2= 5...

O no ?


Come ho tempo correggo lo 0,2 ad un più illustre 1/3...

Per verifica puoi incollare questa in excel:

nella colonna A metti gli interi da 5 in poi nella prima cella della colonna B incolli:

=INT((FATTORIALE(A1-1)/A1-INT(FATTORIALE(A1-1)/A1))+0.3)

poi trascini in basso e vededi che (a partire da 5 in poi) per ogni primo che trova restituisce 1....


Ciao e grazie per la pazienza !
Stefano

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: VARIANTE TEOREMA DI WILSON

Messaggio da Pasquale »

Va bene, appena posso ci guardo, grazie.
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: VARIANTE TEOREMA DI WILSON

Messaggio da modulocomplicato »

...hai mica avuto tempo di guardarci ???

Lascio giochetto:

Fare a mano radice quinta di 16809, utilizzando il modulo complicato:

Tabulare: M5= 5x^4-10x^3+10x^2-5x+1

\text x M5 R^5 = 16809
\text 1 1 16809-1 = 16808
\text 2 .... 16808- ....= etc...

etc... quando si ferma con x=r intero ?

Chiude esatto o fa resto ?

Se fa resto volendo c'è modo di continuare e affinare la precisione... quanto si vuole, fino all'infinito...

...sarò gnugnu, ma il \text resta così....
Ultima modifica di modulocomplicato il mar nov 27, 2012 11:54 am, modificato 1 volta in totale.

Pasquale
Livello 12
Livello 12
Messaggi: 2853
Iscritto il: mer mag 25, 2005 2:14 am

Re: VARIANTE TEOREMA DI WILSON

Messaggio da Pasquale »

Scusa, non sempre posso dedicarmi, o non sempre tutto mi è chiaro, e le cose finiscono nel dimenticatoio.

Per la questione degli spazi mancanti, puoi caricare un disegnino in formato jpg, oppure utilizzare TEX con il comando "\text"

Esempio:

Immagine


$\text AA BBBBBBB CCCCCCCC DDDDDDD$
_________________

$\text { }$ciao Immagine ciao
E' la somma che fa il totale (Totò)

Rispondi