Algoritmo antiperiodo di una frazione

Dai blog precedenti abbiamo visto come lavorare sul periodo
di una frazione e come quest'ultimo dipendesse eslusivamente
dal denominatore della frazione.

Una frazione però può dare anche un antiperiodo. L'antiperiodo
è il numero di cifre dopo la virgola e che precedono quelle del
periodo.

Anche l'antiperiodo dipende esclusivamente dal denominatore
della frazione a/b. Per cui il numeratore può tranquillamente
essere a=1.

Alcuni esempi, con in rosso il periodo e in blu l'antiperiodo:

1/70 = 0.01428571428571428571428571429
1/130 = 0.007692307692307692307692307692
1/404 = 0.002475247524752475247524752475
1/808 = 0.001237623762376237623762376238

L'antiperiodo conta il numero di cifre antecedenti il periodo.

Da cosa dipende l'antiperiodo ed il periodo? E' lo stesso che chiedere:
"Da cosa dipende che un numero ha periodo finito, nullo o infinito?"

La periodicità, nulla, finita o infinita non è una proprietà
del numero (del denominatore della frazione) ma dipende da:
- base numerica che si considera (decimale, ottale, etc)
- numero di primi di cui è costituito il denominatore della frazione.


Ad esempio
1/10 = 0,1 è finito perchè 2, 5 e 10 sono contenuti in 10
1/3 = 0,33333 è irrazionale perchè 3 non è contenuto nella base 10

L'antiperiodo quindi è il massimo numero tra le potenze di 2^h e le potenze
di 5^k.

Quindi basta contare quante volte h è divisibile il numero per 2 e
quante volte k è divisibile il numero per 5 e si prende il massimo
tra i due valori h e k.

L'algoritmo quindi è molto semplice.

/*
*
* AntiPeriod of a fraction with
*
*/
AntPerN(n)= local(d2=0, d5=0); {

while( Mod(n,2) == 0, n = n/2; d2=d2+1);
while( Mod(n,5) == 0, n = n/5; d5=d5+1);

return(max(d2,d5));

}

Alla prox

Algoritmo sul gaussiano di una frazione, primalità e compositezza

In questo blog ci poniamo il problema di scrivere un algoritmo in PARI/GP per determinare il periodo di una frazione.

Nel blog precedente abbiamo detto che: 

1 - Si definisce gaussiano del numero N rispetto ad una base B, indicato come k = g(N) = T(1/N), “il più piccolo valore k tale che B^k = 1 mod N”.

2 - Si dimostra che il gaussiano k di un rapporto a/b dipende solo dal denominatore b, quindi nel calcolo del gaussiano si può porre a=1 e calcolare k = T(1/N), dove t è l'algoritmo da realizzare.

3 - Un teorema che deriva dal Piccolo Teorema di Fermat porta a dire anche che il gaussiano di n è un divisore della funzione di Eulero φ(n). In particolare se n è primo è φ(n) = n – 1.

Se dobbiamo scrivere degli algoritmi di primalità o di compositezza basati sulle frazioni continue occorre scrivere prima un algoritmo per il gaussiano.

/*

*  Period of a fraction with

*  gaussian function

*/

GaussN(n)= local(g=0, r=1); {

 while( Mod(n,2) == 0, n = n/2;);

 while( Mod(n,5) == 0, n = n/5;);

 while( g == 0 | r != 1,

        r = Mod(( 10 * r), n);

        g = g + 1;

 );

 return(g); 

}

 

Considerazioni sull'algoritmo

Scrivere un algoritmo che calcoli il gaussiano comunque è semplice, ma sicuramente il metodo non è veloce per numeri grandi (basta applicarlo ad esempio al numero di Mersenne 2^31-1)

In PARI/GP esiste anche un ulteriore metodo semplice da collocare comunque nell’ambito di un algoritmo; ad esempio sappiamo che sqrt(21)= 4,1,1,2,1,8 dove la parte sottolineata è il periodo T(sqrt(21)).Se usiamo contfrac(sqrt(21)) otteniamo il vettore [4,1,1,2,1,8,1,1,2,1,8,1,…].  Ora se a1 è il primo elemento del vettore e aj è il j-esimo elemento del vettore, allora il periodo T(sqrt(21))=j-1 se aj=2*a1. Ovviamente il metodo è poco applicabile se a1=0, ovvero la frazione non è periodica ma è finita o infinita (numero irrazionale).L’algoritmo presentato per il calcolo del gaussiano non usa però contfrac. La scelta dipende dal fatto che contfrac non sempre fornisce il risultato in modo facilmente trattabile nei casi di rapporti 1/N. Contfrac è più efficace nei casi di calcoli delle radici quadrate di un numero N.

Algoritmo di compositezza  (basato sul Teorema del blog precedente)

/*

*  IsComposite ?

*  -1 Boh

*   1 Yes

*   0 No (it's a prime number)

*/

isCompN(n)= local(g=0, status=-1); {

 if( Mod(n,2) == 0, return(status););

 g = GaussN(n);

 print("gaussiano(",n,") = ", g);

 if( g == n-1,

     status=0;

     print("No, it's a prime number!");

     return(status);

 );

 if( g != 1,

     if( frac((n-1)/g) != 0.0, status = 1;);

 );     

 if( status == 1, print("Yes, it's a composite number!"););

 return(status); 

}

/*

*  IsMyPrime ?

*   1 Yes

*   0 No

*/

isMyPrime(n)= local(status=0); {

 if( eulerphi(n) == n-1, status=1;);

 return(status); 

}

Se si guarda l’algoritmo isComposite ci si rende conto che, per numeri grandi, già ad esempio per un numero di Mersenne come 2^31-1, poiché il gaussiano è calcolato per successivi incrementi unitari ne consegue che sono necessari molti cicli. In tal caso è più veloce un algoritmo come isMyPrime o le funzionalità built-in di PARI/GP come eulerphi, isprime, ispseudoprime. Queste ultime funzioni built-in soffrono ovviamente del fatto che dipendono dal numero di primi precaricati e dalla RAM disponibile e allocata al programma.

Alla prox

Esiste un metodo per dire che un valore intero N non è primo?

No body ?  No party!!

Beh a pensarci sì; con le frazioni continue e l'espansione periodica è possibile creare un "test di compositezza" ad hoc. Brutto il termine "compositezza", ma l'italiano non offre di meglio perchè invece "compostezza" è un'altra cosa!.

Il risultato di una frazione può dare: 
1 assenza di periodo: numero finito o numero irrazionale  
2 presenza di periodo  
3 presenza di antiperiodo e periodo

Se al denominatore ci sono 2 e 5 o potenze di essi o combinazioni (perché fattori della numerazione per 10), avremo a che fare con un numero finito.

Si definisce gaussiano del numero N rispetto ad una base B, indicato come k = g(N) = T(1/N), “il più piccolo valore k tale che B^k = 1 mod N”.

Si dimostra che il gaussiano k di un rapporto a/b dipende solo dal denominatore b, quindi nel calcolo del gaussiano si può porre a=1 (come nell’algoritmo proposto). Ecco perché spesso è indicato come k = T(1/N).

Un teorema che deriva dal Piccolo Teorema di Fermat porta a dire anche che il gaussiano di n è un divisore della funzione di Eulero φ(n). In particolare se n è primo è φ(n) = n – 1.

Un algoritmo del gaussiano è presentato in APPENDICE.

Primalità? Meglio la compositezza.

Con le frazioni continue e l'espansione periodica in base 10 è possibile creare un "test di compositezza" ad hoc.

E’ brutto il termine "compositezza", ma l'italiano non offre di meglio, anche perché "compostezza" ha un altro significato!.

Teorema (R. Turco)

“Sia n>1 e dispari. Se il quoziente di 1/n ha un gaussiano k = T(1/N) diverso da 1 e (n-1)/T dà un quoziente non intero, allora n non è primo. Se il gaussiano di 1/n equivale a n-1, allora n è primo”.

Esempi

T(1/57)=18   (T diverso da 1)

(57-1)/18=3.1111 non intero

allora 57 è composto.

T(1/3337)=1610   (T diverso da 1)

(3337-1)/1610=2.0720496 etc

allora 3337 è composto.

T(1/3333)=4 con (3333-1)/3=883.0

allora il metodo non può dire se è composto.

T(1/9)=1   violazione della regola   

(9-1)/1=8 intero il metodo non può dire se è composto.

             

T(1/3367)=6 (3367-1)/6  il metodo non può dire se è composto.

T(1/3343)=3342=φ(3343)  è primo!!!

Valutazione del metodo

Se si guarda l’algoritmo isComposite ci si rende conto che, per numeri grandi, già ad esempio per un numero di Mersenne come 2^31-1, poiché il gaussiano è calcolato per successivi incrementi unitari ne consegue che sono necessari molti cicli.

In tal caso è più veloce un algoritmo come isMyPrime o le funzionalità built-in di PARI/GP come eulerphi, isprime, ispseudoprime. Queste ultime funzioni built-in soffrono ovviamente del fatto che dipendono dal numero di primi precaricati e dalla RAM disponibile e allocata al programma.

Alla prox

Le frazioni continue e di Farey, legami con zeta di Riemann e la geometria frattale

Le frazioni continue e di Farey,  legami con zeta di Riemann e la geometria frattale


Come promesso nel blog precedente, qui ci poniamo il seguente problema: poichè esiste un nesso tra frazioni continue e la fattorizzazione di un semiprimo N, sapendo che la fattorizzazione in qualche modo è legata alla zeta di Riemann, allora esiste un legame tra frazioni continue e zeta di Riemann?

Ebbene scopriremo insieme che la risposta è affermativa. Non solo ma troveremo legami con le frazioni di Farey ed i frattali e si mostra che le equazioni della gravità alle dimensioni extra compattizzate ci portano a dei frattali.

Con calma leggetevi:
http://www.gruppoeratostene.com/articoli/Tcn7.pdf


Penso che ora preparerete più soddisfatti il vostro "Albero di Frattale" ... oppss! volevamo dire di Natale!!!

Auguri di Buon Natale 2009

 

Geometria frattale: tra filosofia e necessità

Geometria frattale: tra filosofia e necessità

Il mondo intero deve agli antichi greci un immenso tesoro teorico come la filosofia, la geometria e la logica.

 

Euclide ci ha insegnato che con una retta si ha a che fare con una sola dimensione, con una superfice con due dimensioni e con un volume con tre dimensioni.

Ma un albero quante dimensioni ha?

E’ giusto parlare di tre dimensioni soltanto? E una nuvola? E le coste italiane oppure il contorno di un Lichene Rizhocarpon Geographicum o di una cellula?

Questa è una problematica che nasce già a “dimensioni normali”.

E’ noto che per talune problematiche come GPS, navigazione marina ed aerea si è passati alla geometria non euclidea (ad esempio quella sferica), ma ci sono situazioni per cui neanche le geometrie note sono adeguate e bisogna rivolgersi alla geometria frattale. 

Spesso è la distanza dell’osservatore che porta alla semplificazione a tre dimensioni, ma nell’ambito del problema che si affronta occorre sempre decidere se il livello di astrazione in gioco consente la semplificazione. Osservando una mela a distanza, per calcolare la velocità di caduta di un grave, possiamo immaginare la mela come una superfice o un cerchio, fino a ridurla ad un punto. Se ci avviciniamo cominciamo a considerarla una sfera, ma l’astrazione del problema nell’ambito della fisica classica ci consente ancora di considerarla un punto.

Esiste, quindi, un evidente rapporto tra osservatore e oggetto osservato e tra oggetto osservato e problema da risolvere: dal modo in cui si instaura questo rapporto, tra distanza di osservazione o grado di risoluzione e astrazione, si arriva ad un valore di dimensione diversa.

Un ottimo articolo a tal proposito è al link:

http://www.gruppoeratostene.com/articoli/RMNC.pdf

Però i frattali sono legati anche ad altre problematiche. Ad esempio esiste un legame con le frazioni continue, con la fattorizzazione e con la zeta di Riemann ... Ma di questo ve ne parleremo nel blog dei prossimi giorni quasi a preparazione di un delizioso Natale 2009.

Alla prox