Block Notes Matematico

2012-01-31T03:01:00.000-08:00

Quadrati di numeri pari

Lemma
Un quadrato pari è sempre un numero abbondante.

Dim.
Per definizione di quadrato pari è:
n = (2m)^2 = 4m^2
i suoi divisori sono quindi almeno:
[1,2,4,m,2m,4m,m^2,2m^2] la cui somma è maggiore di 4m^2

Sperimentare in PARI/GP con i numeri lievemente eccedenti

2012-01-04T03:39:00.000-08:00

Se definiamo i divisori di un numero n come il vettore d=[d1,d2,d3,...dk], escluso se stesso cioè dk<>n, allora un numero n lievemente eccedente è tale che:

s=sum(i=1,k,di)=n+1

I numeri lievemente eccedenti finora non sono mai stati trovati.

Lo studio "SOME RESULTS CONCERNING QUASIPERFECT NUMBERS - PETER HAGIS, JR. and GRAEME L. COHEN" mostra che se i numeri lievemente eccedenti esistessero sono al disopra di 10^35 e con non meno di 7 divisori oppure se 3 non è divisore di n al di sopra di 10^40 con non meno di 9 divisori.

Un nostro Teorema sull'argomento, è stato ritirato per degli errori, anche se CNR Solar lo marca con stato "Retired" ma ne dà ancora visibilità su INTERNET.

Il concetto dietro ad esso, di dimostrazione per assurdo, lo riteniamo ancora valido, ma la dimostrazione non è così banale come ci accorgeremo dall'analisi successiva, che rendiamo nota per stimolare gli appassionati di Teoria dei Numeri elementare a cercare una soluzione.

L'analisi è un tentativo di verificare se esistono metodi semplici circa la dimostrazione della NON esistenza.

Un semplice programmino PARI/GP per trovare un contro-esempio di esistenza è il seguente:

NLE(start=1,end=1000)= local(i=0, j=0,d=0); {
for(i=1,end,
d = divisors(i);
s=sum(j=start,length(d)-1,d[j]);
if(s==i+1,
print(i," è un numero lievemente eccedente");
);
d=0; s=0;
);
print(" Fine ricerca tra n=",start, " e n=", end);
return;
}

Analisi per induzione

Iniziamo un'analisi per induzione, partendo da un caso semplice.

Un numero lievemente eccedente con almeno 3 divisori deve rispettare che:
d1+d2+d3=n+1

ovvero
d2+d3=n

Poichè d3>d2 allora possiamo porre che:
d3=d2+k
da cui:
d2+d2+k=n
d2 = (n-k)/2 (a)

Poichè d2 è intero, n e k devono essere entrambi pari o entrambi dispari, altrimenti d2 non è intero ed è una contraddizione.

Lemma delle potenze
Un numero n=k^m con k>1 e dispari ed m>1 è difettivo.

Dim.

Se n=k^m, allora i suoi divisori propri, escluso n, sono [1,k,k^2,...,k^(m-1)]

Facciamo ora una dimostrazione per induzione.

Supponiamo m=3, allora i divisori propri sono [1,k,k^2]

Ora è evidente che k^2+k+1 < k^3 = k^2 * k.

Generalizzando è che k^(m-1)+k^(m-2)+...+k+1 < k^m = n, il che dimostra il Lemma.

Proprietà
(a) n non può essere potenza di 2 o k qualsiasi perchè n sarebbe difettivo. La proprietà discende dal Lemma delle potenze
(b) n dispari non può essere primo ma composto perchè avrebbe come divisori solo 1 e sè stesso che va escluso, cioè si otterrebbe un difettivo
(c) n pari non può essere perfetto perchè per i perfetti deve essere d2+d3=n-1 -> d2+d2+k = n-1 -> n-1-k/2 = d2 (b) mentre per i lievemente eccedenti deve essere vera la (a) che è diversa dalla (b)
(d) n pari con 3 divisori di cui almeno uno dispari, oltre a 1, allora d2 NON sarebbe intero
(e) n dispari con soli 3 divisori di cui d1=1 è difettivo, anche nel caso di potenze di numeri primi

Lemma dei 3 divisori propri
Un numero n con 3 divisori propri, escluso n, non può essere lievemente eccedente

Dim.
Le proprietà (a),(c),(d),(e) non consentono di avere un numero n con 3 divisori propri che risulta un numero lievemente eccedente.

Esempi

n=2^3=8
d=[1,2,4]
d1=1, d2=2, d3=2+2->k=2

d2 è intero ma essendo il numero potenza di 2 è difettivo

n=10
d=[1,2,5]
d1=1,d2=2,d3=5 se d3=2+k->k=3
d2=(n-k)/2 non è intero

n=22
d=[1,2,11]
d1=1,d2=2,d3=2+9->k=9
(n-k)/2 non è intero

n=77
d=[1,7,11]
s=19

d1=1,d2=7,d3=7+4->k=4
(n-k)/2 non è intero

Tutti i semi-primi o numeri RSA sono di questo tipo, con 3 divisori. Nessuno di essi può essere un numero lievemente abbondante.

Supponiamo ora che n abbia d=4 divisori, per cui
d2+d3+d4=n
d3 = d2 + k1
d4 = d2 + k2 con k2>k1

d2 + d2 + k1 + d2 + k2 = n
d2 = [n - (k1+k2)]/3

Questo vuol dire che per essere d2 intero il numeratore deve essere multiplo di 3.

Generalizzazione

In generale per d divisori, escluso n, è:

d2 = n - Q / (d-1) (1)

dove Q = Sum(ki,i=1..d-2)

ed n - Q deve essere multiplo di d-1 affinchè d2 sia intero.

E' evidente che se n è pari e d2=2 , Q è pari se i è pari o dispari se i è dispari.

Sperimentazione
Verifichiamo se esiste un Pattern che si presenta sempre.

Se cerchiamo i numeri fino a M che hanno solo 4 divisori, scopriamo che sono solo potenze di numeri primi quindi difettivi

M=100000
for(i=1,M,l=length(divisors(i))-1;if(l==4,print(i)));

n=16 [1,2,4,8] potenza di 2 è difettivo
n=81 [1,3,9,27] potenza di 3 è difettivo
n=625 [1,5,25,125] potenza di 5 è difettivo
n=2401 [1,7,49,243] potenza di 7 è difettivo
n=14641 [1,11,121,1331] potenza di 11 è difettivo
n=28561 [1,13,169,2197] potenza di 13
n=83521 [1,17,289,4913] potenza di 17

Inoltre qui
n=16
k1=2 k2=6

Q = k1 + k2 = 8
d - 1 = 3
d2=(16 - 8) /3 non è intero

n=81
k1=6 k2=24
Q = k1 + k2 = 30
d - 1 = 3
d2=(81 - 30) /3 non è intero

Lemma dei 4 divisori propri
I numeri n con 4 divisori propri non possono essere numeri lievemente eccedenti.

Dim.
I numeri a 4 divisori propri sono solo potenze di numeri primi e per il Lemma delle potenze il numero non può essere un numero lievemente eccedente.

Se cerchiamo i numeri fino a M con 5 divisori scopriamo che sono somma di potenze di numeri primi.

Escludendo i perfetti che non rispettano la (1), se il numero di divisori di n è pari e sono in gioco tutte potenze di numeri primi allora n è difettivo o abbondante

Se il numero di divisori di n è dispari e sono in gioco più numeri primi, con somme di potenze di numeri primi allora n è difettivo o abbondante

Usiamo un programmino che cerca gli abbondanti

SNA(start=1,end=1000)= local(i=0, j=0,d=0); {

for(i=start,end,
d = divisors(i);
s=sum(j=1,length(d)-1,d[j]);
if(s>i+1,
if( i%2==0, a=" pari ");
if( i%2!=0, a=" dispari ");
print(i," è un numero abbondante", a, " con ", length(d)-1," divisori");
);
d=0; s=0;
);
print(" Fine ricerca tra n=", start, " e n=", end);
return;
}

Mentre un programmino che cerca un certo numero di divisori è il seguente
SND(start=1,end=1000,adiv=5)= local(i=0, j=0,d=0); {

for(i=start,end,
d = divisors(i);
if(adiv==length(d)-1,
print(i," è un numero con ", length(d)-1," divisori");
);
d=0;
);
print(" Fine ricerca tra n=", start, " e n=", end);
return;
}

Esempi di numeri abbondanti
es:12,18,20,24,30,36

I numeri abbondanti non rispettano la (1), il risultato può essere non intero o negativo.

n=12 [1,2,3,4,6]
s=16>n
d=5
d-1=4
Q=k1+k2+k3=7
k1=1
k2=2
k3=4

12-7/4 non è intero

n=36 [1,2,3,4,6,9,12,18]
s>36
d=8
d-1=7
Q=k1+k2+k3+k4+k5+k6=40
k1=1, k2=2, k3=4, k4=7, k5=10, k6=16

36 - 40 /7 negativo

Il primo numero abbondante dispari è 945 con 15 divisori.

Numeri pari perfetti
es:
n=28
[1,2,4,7,14]
la somma è s=28 è un numero perfetto

Conclusioni
I numeri pari non possono essere lievemente eccedenti, risultano solo perfetti, difettivi o abbondanti. I numeri lievemente eccedenti se esistono devono poter essere dispari e non numeri primi o potenza di un numero.

L'analisi fatta potrebbe non essere esaustiva, al lettore attento la possibilità di segnalarmi controesempi ed errori per affinare l'analisi.

Alla prox

Zeta multipla

2011-12-06T22:41:00.000-08:00

Oggi riprende interesse una vecchia strada esplorata dal Eulero e Goldbach sulla zeta multipla. L'interesse è in ambito della Fisica, delle forme modulari e di altri settori della matematica.

Un articolo introduttivo dell'autore è al link:
http://www.scribd.com/doc/74917403/Zeta-multipla

Alla prox

Zeta pari

2011-12-02T04:35:00.000-08:00

Il giusto titolo del blog sarebbe forse stato "Relazioni tra RH generale dei numeri naturali, Zeta Dispari, Zeta Pari, Zeta di Riemann, Teorema di Voronin, ipotesi del continuo di Cantor", ma era un pò troppo lungo.

Nel divagare tra le varie zeta con simulazioni e studio si è con l'articolo
http://www.scribd.com/doc/74486449/ZetaPari

giunti a delle conclusioni affascinanti. L'autore non è un professionista o un accademico, ai lettori il vaglio di possibili errori. Ma se fosse vero e se l'uso di Maple non ci ha tradito, si sarebbe trovato un legame tra tutto ciò.

Se con la zeta di Riemann si riesce ad approssimare o trattare (grazie al Teorema di Voronin e al fatto che insiemi mumerabili hanno gli stessi zero della zeta di Riemann) insiemi numerabili o di cardinalità alef 0, forse con la somma di infinite zeta di Riemann o le zeta di Riemann multiple si potrebbero trattare gli insiemi non numerabili o di cardinalità alef 1 ... Con la zeta di Riemann si spiega la infinità dei numeri primi, con la Zeta Pari quella dei pari, con Zeta Dispari quella dei dispari, ma si può dimostrare forse anche l'ipotesi del continuo di Cantor con le zeta multiple? E' da approfondire e studiare. E' vero che la RH non è dimostrata ancora ma la zeta è una funzione stra-studiata e utilizzabile.

Alla prox

Zeta dispari

2011-11-17T05:51:00.000-08:00

Che succede nella formula di Eulero gli n sono solo i dispari e non tutti i numeri naturali?

Che succede se nella serie dei dispari eliminiamo qualche dispari?

Uno studio in tal senso è al link:
http://www.scribd.com/doc/73013918/ZetaDispari

In questo breve studio si esamina la zeta ottenibile solo con i numeri dispari, che nel seguito definiamo
come Zeta dispari.

Si fa una semplice analisi in campo reale che mostra un evidente legame con la zeta di Eulero, si
osservano i valori delle costanti e si analizza il tutto in campo complesso dove si osserva, eliminando
determinati numeri dispari dalla serie, come gli zeri spariscono.

Alla prox

Zeta (s)fortunata

2011-11-13T02:37:00.000-08:00

I numeri fortunati (Lucky Numbers) in Teoria dei numeri sono quei numeri naturali che discendono dal setaccio di Ulam. Diversi studi hanno evidenziato molte somiglianze di essi con i numeri primi: l'esistenza di un teorema analogo al teorema dei numeri primi, la densità, la RH, la GRH, Goldbach etc.

A tal proposito si è provato a definire una nuova zeta, la zeta fortunata e a studiarla.

Un articolo a tal proposito è al link:
http://www.scribd.com/doc/72528163/Zeta-s-fortunata

criterio di Riesz, il criterio di Baerz Duarte, ed altre RH equivalenti

2011-10-07T08:32:00.000-07:00

Sulla zeta esistono anche lavori recenti e interessanti, come il criterio di Riesz, il criterio di Baerz Duarte, il Teorema di Voronin, la frattalità e il lavoro ed i Teoremi di Davide Schipani.

Dall'ultimo lavoro è possibile ipotizzare una ulteriore criterio RH equivalente, esposto al link:

http://www.scribd.com/doc/67749588/Criteri-di-Riesz-e-Baerz-Duarte-Teorema-di-Voronin-ed-altre-trasformazioni

Alla prox.

Metodi per lo studio della zeta di Riemann

2011-10-04T01:10:00.000-07:00

Il Teorema di Godel, beffardo, sostiene che fin quando i matematici hanno costruito una impalcatura
matematica coerente, possono esistere delle cose che con essa non sono dimostrabili.

Questo oltre alla possibilità di non aver trovato un sofisticato metodo per poter dimostrare l'anello
mancante.

Nella teoria dei numeri analitica, spesso si ricorre ad altri settori per poter verificare se è possibile
trovare nuovi procedimenti.

L'ipotesi di Riemann è uno degli argomenti di tal genere: sulla RH esistono evidenze ma non si riesce a
dimostrarlo come teorema. Inoltre in cento anni si sono scritti fiumi di pagine di ricerca e trovate molte
RH equivalenti (a dire il vero sono oltre cento le RH equivalenti e tendono a crescere).

Il metodo delle trasformazioni di Moebius è uno dei tanti che sono stati usati (vedi articolo al link
http://www.scribd.com/doc/67257705/Il-metodo-delle-trasformazioni-per-le-RH-equivalenti).

Il vantaggio di una RH equivalente è solo di poter fare un attacco indiretto alla RH, cercando un contro-esempio numerico, ma nel 99% dei casi non contribuisce alla dimostrazione della RH.

L'alternativa è di "rivedere" ciò che è dato per assodato, rismontarlo e aggiungere se necessario dei Teoremi.

Sulla RH si è in "sofferenza dimostrativa" a causa di due, tre cose: la simmetria, l'equazione funzionale e/o
la funzione Gamma. Conosciamo davvero tutti i Teoremi su questi punti? E' proprio qui che è evidente che ci
viene meno qualcosa che non aiuta a dimostrare che tutti gli zeri non banali sono sulla retta critica.

zeta di Riemann - le costanti di Stieltjes e il criterio di Li

2011-09-24T09:12:00.000-07:00

Il criterio di Xiang-Jin Li è una RH equivalente, basata soprattutto sulle costanti di Stieltjes e sul concetto di trasformazione particolare di Mobius che consente di trasformare il piano complesso in modo che la retta critica si trasformi in un disco circolare.

L'idea discende da Weil, ma pochi hanno saputa sfruttarla al meglio.

Il criterio di Li costituisce un ulteriore tecnica di attacco indiretto all'ipotesi di Riemann, che sorniona e sorridente rimane ancora lì a scuotere la testa nei nostri confronti ...

Un articolo sul criterio di Li è al link:
http://www.scribd.com/doc/66153928/Zeta-di-Riemann-costanti-di-Stieltjes-e-il-criterio-di-Li

Alla prox

Serie divergenti - zeta e sviluppo in serie di Eulero-Mac Lauren

2011-09-17T11:58:00.000-07:00

Secondo Abel e Cesaro non valeva la pena approfondire le serie divergenti, poi si è scoperto che non è così.

La zeta di Riemann permette oggi disinvoltamente di calcolare cose che sembrano bizzare: la serie infinita che somma tutti 1 si pensava che fosse divergente e, invece, converge ad un numero negativo!

Come si analizzano queste serie, senza la zeta di Riemann? Il grande matematico Ramanujan ha lasciato nei suoi notebooks molte idee originali, ma soprattutto una grande matematica ...

Un articolo sull'argomento è al link:
http://www.scribd.com/doc/65316487/Serie-bizzare-zeta-e-sviluppo-in-serie-di-Eulero-Mac-Lauren

Alla prox

Sotto il segno della zeta

2011-09-12T02:23:00.000-07:00

Attualmente sono allo studio molte funzioni zeta oltre alla famosa zeta di Riemann: la zeta di Dedekind (importante per il gap di massa altro problema del millennio), la zeta di Selberg per le superfici di Riemann, la zeta di Ihara, zeta di Fibonacci, la zeta di Keith, la zeta Fattoriale, la zeta dei Primoriali, etc.

La zeta di Ihara, ad esempio, ha grosso interesse nei grafi e nelle sue possibili applicazioni (social network etc). In tutte queste zeta c'è sempre la traduzione matematica, in varie modalità, della ipotesi di Riemann.

Esse sono studiate principalmente sia per trovare correlazioni con la zeta di Riemann, ma soprattutto per trovare nuove strade utili per la risoluzione del problema del millennio, ovvero l'ipotesi di Riemann (RH) o congettura di Riemann.

Lo studio delle varie zeta e della zeta di Riemann sono legati a moltissime problematiche di Fisica e di altri settori: teoria delle stringhe, campi p-adici, gap di massa (Yang e Mills), gravità e frattali, teoria dei grafi, crittografia, fattorizzazione etc.

Può darsi che la soluzione dell'ipotesi di Riemann richiederà ancora moltissimo tempo, ma sicuramente per motivi pratici di molti settori serve l'approfondimento ulteriore e continuo su queste tematiche.

Uno studio sulla zeta fattoriale è al link:
http://www.scribd.com/doc/64659653/ZetaFattoriale

Alla prox

La musica dei numeri primi

2011-09-11T07:03:00.000-07:00

Esiste una armonia, una musica dei numeri primi?

In realtà sì. Dal loro studio si evidenzia che esiste una forma con cui si distribuiscono nell'insieme dei numeri e che non è casuale.

Un articolo divulgativo è al link:
http://www.scribd.com/doc/64574400/MusicaDeiNumeriPrimi

Potrete ascoltare anche da un wav la musica di 100 zeri non banali dovuti all'espressione esplicita trovata da Riemann.

Alla prox

Dai Numeri Primi all'ipotesi di Riemann, visti attraverso "Maple"

2011-08-25T11:27:00.000-07:00

Dopo una lunga sosta, eccoci di nuovo sulla pista di Riemann, vista attraverso uno strumento di analisi matematica veramente interessante: Maple.

I matematici, gli studenti e gli appassionati, che dispongono di Maple, possono scaricare l'articolo da
http://www.scribd.com/doc/63814615/Dai-numeri-primi-alla-zeta-di-Riemann-visti-attraverso-Maple e organizzarsi un worksheet secondo l'articolo.

Esso vi illustra a partire dalla legge di Gauss e il Teorema dei Numeri Primi (col Logaritmo integrale), tutto il percorso Maple, matematico e grafico, per assaporare le cognizioni dell'argomento.

E' difficile che si trovino su INTERNET le modalità grafiche e matematiche necessarie per lavorare con Maple sulla zeta di Riemann.

Il worksheet presentato è un semplice, ma non esaustivo, tentativo per diffondere tali informazioni in chiave Maple.

Alla prox

THE ZETA-FUNCTION OF RIEMANN

2011-06-26T12:01:00.000-07:00

Un ottimo punto di inizio sulla zeta di Riemann e soprattutto un ottimo libro libero da scaricare, al link:
http://www.archive.org/details/zetafunctionofri032076mbp

Alla prox

Tools di matematica evoluti ed open source

2011-06-19T10:40:00.000-07:00

Se siete appassionati di teoria dei numeri e di PARI/GP e avete voglia di disporre di un ambiente con funzionalità ulteriormente avanzate e Open Source, consiglio di dare un'occhiata a SAGE, un progetto di notevole valore.

Installare una ISO di SAGE su Windows XP/2000/Vista/7 non è difficile. Richiede i seguenti passi:
1) Installare Oracle VirtualBox ultima versione http://www.virtualbox.org/wiki/Downloads
   prelevando quella per Windows

2) Prelevare un ISO funzionante di SAGE
    http://www.mirrorservice.org/sites/www.sagemath.org/index.html
e prelevare Microsoft Windows LIVE CD

3) Da Oracle VirtualBox fare:
    New -> Next
   Name inserire SAGE, Operating System inserire Other, Version inserire Other Unknown, Next, Base
   Memory Size selezionare 512 Mbyte

4) Create New Hard Disk, Next, Dynamically expanding storage,Next, Selezionare una Location (una directory sul Desktop ad esempio Sage)

5) Date una dimensione allo storage (2Gb o meno, tanto se lo avete definito dinamico gli da pochi Kbyte iniziali), Finish

6) Start, click sulle videate fino ad arrivare a Select Installation Media e selezionare dove è l'ISO, Next e attendere i vari caricamenti fino a farla partire

Attenzione: il tasto Ctrl a destra vi consente di uscire dall'ambiente mentre per entrare a usare il cursore interno basta un click di mouse

7) Ora avete un ambiente Linux Puppy disponibile con SAGE.

8) Dovete fare un pò di pratica priam con l'ambiente , poi seguite un Tutorial per l'uso ad esempio
    http://www.sagemath.org/pdf/SageTutorial.pdf

Buon divertimento

P.S: Se sviluppate software ulteriore sulla zeta di Riemann, oppure ulteriori funzionalità grafiche da aggiungere a zeta.txt e lambert.txt fatemi sapere, posso pubblicare anche i vostri articoli se interessanti.

Alla prox

Irrazionali e zeri non banali della zeta di Riemann

2011-06-18T08:19:00.000-07:00

Studiando gli zeri della zeta di Riemann, a nessun appassionato può sfuggire il valore che assumono le parte immaginarie degli zeri.

Sono valori irrazionali, non si vedono periodicità. E' possibile avere evidenza se sono irrazionali algebrici o trascendenti? E' una sfida che ci si può porre.

Mentre alcune costanti di Apery sono state dimostrate come irrazionali trascendenti e legate al famoso problema di Basilea (Vedi Sulle spalle dei giganti) , che sappiamo dire sugli zeri della zeta di Riemann?

Una dimostrazione teorica, sotto forma di Teorema, al momento non esiste, ma ci sono molti studi a tal proposito sia nel settore degli irrazionali (vedi Teoremi di Lioville, di Galoise, etc) che della zeta di Riemann.

E' possibile avere evidenze numeriche che siano trascendenti? Un articolo in tal senso "Zeta di Riemann - trascendenza parte immaginaria zeri non banali" e l'ausilio di un coltellino svizzero come PARI/GP portano in tale direzione http://www.scribd.com/doc/58150801/Zeta-di-Riemann-%E2%80%93-trascendenza-parte-immaginaria-zeri-non-banali

Alla prox

Puzzle e numeri primi

2011-06-08T22:59:00.000-07:00

Un puzzle è un gioco costituito da un disegno rettangolare, che viene suddiviso in N pezzi. Il totale N dei pezzi è dato dal prodotto di quelli presenti sul lato dell'altezza per quelli sulla base del rettangolo N=b*h.

Il rettangolo del puzzle per essere "ben fatto" deve essere almeno di formato DIN, ovvero il rapporto tra b ed h deve essere pari almeno a 1,4 e non deve rappresentare una striscia, cioè uno dei lati non deve essere molto piccolo rispetto all'altro.

Si scopre in questo modo che non è sempre possibile creare puzzle con un numero N qualsiasi di pezzi.

Ad esempio non è possibile farlo per N=2000, nonostante in commercio troverete scatole con 2000 pezzi!

Infatti N=2000 è scomponibile 2000=2^4 * 5^3, il che darebbe teoricamente possibili i seguenti prodotti:
1*2000 = 2*1000 = 4*500 = 8*250 = 10*200 = 16*125 = 20*100 = 25*80 = 40*50

Per evitare di ottenere una striscia, solo gli ultimi due prodotti sono interessanti; ma si scopre che il formato DIN non è rispettato; difatti 80/25 = 3,2 e 50/40=1,25.

Con 1998 pezzi è possibile ottenere un puzzle: 1998 = 2*3^3*37 e 2*3^3/37 è circa 1,46

Per cui se contate i pezzi di un puzzle dichiarato di 2000 pezzi è abbastanza probabile che ne contenga 1998, per cui non date la colpa a vostro figlio che ha perso 2 pezzi!

Alla prox

Sistemi operativi embedded e Distro Linux

2011-06-07T12:28:00.000-07:00

Uno dei settori di recente interesse sono i sistemi operativi customizzati, utili per creare sistemi di controllo
e ludici oppure per telefonini, i palmari etc. Alcuni esempi sono costituiti da Xbox, i telefonini con sistemi
operativi Linux-like, Android etc, i sistemi di controllo per piccole locomotive etc.

Spesso tali sistemi operativi vengono integrati con nuovi componenti hw (tipicamente con PIC) con opportuno firmware, ovvero software progettato e sviluppato ad hoc per integrare il tutto. In altre situazioni si possono creare distro di sistemi operativi Linux per supportare dei Social Network (radiomatori, matematici, fisici, elettronici etc).

Si può creare e assemblare un sistema operativo Open Source, come Linux? Certamente sì. Ogni studente e ogni professionista si è almeno divertito a farlo almeno una volta con i suoi amici.

Occorre un pò di esperienza sistemistica e di compilazione C/C++ ma è adatto anche per imparare. Soprattutto serve pazienza e almeno 3-4 mesi per completare il tutto.

Come si inizia?
1 - Innanzitutto serve un buon PC di base con abbastanza RAM, un buon processore e un bel hard disk
esterno magari.
2- Procurarsi una macchina virtuale: efficace è quella Oracle VM Virtual Box
3 Disporre dell'ultima versione del sistema operativo Linux preferito (Fedora 15 ad esempio) che servirà
    per buildare e assemblare il nuovo sistema operativo
4 - Procurarsi le specifiche di "Linux from Scratch" LFS e BLFS e scaricarsi i pdf relativi
5 - Creare una macchina virtuale con espansione dinamica e darle un nome (quello del sistema operativo che volete creare). Ad esempio con 512Mbyte per la memoria e 161 Gb del filesystem
6 - il filesystem potrete montarlo come SATA aggiuntivo a Fedora
7 - consiglio di scegliere ext4 come tipo di filesystem e creare almeno i partizionamenti application, swap e LFS

Ad esempio
161 Gb
/application     2Gb     /dev/sdb2 --> sda2 sul sistema reale
/swap         1Gb     /dev/sdb3 swap
/LFS         158G    /dev/sdb4 --> sda4 sul sistema reale

mount solo di /LFS   su /media/LFS fatto da root della macchina host o con Disk utility. e ricordatevi inizialmente anche dello swapon -v /dev/sdb3
export LFS=/media/LFS    da root altrimenti non riconosce $LFS

8 - scaricare i pacchetti consigliati per la build e seguire il manuale LFS poi quello BLFS

Alla fine avrete una distribuzione Linux testuale e grafica. A questo punto occorre installare gli applicativi da supprortare per la Social Network desiderata. Attenzione che se rendete pubblica la distro Linux avrete l'obbligo morale di supportare gli aggiornamenti dei suioi pacchetti, meglio creare un gruppo su INTERNET che se ne occupa.

Alla prox

SAT, 2SAT, 3SAT e P versus NP

2011-03-05T03:00:00.000-08:00

Uno dei problemi del millennio è, come abbiamo visto anche in blog precedenti, P=NP? Ci si chiede cioè, di fronte a problemi decisionali tipicamente NP, non risolvibili con algoritmi polinomiali (P) essendo per natura essi esponenziali con l'input come il problema dello zaino e tanti altri, se è possibile individuare degli algoritmi polinomiali (deterministici o non ) tali che si possa poi affermare, invece, che P=NP. Cook e Levin aprirono la strada col loro Teorema su queste tematiche ed una delle loro dimostrazioni riguardava i problemi SAT, cioè i problemi di "Soddisfacibilità booleana" (SAT) costituiti da AND di clausole, dove ogni clausola è un OR di letterali. Ad esempio il 2SAT ha un OR con 2 letterali e il 3SAT un OR con tre letterali.

Per il 3SAT, ad esempio, il problema è di:
1) verificare se esiste una soluzione TRUE per la funzione logica assegnata
2) se la funzione logica esaminata è minimizzabile
3) elencare le soluzioni delle funzione logica assegnata

La sfida è di trovare, per fare questo, un algoritmo polinomiale. Un articolo su questo è su www.scribd.com/rosario_turco

Provate a scrivere un algoritmo in PARI/GP e poi fatemi sapere ... Soprattutto considerate cosa succede all'aumentare del numero di letterali e la velocità del vostro algoritmo.

Geometria integrale

2011-02-23T00:54:00.000-08:00

Un settore molto interessante e moderno è la Geometria integrale. E' nata alla fine del XX secolo e cerca di mettere insieme la geometria e le probabilità geometriche.

E' un settore matematico di notevole interesse in campo biologico e medico. Su esso si basano le innovazioni
e le nuove ricerche da cui sono nate la tomografia assiale computerizzata (TAC), la risonanza magnetica (RM), la recentissima stereologia che è un insieme di metodi per esplorare lo spazio tridimensionale a partire dalla conoscenza di sezioni bidimensionali o proiezioni sui piani.

La stereologia permette ad esempio di sapere il volume di un oggetto, il numero di particelle o la curvatura totale di una superfice. Molti sono i settori a cui già è legata come statistica, geometria, geometria non euclidea, medicina, geologia, geometria computazionale per le simulazioni 2D e 3D; molti altri potrebbero essere legati o potrebbero sfruttarla (frattali, simulazioni n-D etc).

Nel 1979 ad esempio il Nobel per la Medicina fu assegnato all'inglese Godfrey Hounsfield per i suoi studi sulla TAC, basati sulla geometria integrale.

Grazie al computer oggi sono risorte alcune materie dimenticate come la geometria discreta e combinatoria, adatta al computer data la sua natura discreta, a cui poi si aggiungono le più moderne geometria vettoriale, tensoriale e matriciale.

Tale tipo di geometria è di notevole importanza anche nel CAD (Computer Aided Design) per il disegno e la progettazione (ingegneria, architetura etc) o per l'intelligenza artificiale e la robotica per mettere a punto sistemi di visione robotici o per la meteorologia, immagini satellitari etc.

La geometria integrale è nata ufficialmente nel Novecento con lo spagnolo Luis Santalò (1911-2001), con la sua opera "Geometria integrale e probabilità geometrica". Tuttavia le primissime origini risalgono al Settecento con Georges Louis Leclerc, conte di Buffon.

Leclerc scrisse il "Supplemento alla Storia Naturale" al cui interno c'era il "Saggio di aritmetica morale", un suo tentativo di studiare la realtà umana attraverso la matematica.

Se ci pensate non è molto diverso da quello che accade oggi, ricordate ad esempio le puntate della serie televisiva Numbers?

L'attore, che rappresentava un matematico, in diverse puntate cerca di matematizzare le emozioni ed i comportamenti umani, tenendo conto di statistica etc. Nè più nè meno di quello che iniziò a fare Leclerc.

La geometria integrale nasce già nel saggio di Leclerc con uno dei problemi che propone (oggi risolto) e definito "L'ago di Buffon".

"L'ago di Buffon" pone il seguente quesito:"Supponiamo un piano diviso in rette orizzontali (un foglio su cui ci sono tracciate rette parallele) e separate tra loro a distanza costante d, se lanciamo su esso un ago di lunghezza b, con b maggiore di 0 ma minore di d, che probabilità c'è che l'ago intercetti una retta?"

L'esperimento va ripetuto con un certo numero di lanci dell'ago, proprio come se fosse un dado o una moneta. Ad ogni lancio l'ago potrebbe tagliare una retta o nessuna. La cosa straordinaria è che tali probabilità sono legate a pi greco!

Se P è la probabilità intesa come rapporto tra numero di volte che l'ago interseca una retta v e numero di lanci n, si ha che:

P=v/n e se b è minore o uguale a d si ottiene P=v/n=2b/(d * pi greco)

Leclerc quindi dimostrò con un lungo procedimento e correttamente che pi greco = 2nb/vd

Facendo un numero notevole di lanci si riesce ad approssimare pi greco con un bel numero di cifre dopo la virgola. Lazzaroni lanciò l'ago per 34.080 volte ottenendo pi greco = 3.1415929

"L'ago di Buffon" suggerisce la possibilità di misurare oggetti geometrici come lunghezze, aree, volumi soprattutto laddove non si hanno molte informazioni certe e facendo uso della probabilità. Permette quindi anche di formalizzare concetti come la misura di rette,piani etc.

Qua aggiungerei che la cosa non dipende nemmeno dal tipo di geometria che usiamo, potrebbe benissimo essere una geometria non euclidea come quella di Riemann ovvero una geometria sferica e quindi di interesse per la Fisica e molte altri settori scientifici. Ma esistono anche la geometria ellittica e iperbolica.
Ovviamente può essere interessante per le problematiche di fisica a n-dimensioni.

Come si vede la geometria integrale, valorizza la geometria alla pari dell'aritmetica su problematiche di probabilità, di combinazioni, permutazioni etc. ed ha un vantaggio "visivo" ulteriore.

Alla prox

In matematica non tutto è già noto

2011-02-20T08:45:00.000-08:00

I criteri di divisibilità sono un tema della Teoria dei numeri, simpatico e utile e ovviamente sono dimostrabili le regole che nascono della divisibilità per 3, per 9 etc.

Non crediate che si è messo il punto fine a questa tematica semplice ma interessante.

Grandi cultori di queste tematiche furono: Leonerdo Fibonacci (Pisa: 1170-1250), Blaise Pascal (Francia: 1623-1662), Henri Poincarè (Francia: 1854-1912) solo per citarne alcuni tra i più noti. Anche molti altri
italiani hanno concorso a queste tematiche.

Vediamo nel seguito solo alcuni esempi di divisibilità.

Divisibilità per 7
Una regola è di isolare l'ultima cifra del numero assegnato, raddoppiarla e sottrarla al numero rimanente di partenza.

Se il risultato è 0 o multiplo di 7 il numero è divisivile per 7. Se il numero è grande reiterare il procedimento.

Esempio
105 -> 10_5 -> 5x2=10 10-10=0 quindi 105 è divisibile per 7

394 -> 39_4 -> 4x2=8 39-8=31 non è divisibile per 7

12578 -> 1257_8 -> 8x2=16 1257-16=1241 124_1 -> 1x2=2 124-2=122 12_2 -> 2x2=4 12-4=8 8 non è divisibile per 7.

Divisibilità per 13
E' divisibile per 13 se isolando l'ultima cifra e considerando il quadruplo di essa, sommando il risultato parziale ottenuto con la cifra rimasta di partenza, il risultato finale è divisibile per 13.

Esempio
169 -> 16_9 9x4=36 16+36=52 che è divisibile per 13
943 -> 94_3 3x4=12 94+12=106 -> 10_6 6x4=24 10+24=34 non è divisibile per 13

Divisibilità per 11 per numeri a n>2 cifre
E' divisibile per 11 se isolando le ultime 2 cifre, e si sommano al numero rimanente precedente, il risultato è divisibile per 11.

Esempio
352 -> 3_52 3+52=55 divisibile per 11
1052 -> 10_52 10+52=62 non è divisibile per 11.

Metodo classico divisibilità per 11
Se alla somma delle cifre di posto dispari si sottrae la somma delle cifre di posto pari e il risultato è 0 o multiplo di 11 esiste la divisibilità per 11.

Esempio precedente
352 3+2=5 5-5=0 divisibilità per 11

Esempio a molte cifre
87635064 -> 8+6+5+6=25 7+3+0+4=14 25-14=11 divisibile per 11

Dimostrazione di divisibilità
Ok, ma se dovreste dimostrarli che sono metodi corretti? Si usano le manipolazioni di prestigio algebriche!

Facciamo un esempio con 11.

Chiamiamo con a la cifra dell'unità, b quella delle decine, c le centinaia etc.

N=a+10b+100c+1000d+...= a+10(b+10c+100d+...)

Se da N ci sottraiamo 11(b+10c+100d+...) che è multiplo di 11, che succede?

a+10(b+10c+100d+...)-11(b+10c+100d+...)=a-b-10(c+10d+...)

Questo risultato sarebbe lo stesso resto di quello che si ottiene dividendo N per 11.

Se a tale risultato ci sommiamo invece 11(c+10d+...) multiplo di 11 otteniamo adesso:

a-b-10(c+10d+...)+11(c+10d+...)=a-b+c+10(d+...)

Se proseguiamo a sottrarre 11(d+...) si ottiene:

a-b+c-d+...

cioè la regola di sopra di sommare le cifre di posto dispari tra loro e quelle pari tra loro, per poi sottrarre come dice la regola precedente.

Si può dimostrare anche l'altro metodo di divisibilità per 11 basato sull'isolamento di 2 cifre (almeno decine e centinaia se sono 3 cifre). In tal caso N va scritto nel seguente modo:

N = a + 100b + 10000c+...=a+100(b+100c+...)

Ora sottriamo allora a N 99(b+100c+...) che è multiplo di 11

a + 100b + 10000c+...=a+100(b+100c+...) - 99(b+100c+...)= a + b + 100(c+...)

a questo possiamo sottrarre 99(c+...) divisibile per 11 e si ottiene

a + b + c + ...

Cioè si ottiene la regola N è divisibile per 11 se isolando le ultime 2 cifre, e si sommano al numero rimanente precedente, il risultato è divisibile per 11.

Divisibilità per 19
Un numero è divisibile per 19 se le sue decine più il doppio delle sue unità danno un multiplo di 19.

N=10x+y
Abbiamo scritto y come unità e x è di peso 10 come decina.

Se la regola è vera devo scrivere che N' = x+2y e deve essere multiplo di 19.

A questo punto se facciamo
10N' - N = 10(x+2y) - (10x + y) = 19y

Quindi se N' è multiplo di 19 allora:
N = 10N' - 19y
N si divide esattamente per 19.

Esempio
38 -> 3+2x8=19 divisibile per 19

Alla prox

Le congetture e gli attacchi diretti e indiretti

2011-02-13T00:14:00.000-08:00

Nella Teoria dei Numeri esistono varie congetture non ancora dimostrate, apparentemente semplici, ma di una complessità notevole se li si vuole realmente dimostrare con la matematica analitica.

Un esempio notevole è il Postulato di Bertrand, unico dimostrato (da Chebyscev), che afferma nella sua versione semplice che tra n e 2n con n>1 esiste almeno un numero primo. Una volta dimostrato nell'Ottocento, successivamente si sono avute dimostrazioni più semplici di Ramanujan e di Paul Erdos.

Per comprendere come si fa una dimostrazione di una congettura come questa basta che date un'occhiata ad esempio a: http://it.wikipedia.org/wiki/Dimostrazione_del_postulato_di_Bertrand

Ebbene congetture più restrittive e legate tra loro sono la congettura di Oppermann che afferma che tra n^2-n e n^2+n esistono almeno due numeri primi. C'è un effetto domino tra alcune congetture legate; ad esempio se si dimostrasse la congettura di Cramer, anche la congettura di Oppermann sarebbe risolta, il che implicherebbe anche la soluzione della congettura di Legendre.

Un legame esiste anche tra la congettura di Andrica e quella di Cramer. Lo stesso postulato di Bertand è un caso particolare della congettura di Legendre.

Il postulato di Bertrand si potrebbe esprimere in una forma generalizzata come segue:

Per ogni n>1 esiste sempre un numero primo tale che kn < p < (k+1)n

Se k=1 abbiamo il postulato di Bertrand, se k=n abbiamo la congettura di Legendre.

Per k=2 il postulato di Bertrand generalizzato è stato dimostrato da Bachraoui con la stessa tecnica di Erdos, con i coefficienti binomiali. Rimane da dimostrarlo per k>2.E questa è una strada da non trascurare per la dimostrazione finale.

La congettura di Legendre è la più affascinante ed afferma che tra (n+1)^2 e n^2 esiste almeno un numero
primo.

Il problema non è "se sono vere o meno" queste congetture. Non serve che qualcuno esca fuori e lo dichiari.
Gli innumerevoli esempi e la ricerca di contro-esempi danno l'evidenza della verità su esse, come sulla
congettura di Riemann.

Il problema è proprio di trovare il giusto procedimento matematico analitico per dimostrarle vere. E' sempre accaduto che quando una congettura è stata risolta è emersa una nuova tecnica a vantaggio del progresso matematico.

Diversi lettori mi hanno fatto domande sul cosa si intende dimostrare una congettura.

Sicuramente dimostrare una congettura non è fare esempi, tabelle di numeri e calcoli con stime approssimate del Teorema dei Numeri Primi, queste sono tecniche di ricerca al massimo di contro-esempi o per stabilire una stima. Occorre, invece, partire dalla ipotesi della congettura e trovare un metodo con vari passaggi generalizzati, algebrici, geometrici,analitici o trigonometrici, in dipendenza del tipo di problema e proposizione che si sta affrontando, fino ad arrivare ad un risultato che confermi la tesi o la contraddice. Altrimenti non si è dimostrato niente, ma si è dato solo delle evidenze.

Un modo economico diverso, è quello di progettare attacchi diretti e indiretti alle congetture per cercare, graficamente o numericamente, con del software sviluppato ad hoc da noi stessi, dei contro-esempi. Se si trova un solo contro-esempio sono false, in caso contrario rimane aperta ancora la ricerca della loro dimostrazione di verità.

Gli attacchi diretti sono attacchi alla congettura nella sua forma principale. Un esempio di attacco diretto
è l'articolo "Aggirandosi tra i plot della zeta di Riemann", dove sia numericamente che graficamente con del software si verifica la posizione degli zeri della zeta di Riemann.

Un attacco indiretto è invece un attacco grafico e numerico, ad una congettura equivalente. Ad esempio per
l'ipotesi di Riemann ci sono innumerevoli congetture RH equivalenti: criterio di Robin, criterio di Lagarias,
funzione di Liouville, Frobenius etc. Nel caso di Riemann ce ne sono almeno una ventina e spesso ne nascono di nuove.

Un esempio, invece, di proposta di dimostrazione è sempre quello dell'autore sulla zeta di Riemann.

Per chi è interessato a tali tecniche, in tal caso occorre stilare la lista di tutte le congetture equivalenti, magari su Wikipedia, poi comprendere bene cosa dichiarano rigorosamente e cercare di attaccarle una dopo l'altra, per la ricerca di contro-esempi.

Questa tecnica è più pratica e richiede meno conoscenze dimostrative matematiche: basta un solo contro-esempio per dimostrarle false. Spesso la scoperta del contro-esempio porta alla correzione della congettura o al suo definitivo abbandono.

Con le tecniche di attacco furono dimostrate false varie congetture (Mertens, etc). Grossi nomi di utilizzatori di tecniche del genere sono Alan Turing, Odlyzko etc.

Se l'attacco non dimostra la falsità con un contro-esempio, l'attacco è fallito e la congettura è ancora da
dimostrare.

Affinando queste tecniche di attacco si finisce, inevitabilmente, con lo scoprire un "comportamento nascosto" che non si conosceva. Ad esempio con la zeta di Riemann se non si fosse affrontata una cosa del genere non si conoscerebbero ora i punti di Gram ed altro etc.

Spesso la dimostrazione, invece, è corretta ma non è stata fatta con i metodi analitici come si richiede per ottenere progressi sull'argomento (ad esempio nel campo delle funzioni complesse di variabili complesse o delle funzioni ellittiche), per cui alla fine è una soluzione minore o elementare, cioè è considerata solo una evidenza; perchè potrebbero esistere implicazioni che il metodo elementare non mette in risalto.

Un articolo delle attuali conoscenze sulla congettura di Legendre è a:
www.scribd.com/rosario_turco (Collections contiene tutti gli articoli dell'autore).

Alla prox

Shrimp Factored Problem

2011-02-04T11:49:00.000-08:00

Spesso per studiare un problema si cerca di semplificarlo con un altro, a volte l'espediente riesce ma in altri casi nasce un altro problema.

Un problema "carino" da me inventato mentre studiavo il problema di Collatz e gli automi cellulari è quello che
chiamo lo "Shrimp Factored Problem" ovvero il "problema del Gambero fattorizzato".

Il suo enunciato è il seguente:
Sia dato un intero N qualsiasi e si procede nel seguente modo:
1) Se N è primo si moltiplica randomicamente per un numero presente nell'intervallo [2,N-1] e si passa allo step successivo 2). Se N non è primo si prosegue lo stesso allo step 2).
2) Si fattorizza il numero N ottenuto dallo step 1) e si preleva il minor fattore. Se il fattore è 2 si arresta il procedimento, altrimenti si passa allo step 1) con l'N ottenuto

I quesiti che si pongono sono almeno due:
a) L'automa si arresta sempre? Ovvero la sequenza di numeri che si ottiene arriva sempre a 2? La sequenza è sempre convergente o può avere cicli?

b) Come si calcola il numero di step che verranno fatti?

Eccovi un algoritmo in PARI/GP utile all'analisi:

Shrimp(N)= local(s="", Np=0); {
if( N == 2, error("You must insert N > 2"));
s=concat(s,N);
s=concat(s,",");
i=1;
while( N != 2,
        i++;
        A=factor(N);
        if(length(A)>=2 & A[1,1] != 2,
           c=random(N-1);
           if( c < 2, c=2;);
           print(c);
           N=A[1,1]*c;
           if( N > Np,
             Np = N;
             pos = i;
           );
           s=concat(s,N);
           s=concat(s,",");
        );
        if( A[1,1] == 2,
            N = A[1,1];
            s=concat(s,N);
        );
);
r = pos/i * 1.0;
print("Max = ", Np);
print("r   = ", r*100);
print(s);
return;
}
Alcuni risultati:

? Shrimp(23)
23,207,492,2

? Shrimp(27)
27,63,168,2

? Shrimp(31)
31,837,192,2

? Shrimp(313)
313,35369,2581824,2

? Shrimp(723421)
723421,248066124847,1068167619936,2

? Shrimp(723421345678)
723421345678,2

Apparentemente si ferma subito.
Eccovi un altro esempio col 31, lanciato almeno due-tre volte (cambia il c randomico che faccio stampare prima di mostrare la sequenza numerica):
? Shrimp(31)
19
273
2357
451
1051
1225
1963
4365
11029
1657
211
396
31,589,5187,7071,1353,3153,3675,5889,13095,33087,4971,633,1188,2
? Shrimp(31)
11
128
31,341,1408,2
? Shrimp(31)
27
206
31,837,618,2

Anche qui apparentemente sembra esistere una "congettura del Massimo dello Shrimp Factored": il massimo si presenta sempre con una posizione non inferiore al 66,67%. Invece il contro-esempio:

? Shrimp(511)
493
105
396
Max = 3451
r   = 40.00000000000000000000000000
511,3451,735,1188,2

Si può avere meno del 40%?

Se avete una dimostrazione ai vari quesiti, fatemi sapere.

Alla prox

I Simpson e le approssimazioni matematiche

2011-01-30T23:15:00.000-08:00

Se per un attimo le calcolatrici si usano senza tener presente delle approssimazioni che introducono, si può incappare in qualcosa che sembra il contro-esempio per un Teorema famoso.

Prendiamo l' "Ultimo Teorema di Fermat" dimostrato da Wiles.

Nei cartoni de “I Simpson“, gli sceneggiatori nell'episodio “La paura fa novanta VI” ambientano Homer Simpson dal mondo bidimensionale dei cartoni animati ad uno spazio cartesiano virtuale in tre dimensioni dove si possono cogliere di sfuggita delle formule estremamente complesse come per esempio:

1782^12 + 1841^12 = 1922^12

Se questa equazione fosse vera, il Teorema di Fermat verrebbe smentito. Calcolatrice alla mano, l’equazione torna. Com’è possibile? Ok. Contate un attimo le cifre che può rappresentare la calcolatrice. Sicuramente sono dieci.

Se infatti scegliessimo una calcolatrice con un display di almeno tredici cifre ci renderemmo subito conto che
l’equazione scritta sopra non è corretta.

Gli sceneggiatori hanno avuto nel cartone l'aiuto di David Cohen, laureato in fisica ad Harvard e con un master in informatica teorica a Berkeley. Cohen per ottenere la relazione ha scritto apposta un software per ricavare le “quasi soluzioni” del teorema di Fermat.

Gli sceneggiatori hanno ripetuto l'esperimento nell’episodio “L’inventore di Springfield”. Qui Homer, con tanto di occhiali per assumere un apsetto da professore, scrive alla lavagna la seguente equazione:

3987^12 + 4365^12 = 4472^12

Qua quanto deve essere il display per accorgersi dell'errore?

Bubbole matematiche divertenti, che hanno incuriosito mezzo mondo!

Alla prox

L'equazione funzionale della zeta di Riemann

2011-01-30T00:16:00.000-08:00

Un tema affascinante nel campo complesso è ancor oggi costituito dalla zeta di Riemann e dalle sue due ultime congetture, che resistono come ultimo baluardo della matematica dell'Ottocento.

Chiunque abbia in qualche modo affrontato lo studio di tale argomento si sarà posto almeno un paio di domande come: “da dove nasce l’equazione funzionale?” oppure “perché i numeri primi sono legati agli zeri della zeta di Riemann?”.

La difficoltà di svelare gli ultimi misteri della zeta di Riemann, per una sua dimostrazione definitiva con strumenti di matematica analitica, sono spesso legati all'impenetrabilità dell'equazione funzionale, sotto certi aspetti complicata come dimostrazione, e che da una visione a "tutto tondo" non fornendo elementi ulteriori che possano portare a contraddizioni dimostrative.

Nel 1986 Titchmarsh col suo libro, mostrò ben sette tecniche per dimostrare l’equazione funzionale.

Un breve articolo su una semplice dimostrazione dell'equazione funzionale è al link di www.scribd.com/rosario_turco

http://www.scribd.com/doc/47783422/Equazione-funzionale-della-zeta-di-Riemann

Tale dimostrazione, una delle sette di Tichmarsh, mette in evidenza la “natura frazionaria” insita nella zeta di Riemann, il suo legame con i numeri primi e rappresenta essa stessa una ulteriore strada in cui emerge la stessa zeta.

Buona lettura
Alla prox

I numeri primi e i numeri Gaussiani primi

2011-01-18T11:40:00.000-08:00

Una delle cose che, forse, non tutti sanno è che risulta possibile estendere nel piano di Argand, noto anche come piano di Gauss, il concetto di numero primo ed è possibile farlo per diverse altre proprietà dei numeri. Passare da una dimensione a due dimensioni dei numeri complessi è inizialmente un gioco che porta a molte riflessioni e alla nascita di tecniche nuove.

I numeri nel piano complesso sono definiti numeri di Gauss interi oppure numeri di Gauss primi. Nel mondo dei numeri interi, compreso i negativi, sappiamo trattare facilmente i numeri primi e la fattorizzazione.

Alcuni elementi semplici del mondo degli interi ad "una dimensione" sono ad esempio:
1) Un numero è primo se divisibile per 1 e sè stesso.
2) i numeri primi appartengono sia alla forma 4n+1 che 4n+3
3) la scomposizione di un numero è univoca

Se passiamo un attimo al mondo dei numeri complessi, vediamo che si perdono alcune delle tre proprietà di sopra. Prendiamo un numero primo, ad esempio il 2. Il 2 è fattorizzabile, nel piano di Gauss; quindi, non è primo; difatti (1+i)(1-i)=2. Mentre numeri di Gauss primi sono ovviamente 1-i e 1+i. Eppure il 2 nel mondo degli interi era primo. Stessa cosa accade al 5 il 13 e il 17. Chi mi sa trovare altri? E' facile.

La 2) è vera solo per i numeri di forma 4n+3. I numeri 4n+1 non sono numeri di Gauss primi.

La divisione per 4 è, quindi, un utile tool di verifica se il numero può essere un numero di Gauss primo. Quelli di forma 4n+1 sono numeri di Gauss interi perchè possono essere splittati, fattorizzati o scomposti in numeri di Gauss primi.

Non solo, ma i numeri interi (non quelli di Gauss) splittabili hanno la proprietà (dovuta a Pitagora) di essere
esprimibili come somma di quadrati di due interi. Ad esempio 5 = 1 + 4, 13 = 4 + 9, etc.

I numeri immaginari escono fuori anche dalle soluzioni delle equazioni quadratiche, cubiche etc. avendo ammesso che i^2 = -1, cosa che non piaceva a Kronecker, il quale affermava: "Dio ha creato i numeri naturali, l'uomo ha fatto il resto".

D'altra parte i numeri immaginari iniziano possono far capolino anche nell'Ultimo Teorema di Fermat che sostiene correttamente (dimostrazione di Andrew Wiles) che il cubo di un intero qualsiasi non è mai somma di due cubi interi.

Se aggiungiamo i numeri razionali compresi dai numeri complessi è evidente che si perde anche la proprietà 3). Ad esempio prendiamo 6: Nel mondo degli interi -6=-2*3. Nel mondo dei numeri di Gauss possiamo avere che:
-6=(1 + sqrt(-5))(-1+sqrt(-5))
e inoltre è anche
- 6 = -2*3

Adesso la fattorizzazione non è unica, anzi un numero potrebbe essere splittato in vari modi.

In seguito a questo Eduard Kummer introdusse la "teoria dei numeri ideali", per giustificare situazioni come questa e per sostenere settori della Fisica, come la teoria quantistica. Per la verità furono introdotti inizialmente per attaccare l'Ultimo Teorema di Fermat facendo nascere quella che fu detta la teoria dei
numeri algebrica.

I settori di sopra attualmente sono meno "presidiati" e offrono ancora tante altre opportunità. Penso, ad esempio, che esistono molte proprietà della teoria dei numeri (proprietà dei vari tipi di numeri) da verificare anche tra i numeri Gaussiani e gli ideali ...

Grossi e ulteriori sostenitori di questi settori della matematica furono Dedekind (allievo di Gauss), Dirichlet e
Riemann (allievo di Dirichlet).

Parafrasando Einstein, mi piace concludere questa semplice panoramica, osservando che spesso "I problemi hanno soluzioni il cui livello di pensiero è totalmente diverso da quello che ha fatto nascere il problema", ma
aggiungo che esistono anche molte soluzioni alla ricerca del problema giusto.

Alla prox

Algoritmi di Page Ranking

2011-01-11T13:34:00.000-08:00

Come funziona un motore di ricerca per cercare le pagine più attinenti? Qual è l'attuale matematica che c'è dietro?

Il page rank è calcolato in base alla importanza della pagina. Ma come si deve definire l'importanza di una pagina?

Ci possono essere vari modi:
1) in base al numero di volte che la parola compare
2) in base al numero di link che da essa partono
3) in base al numero di link che ad essa arrivano
4) in base al numero di pagine valutate importanti che puntano alla pagina

L'idea di Brin e Page di Google è legata proprio al quarto punto di sopra, che offre maggiori risultati.

Il concetto è semplice: una pagina è importante per le pagine importanti che vi puntano e non tanto per una parola, magari presente una sola volta, e da noi ricercata. Una pagina importante, quindi, da valore ad una pagina a cui punta; per cui l'importanza di una pagina è la somma delle frazioni di importanza che le trasferiscono le pagine che ad esso puntano.

Supponiamo di numerare le pagine web da 1 a n. Avremo una matrice di connettività H (nxn), dove hij è l'elemento generico della matrice H, di riga i e colonna j . Ora hij=1 se esiste un link dalla pagina i alla pagina j; mentre hij=0 se non esiste il link e se i=j hii=0 perchè una pagina non punta a sè stessa. Supponiamo n=4, ovvero 4 pagine web.

Una matrice H potrebbe ad esempio avere:
h11=0    h12=1    h13=1    h14=1
h21=1    h22=0    h23=0    h24=1
h31=0    h32=0    h33=0    h34=1
h41=0    h42=1    h43=1    h44=0

Se sommiamo gli 1 su una riga otteniamo ri, cioè il numero di link (che è un dato noto). Chiamiamo con xj l'importanza della pagina; per cui è:

xj = h1j * x1/r1 + h2j * x2/r2 + ... + hnj * xn/rn per j=1..n   (1)

La (1) è un sistema di equazioni lineare in n incognite xi che rappresentano l'importanza delle pagine. Google usa una equazione leggermente differente:

xj = d(h1j * x1/r1 + h2j * x2/r2 + ... + hnj * xn/rn) * 1/n * (1-d) per j=1..n   (2)

dove d è un parametro nell'intervallo (0,1); di solito si usa d=0,85. Ora un metodo di soluzione come quello di eliminazione di Gauss ha una complessità O(n^3). Se n è molto grande, la soluzione del sistema di equazioni potrebbe richiedere miliardi di anni.

Come allora avviene, visto che i motori di ricerca lo fanno? Sono stati implementati algoritmi veloci e se ne stanno cercando ancora ulteriori.

Si usa un metodo iterativo di convergenza:
1) Si fissano inizialmente dei valori qualsiasi agli xi di destra per ottenere xj di sinistra nella (2),
2) Si ripete il passo 1 stavolta col valore xj trovato mettendolo a destra della (2) e, per successive approssimazioni (ripetendo i passi 1 e 2), si converge alla soluzione finale xi(1), xi(2), ..., xi(k) -> xj

Questa è una tecnica usata anche per lo studio dei campi elettrici, magnetici etc.

L'errore che si commette e(k) = max|xi(k) - xi| ed è tale che: e(k) <= lambda(k)   0 < lambda < 1
Purtroppo più grande è d nella (2) più lambda è grande e più lenta è la convergenza. La (2) ha anche una sua giustificazione probabilistica; xj rappresenta la probabilità che una pagina venga visitata ritenendo equiprobabili i link che una persona sceglie sulla pagina: d è la probabilità che la persona scelga un link offerto dalla pagina e 1-d se ne sceglie un altro.

Dietro a tutto questo c' è la teoria delle catene di Markov e delle matrici non negative che forniscono
l'esistenza e l'unicità della soluzione xj.

Oggi allo studio ci sono molti altri problemi importantissimi:
- trovare metodi più veloci affinchè le successioni convergano più velocemente

successioni di Krylov
metodi del gradiente o delle differenze finite
etc

- studiare modelli più complessi dove non c'è l'equiprobabilità
- studiare i valori migliori assumibili da lambda

Alla prox

Fisica alla ricerca di una Matematica applicata

2011-01-02T00:11:00.000-08:00

Spesso leggendo o studiando problemi di Fisica moderna, come la teoria delle stringhe o altre nuove, ci si rende conto che la matematica che dovrebbe creare l'impalcatura teorica a sostegno o a demolizione spesso è vecchia o molto complessa.

In altri termini il nostro progresso teorico e tecnologico è fortemente legato al progresso della matematica o alle ricerche che si fanno in suo ambito. Spesso la teoria matematica è molto complessa e ci si chiede se la Natura, che ama le semplificazioni, possa realmente seguire ragionamenti complessi oppure si è spinti a voler comprendere quali sono i suoi "pregiudizi" che gli permettono di fare percorsi semplificati in una teoria tanto complessa.

Prendiamo l'esempio della teoria delle stringhe e delle simmetrie.

La teoria matematica di queste cose, nei suoi mattoncini elementari, sono partite nel 1801 con Jean-Robert Argand, che formalizzò il concetto di piano di Argand e dei numeri complessi a+ib.

Con essi fu evidente che si ottenevano rotazioni di 90° nel piano o in 2D e che l'operazione moltiplicazione fosse commutativa; difatti se i^2=-1 era:

1 * i^0 = 1
1 * i = i
i * i = -1
i^2 * i = -i
i^3 * i = 1

Nel 1843 a William Rowan Hamilton venne l'idea di simmetrie in 3D ponendo:

i^2 = j^2 = k^2 = i * j * k = -1

Nacquero i numeri quaternioni a+ib+cj+dk, con cui però si perdeva la proprietà commutativa della moltiplicazione.

D'altra parte questa fatto in termini di simmetria è giustificato; difatti se si fa una rotazione in un piano di un
pentagono e una riflessione nella terza dimensione il risultato è diverso dal fare prima una riflessione nel piano e poi una rotazione nella terza dimensione.

Con Arthur Caley nel 1845 si arrivò agli ottetti o ottenioni indicati con 7 lettere e1..e7 e qui si perde anche la
proprietà associativa.

Sempre nell'Ottocento abbiamo i sedenioni a 16 unità. Con queste teoria si arriva a comprende varie proprietà della Teoria delle stringhe e anche altro; soprattutto si inizia a comprendere un mondo a N-dimensioni.

La Fisica del 21esimo secolo è ancora basata su Matematica dell'Ottocento e di inizio Novecento.

Avete mai provato a studiarla, per trarne qualche idea in fisica? Diversi articoli di fisica basati su essi sono presenti sia su Rudi Mathematici che sull Gruppo Eratostene.

Alla prox.

Due buone idee per un "regalo non impegnativo" ad un matematico ...

2010-12-29T04:47:00.000-08:00

Se siete appassionati di giochi matematici tridimensionali, vi consiglio di leggere questa pagina di Wikipedia: è fatta apposta per voi per introdurvi a tale "dimensione": http://it.wikipedia.org/wiki/Utente:DBC/Twisty_puzzle

I twisty puzzle sono poliedri magici o puzzle matematici: ne esistono un sacco. Alcuni noti come il cubo di Rubik, il Sudoku-cube e altri meno noti, ma bellissimi. Hanno un fondamento matematico, ma a che servono?

Se ci pensate Platone iniziò con i solidi platonici per filosofia, poi sono serviti come diletto (esistono i campionati del mondo del cubo di Rubik ad esempio), alcuni sono serviti come modellini per tecniche di imballaggio o come infrastrutture, alcuni sono nati dal mondo dell'arte.

Oppure provate a leggere un vecchio libro italiano del 1913 di Italo Ghersi, ormai alla quinta edizione "Matematica dilettevole e curiosa".

Tratta di tutto: Problemi bizzarri - Paradossi algebrici e meccanici - Moto perpetuo - Grandi numeri - Curve e loro tracciamento meccanico - Sistemi articolati - Quadratura del circolo - Trisezione dell'angolo - Duplicazione del cubo - Geometria della riga e del compasso - Rompicapo geometrici - Iperspazio - Probabilità - Giochi - Quadrati - Poligoni e poliedri magici.

Due buone idee per un regalo ...

Per chi è interessato anche all'esistenza di ipercubi magici, ebbene esistono.

Un ipercubo magico perfetto è stato costruito da J. Hendricks, nel 1999. E’ di ordine 16 e la somma costante è 524296.

Un articolo sulla storia e l'attualità delle figure geometriche magiche per diletto lo troverete a http://areeweb.polito.it/didattica/polymath/htmlS/Interventi/Articoli/AvventuraCubi/AvventuraCubi.htm

Un settore nuovo, che rappresenta un nuovo filone di lavoro, è quello di ideare nuovi imballaggi ecologici e a basso costo, con tutto quello che usiamo per vivere ogni giorno, per ridurre alla fonte (la fonte di produzione dei beni) la quantità di rifiuti non riciclabili o comunque non costituenti l'umido. Gli imballaggi ecologici dovrebbero avere i seguenti requisiti minimi:

essere fatti con materiale riciclabile
non essere costituiti da differenti materiali da differenziare in modo diverso perchè potrebbero causare dubbi o errori sul dove buttarli (indifferenziata, plastica-cartone, ...). Ad esempio lo sapevate che le posate di plastica, i bicchieri e i piatti non vanno nella plastica ma nell'indifferenziata? La carta o il catone sporco di salsa non può essere messo nella carta o cartone? Lo scontrino è carta particolare e non si può riciclare nella carta
essere di basso costo
essere tali da poterli ridurre facilmente di volume dopo l'acquisto
essere igienici e non nocivi
essere tali da rendere minimo lo spazio di intramezzo non utilizzato nel caso di accumulo in un deposito

In pratica vanno riprogettati su tutti i prodotti oggi noti ...

Alla prox

Natale e la stella cometa

2010-12-27T05:46:00.000-08:00

L'atmosfera natalizia ad un matematico fa venire in mente almeno due cose:

i comet diagram, come quelli della congettura di Goldbach, di Riemann etc
le stelle magiche

Una stella magica è un poligono stellato a n punte, con n maggiore di 5, avente come simbolo di Shläfli {n/2} con gli n vertici e le n intersezioni degli n lati munite di 2n interi tale che le somme dei 4 numeri su ciascun lato coincidano. Il valore di queste somme si dice costante magica o somma magica della stella.

Si dice inoltre stella magica normale una tale configurazione che sia munita degli interi consecutivi da
1 a 2n.

La somma magica delle stelle magiche ad n punte è Mn = 1/n[2*2n(2n+1)/2]=4n+2. Quindi sono legate ai numeri triangolari 2n(2n+1)/2.

Si dimostra che non esistono poligoni stellati con meno di 5 punte. Le stelle magiche più ridotte hanno 6 punte.

In figura alcuni esempi: esagramma magico (somma 24), ettagramma magico (somma 30), ottogramma magico (somma 34) etc.

Stelle mod n

Un'altra categoria interessante sono le stelle mod n. Ad esempio una stella a 6 punte con la distribuzione circolare dei numeri interi da 1 mod 6 a n mod 6 individua i numeri primi incolonnati però nelle punte della stella secondo il resto della divisione x/i mod 6. In pratica si ottiene la spirale di Ulam, se si usa mod 6.

Un articolo sulla spirale di Ulam a tal proposito è su http://eprints.bice.rm.cnr.it/513/1/ULAMSEGR.pdf

Tutti gli articoli dell'autore si trovano su:
http://www.gruppoeratostene.com/articoli/articoli.htm
http://www.rudimathematici.com/blocknotes.htm
http://rudimatematici-lescienze.blogautore.espresso.repubblica.it/2010/12/19/colpo-grosso-alla-regence/
http://www.scribd.com/rosario_turco

Metodi di generazione dei numeri di Smith

2010-12-18T09:53:00.000-08:00

S è un numero di Smith se considerando con T la somma dei digit di S, con F la somma della lista dei fattori di S, allora F è uguale a T.

Esempio 729
T=18
S=3^6=3*3*3*3*3*3
F=3+3+3+3+3+3=18
F=T
S è un numero di Smith.

Nella base 10, i primi numeri di Smith sono

4, 22, 27, 58, 85,   94, 121, 166, 202, 265, 274, 319, 346, 355, 378,   382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, ... (Sequenza A006753 dell'OEIS)

Metodi per generare i numeri di Smith
1.mo metodo

Se p è un primo Repunit allora posso generare numero di Smith con la moltiplicazione S=k*p dove k può assumere ad esempio uno dei seguenti valori: 1.540, 1.720, 2.170, 2.440, 3.304, 5.590, 6.040,
7.930, 8.344, 8.470, 8.920, 23.590, 24.490, 25.228, 29.080, 31.528, 31.780, 33.544, 34.390, 35.380.

Alcuni esempi:

R(2)=11
S=3304*R(2)=36344
T=3+6+3+4+4=2+0=2
L=2^3*7*11*59
F=2+2+2+7+11+59=24+59=8+3=1+1=2
-->Si Notare che il repunit primo appare anche nella scomposizione

R(3)=111
S=3304*R(3)=366744
T=3+6+6+7+4+4=30=3
S=2^3*3*7*37*59
F=2+2+2+3+7+37+59=16+37+59=112=1+1+2=4
-->No

R(19)
S=3671111111111111110744
T=3+6+7+15+15=16+15+15=46=4+6=1
S=2^3*7*59*1111111111111111111
F=2+2+2+7+59+19=13+59+19=91=9+1=1
-->Si Notare che il repunit primo appare anche nella scomposizione

I numeri di Smith di questa formas sono, quindi, legati ai numeri Repunit primi.

2.do metodo
Nel 1984, Pat Costello generò numeri di Smith con la formula P*Q*10^M dove P è un piccolo primo e Q è un numero primo di Mersenne noto.  Come si deve scegliere M nella formula P*Q*10^M?

Un metodo è il seguente:
a) Si sceglie il numero primo di Mersenne e si calcola la somma dei suoi digit
b) Si un numero primo piccolo P e si fanno i seguenti passi:
    b1) si calcola ps = somma dei digit di Q + la somma dei digit di P;
    b2) si calcola il prodotto P*Q;
    b3) si calcola ds = somama dei digit di P*Q;
          se ds<ps, si torna a b) e si sceglie un nuovo P;
          se ds=ps, allora P*Q è un numero di Smith;
          se ds>ps, allora si calcola (ds-ps) mod 7;
                    se (ds-ps) mod 7 = 0 allora M = (ds-ps)/7 e P*Q*10^M è un numero di Smith
                    altrimenti si torna a b) e si sceglie un nuovo P.
Esempio:
      Scegliamo Q = 2^17-1 = 131071 scegliamo P = 5011.
      ps = 20.
      P*Q = 656796781.
      ds = 55.
      ds-ps = 35 divisibile per 7. M=35/7=5.
      P*Q*10^5 = 65679678100000 è un numero di Smith secondo la definizione iniziale

Costello individuò 65 numeri di Smith in questo modo, incluso uno da record:
191*(2^216091-1)*10^266 con 65319 digit.

3.zo metodo
Nel 1987, Wayne McDaniel generalizzò il concetto di numeri di Smith e introdusse i k-Smith numbers e provò che sono infiniti. Con k=1 ci si riduce ai numeri di Smith, allora anche i numeri di Smith sono infiniti.

McDaniel generò i numeri di Smith della forma t*9Rn*10^M dove t è nell'insieme {2, 3, 4, 5, 7, 8, 15}, con Rn repunit primo.

4.to metodo
Dovuto a Yates.Di forma 9Rn*QS*10^M con Rn repunit primo e Q un primo palindromo di forma
10^2K +A*10K + 1.

Si suppone che esistono molte altre forme generatrici di numeri di Smith.

Tuttavia è bene sottolineare che alcuni numeri possono avere più proprietà, ad esmpio è possibile trovare un numero di Fibonacci Smith e così via. Esistono i numeri di Smith palindromi, fratelli etc (http://it.wikipedia.org/wiki/Numero_di_Smith)

L'utilità dei numeri di Smith? Si può cercare di appoggiarsi ad essi per semplificare la primalità di un altro tipo di numero. Ad esempio abbiamo visto che i numeri di Smith sono composti, ma legati ai Mersenne primi o a Repunit primi. Questo vuol dire che se si crea un algoritmo con cui generare un numero di Smith di una certa forma, allora si potrebbe risalire ad un Mersenne primo o a un Repunit primo.

P.S: Se usate la forma S=K*p vi renderete conto che avrete bisogno della fattorizzazione di S, che è lenta; oppure di sapere dato un p se esso è un fattore primo di S senza fattorizzare S (problema oggi non risolto).

Alla prox

Articoli informatici

2010-12-11T00:58:00.000-08:00

Oltre che interessarmi per hobby di Matematica e Fisica, il mio lavoro professionale è svolto nell'ambito progettazione di sistemi software (HW, prodotti, Architetture, progettazione SW) e spesso mi diletto anche a scrivere articoli di progettazione UML, Object Oriented, Framework, processi produttivi software (RUP, XP) e i principi di base: riusabilità, refactoring, etc.

Per chi fosse interessato a seguire tali articoli sono disponibili su SCRIBD
(http://www.scribd.com/rosario_turco).

Ve ne segnalo solo alcuni:

Principi di base
http://www.scribd.com/doc/45083638/oobase

http://www.scribd.com/doc/45083753/Principi
http://www.scribd.com/doc/45083533/Re-Factoring
http://www.scribd.com/doc/45083503/riuso

http://www.scribd.com/doc/45083402/Usa-Bi-Lit-A

Progettazione UML
http://www.scribd.com/doc/45083368/colori
http://www.scribd.com/doc/45083901/Business

http://www.scribd.com/doc/45083612/esempiuml

Design Pattern
http://www.scribd.com/doc/45083152/OO-Design-Pattern-e-Book

Processi produttivi
http://www.scribd.com/doc/45083287/Extreme
http://www.scribd.com/doc/45083473/Rup

Framework
http://www.scribd.com/doc/45083575/Framework

Alla prox

Tools per Windows - Teoria dei Numeri

2010-11-20T04:43:00.000-08:00

Ok, ma chi non vuole fare il salto e provare la maggior potenza delle altre piattaforme e vuole mantenere i piedi per terra, su quella terra che meglio conosce? Ok, anche per Windows esistono gruppi o persone di tutto il mondo che si occupano di primalità, fattorizzazione, con tutta la teoria migliore possibile: curve ellittiche, Sieve etc.

Alcuni link, veramenti importanti sono:
- http://www.ellipsa.eu/public/primo/primo.html - programma PRIMO
- http://gilchrist.ca/jeff/factoring/index.html- http://math.crg4.com/software.html

Qua basta scaricarsi le parti Windows, anche se esistono anche le versioni Linux/Unix.

Altri consigli sono al mio blog:
- http://mathbuildingblock.blogspot.com/2010/01/numeri-primi-tools-e-linguaggi.html

Alla prox

Piattaforma Linux per la teoria dei numeri

2010-11-20T03:27:00.000-08:00

Finora vi ho indicato molti strumenti per la Teoria dei numeri, ma un vero matematico che è anche un informatico/sperimentatore non può essere soddisfatto se non effettua il "salto" verso una piattaforma matematica completa, con tutti gli strumenti desiderati: C/C++/Java, Perl, GMP, PARI/GP, GP, ECPP, Maxima, Octave, Pari/GP, XAO e altro.

Occorre passare ad una "distro Linux" orientata alla Matematica (distro=distribuzione). Lo so si ha paura di partizionare Windows, fare il dual boot etc. Non occorre! Se sapete installare qualche programmino e volete anche un minimo osare, installiamo su Windows una macchina virtuale: VirtualBox http://www.virtualbox.org/wiki/Downloads

Scaricate la versione ultima per Windows x86/amd e installatela. Il sito è corredato di manuale ed esempi.
La VirtualBox vi consente di rimanere Windows e Linux indipendenti come ambienti. Qualsiasi cosa fate anche un danno, lo fate in un ambiente virtuale e non sul PC con Windows.

Gli sviluppatori conoscono VirtualBox perchè amano provare i propri programmi su più sistemi operativi pur possedendo un solo PC.

Poi vi consiglio come distro Linux matematica la "Knoppix Math" da scaricare da uno dei seguenti link:

- http://epidemiology.md.tsukuba.ac.jp/~mokada/R/knoppix/
- ftp://ftp.math.kobe-u.ac.jp/pub2/knoppix-math-cd/
- http://epidemiology.md.tsukuba.ac.jp/~mokada/R/

Scegliere l'ultima ISO dell'anno disponibile in versione inglese en (ufficialmente la distro di matematica è
giapponese). Ad esempio del 2010 usare: knoppix_v6.2.1-math-dvd-icms2010-20100730-en.iso

Sotto VirtualBox la ISO la si può caricare come CD-ROM virtuale (sempre configurando la VirtualBox) oppure la si può installare e poi configurare la VirtualBox per fare il boot da disco virtuale.

Per problemi e suggerimenti, conoscete la mia e-mail e potete contattarmi.

Alla prox

Calcoli mentali rapidi su grandi numeri

2010-11-18T00:21:00.000-08:00

Nella matematica si verificano spesso problematiche che confluiscono nel Teorema di Godel: una branchia matematica non è auto-dimostrante. Ad esempio proprietà dell'aritmetica non si riescono a dimostrare con l'aritmetica stessa e si deve ricorrere all'algebra, e questo è vero per ogni branchia e quando non esiste un settore o non è stato esplorato sufficientemente una congettura rimane un Teorema mancato, in attesa di nuovi strumenti matematici esistenti o da creare (magari anche il settore matematico è da creare). Esistono molte congetture, difatti, non ancora rigorosamente dimostrate, ma sono presenti moltissime evidenze sulla loro verità.

L'algebra ha un fascino enorme, perchè permette di manipolare espressioni e termini, equazioni, facendo apparire e sparire elementi fino ad arrivare ad una dimostrazione di verità o falsità.

Ad esempio il problema classico di Sophie Saint Germain di verificare se a^4 + 4 è composto, va affrontato con qualche passaggio del tipo:

a^4+4=a^4+4a^2+4-4a^2=(a^2+2)^2-(2a)^2=(a^2-2-2a)(a^2-2+2a)

In pratica appare il prodotto notevole, quindi a^4 + 4 è costituito sicuramente da due fattori, per cui è composto.

L'algebra ed il prodotto notevole sono spesso dietro a a calcoli mentali con numeri enormi, che non hanno nulla di prodigioso in chi lo esegue. Il fatto è che la maggioranza delle persone, anche il sottoscritto, tende a fare i calcoli con la moltiplicazione classica e gli occorre almeno carta e penna per disporre di una memoria tampone.

A tutti è noto però che esistono metodi mentali per approssimare rapidamente il calcolo e poi correggerlo. Un caso semplice a cui tutti ricorrono è nelle somme o nelle differenze; ad esempio con 112+231 è più facile fare 112+200=312 e poi correggere di 31 a 343.

Tecniche per le potenze
Con le potenze esistono diverse teniche per rendere rapido un calcolo con l'aiuto dell'algebra.

Tecnica 1 - adattare il calcolo ad un prodotto notevole del tipo:

   a^2 = a^2 - b^2 + b^2 = (a+b)(a-b)+b^2

Sopra (a+b)(a-b) è il prodotto notevole e b è il termine di aggiusto in modo che (a-b) oppure (a+b) sia un numero tondo e facile per fare i calcoli.

Tecnica 2 - regola del 5
Una seconda tecnica sulle potenze è osservare come termina il numero se per 5, allora si applica la regola del 5: Il quadrato di un numero che termina per 5 a5^2 = a*(a+1) concatenato con 25.

Vediamo alcuni esempi per le potenze:

1) 27^2

Qui è più facile aggiustare a 30

(27+3)(27-3)+3^2 = 30*24+9=3*10*24+9=3*240+9=3*200+40*3+9=600+120+9=729

2) 63^2

(63-3)(63+3)+3^2=6*10*66+9=6*660+9=3969

3) 35^2 = 1225

ricordando che 3*4=12 concatenando 25

4) 65^2 = 4225

5) 75^2 = 5625

Metodo generale per la moltiplicazione

Regola per a*b con a>b
Mettere il tutto nella forma (a+c)(b-c)+c*((a+c)-b)   con a>b facendo in modo che a+c diventi un numero semplice multiplo di 10 ad esempio o comunque facile da calcolare.

Esempio
997*986

997 è vicino a 1000 per cui pensiamo ad un (a+c) con c=3, mentre 986 è lontano di 14=(b-c) da 1000; per cui si può scrivere:

(997+3)*(986-3)+3*14=1000*983+3*14=983000+42=983042

Scorciatoie basate sul numero di cifre
Prima tecnica:
Se abbiamo due numeri di tre cifre abc*abd con cifra delle centinaia uguale e somma delle unità pari a 10 allora separiamo i calcoli ab*a(b+1) e c*d. Il risultato si ottiene concatenando le cifre ottenute.

Esempio
783*787
si moltiplica 78*79 col metodo precedente e 3*7=21.

Quindi 78*79=(79+21)(78-21)+21*22=100*57+22+440=5722+440=6162

per cui concatenando si ottiene che:

783*787=616221

Seconda tecnica:
usare un prodotto notevole osservando la distanza tra i due numeri e usando il numero medio

Esempio
783*787 = (785+2)(785-2)=785^2-4

Possiamo ora usare i metodi delle potenze precedenti (regola del 5), il riusultato esce da

78*79 concatenato a 25 quindi 616225, per cui

783*787 = (785+2)(785-2)=785^2-4=616221

Tecniche di predizione delle ultime cifre

Regole delle cifre 1,5,6
Sicuramente tutti abbiamo notato che se moltiplichiamo due numeri che hanno entrambi il 5 finale, il risultato avrà il 5 finale.
Questo accade anche per 1 e 6 (ovviamente dimostrabile).

Questo per dire che se vi chiedono l'ultima cifra di 3456^323342 è sicuramente 6, come per 345621^342 è 1 e per 815^723 è 5.

Regola del 25 e 76
Il prodotto di due numeri che terminano per 76 conterrà 76 alla fine e così per il 25.

Esempio
8176^2 = 66846976

3176 * 2576 = 8181376

Ma ne esistono anche tante altre regole: per la divisibilità, per dire le cifre decimali di una divisione etc.

Alla prox

La Matematica ed i giochi

2010-11-15T13:50:00.000-08:00

La matematica pone sfide a qualsiasi livello, scientifico e professionale, ma anche ludico e dilettevole. Spesso soluzioni di matematica dilettevole si trasformano, negli anni, in teoria apri-pista per i problemi professionali. Un esempio è stato il problema dei ponti di Konosberg di Eulero da cui poi è nata la Teoria dei grafi, la Topologia etc.

Dal diletto sono nati problemi, teoremi e teorie e così sarà anche in futuro. Nomi di esperti di matematica dilettevole potrebbero essere: Varahamihira, Narayana, Bachet de Meziriac, Fermat, La Hire, Eulero, Beniamino Franklin, Edouard Lucas, Jean Pierre Alem, Mariano Mataix,Googol, Yakov Perelman, Henrey Dudney, Martin Gardner. Ma sicuramente ne abbiamo tralasciati tanti altri altrettanto noti ed importanti: impossibile nominarli tutti.

Esaminiamo nel seguito un argomento di matematica che in Europa ha avuto radici nel Cinquecento: i quadrati magici. Hanno un fascino esoterico (citati anche nei libri di Dan Brown), un fascino particolare dovuto alla simmetria esistente in essi, fino ad esplodere nel Sudoku o nel tridimensionale gioco del cubo di Rubik. Chissà se qualcuno mostrerà qualcosa di analogo con un 'ipercubo magico'. In realtà la teoria dei quadrati magici risale al VI secolo con gli Indiani poi tramandata agli Arabi nel IX secolo.

I quadrati magici sono caratterizzati da innumerovoli proprietà a seconda del tipo di quadrato si considera; comunque le proprietà più semplici sono:
a) la somma delle diagonali o delle linee è sempre N, che è detto 'numero magico' del quadrato
b) Se il quadrato è nxn, N è la n-esima parte della somma di tutti i numeri del quadrato.
c) I numeri non sono ripetuti nel quadrato

Vediamo qualche problema.

Problema 1: Trovare N e K nel quadrato magico 3x3 ponendo k al centro e sapendo che esso è costituito
solo di numeri dal 10 al 18.

Supponiamo di avere un quadrato 3x3 come segue:

|a|b |c
| |K|
|d|e|f

Dall'algebra e dal numero N risulta allora che la somma delle diagonali è N e la somma di una traversa dall'alto in basso è N:

a+k+f=N
b+k+e=N
c+k+d=N

Se sommiamo le tre equazioni si ottiene che: (a+b+c)+3k+(d+e+f)=3N; però in un quadrato magico anche a+b+c=N e d+e+f=N per cui: k=N/3 o 3k=N. N è 1/3 della somma degli elementi da 10 a 18:

N = 1/3 (10+11+12+13+14+15+16+17+18)=42 e k=14.

Problema 2 - Quadrato dei primi: Completare il quadrato 3x3 seguente:

|67|    |43
|    |    |
|    |73|

Dal problema 1 abbiamo imparato che conviene mettere un k al centro e cercare di completare una riga o una diagonale:

|67|b |43
|    |k |
|    |73|

Qui deve essere: 67+b+43=b+k+73=3K   per cui b=1 e k=37 N=3k=111

Il quadrato magico per le ovvie differenze deve essere

|67|1 |43
|13|37|61
|31|73|7

Questo quadrato è dovuto a Dudney ed è detto "Quadrato dei primi" poichè è costituito da soli numeri primi.

Problema 3: Sudoku o Novenario. Trovare il numero magico N del Sudoku 3x3.

In un quadrato 3x3 del Sudoku la somma di tutti i numeri è quella da 1 a 9, per cui N=1/3(1+2+3+4+5+6+7+8+9)=45/3=15. Il k=N/3=5 può essere messa al centro del Sudoku.

Se poniamo in un angolo il 9 otteniamo:

|9 |   |
|   |5 |
|   | |1

Ma così possiamo avere una sola soluzione per ottenere N=15 in riga e colonna: 4,2; il che non va bene perchè sarebbe una ripetizione. Di conseguenza il 9 non può stare nei vertici. In tal caso abbiamo due 'soluzioni principali' e tutte le altre si ottengono ruotando il quadrato:

|4 |9 |2
|3 |5 |7
|8 |1 |6

|2 |9 |4
|7 |5 |3
|6 |1 |8

Il quadrato di Albrecht Durer

In un'opera esoterica di Albrecht Durer, "Melancholia" del 1514 c'era raffigurato un particolare quadrato magico 4x4.

|a|b |c |d
|e|x |y |f
|g|w|z |h
|i |j |k |l

Problema 4: Completiamo il quadrato di Albrecht Durer suppoenendo di avere:
|16| | |13
|    | | |
|    |6| |
|    | | |1

E' costituito da un quadrato interno x,y,w,z 2x2 e da una cornice esterna a,b,c,d,e,f,g,h,i,j,k,l. Le equazioni in gioco sono quindi:

a+x+z+l=N
b+x+w+j=N
c+y+z+k=N
d+y+w+i=N

Sommando le 4 equazioni otteniamo:
(a+b+c+d)+2(x+y+z+w)+(l+j+k+i)=4N poichè (a+b+c+d)=N e (l+j+k+i)=N allora è evidente che x+y+z+w=N (proprietà a)

Però è anche vero che se sommiamo solo
a+x+z+l=N
d+y+w+i=N

otteniamo che: (a+d+l+i)+(x+y+z+w)=2N quindi (a+d+l+i)=N cioè la somma degli angoli è pari a N (proprietà b).

Il quadrato gode della proprietà c che dividendolo in 4 quadrati alto a sinistra, basso a sinistra, alto a destra e
basso a destra la somma dei numeri è uguale a N. A questo punto possiamo abbozzare alla soluzione del problema:

1) Si suppone che il massimo numero è 16 e che il quadrato contenga da 1 a 16.
2) Questa volta il numero magico è 1/4 del totale dei 16 numeri (1..16) ovvero N=34.
3) per la proprietà b allora il numero all'angolo sinistro in basso è N-16-13-1=34-16-13-1=4.

|16| | |13
|    | | |
|    |6| |
| 4 | | |1

La diagonale si può completare N-13-6-4=34-23=11

|16| |    |13
|    | |11|
|    |6|    |
| 4 | |    |1

b,c possono essere solo 3,2 oppure 2,3 perchè la riga a+b+c+d=N

|16|3| 2 |13
|    | |11|
|    |6|    |
| 4 | |    |1

j e k possono essere solo 15,14 o 14,15 (Durer scelsa 15,14 così da avere la data 1514):

|16|3   | 2|13
|    |    |11|
|    |6 |    |
| 4 |15|14|1

A questo punto si riempe il quadrato interno facilmente

|16|3 | 2 |13
|    |10|11|
|    |6 | 7 |
| 4 |15|14|1

Alla fine è:

|16|3 | 2 |13
| 5 |10|11| 8
| 9 |6 | 7 |12
| 4 |15|14| 1

Ne esistono tante altre versioni:
- quadrato bimagico che è un quadrato che resta magico se si sostituiscono i suoi elementi con i i rispettivi
quadrati,
- quadrato trimagico, come prima ma con i cubi
- quadrato magico geometrico, dove i prodotti delle righe (non le somme), delle traverse e delle diagonali
sono uguali
- quadrati magici costituiti da lettere (il celebre SATOR rinvenuto negli scavi di Pompei del 79 d.c.)
- quadrato di 7, contenente i 49 iniziali numeri primi
- quadrati magici in base non decimale

Interessante è la trattazione su essi fatta da Jean-Pierre Alem nel suo "Giochi di ingegno e divertimenti matematici".

Sui quadrati magici se non si dispone di un metodo matematico, si possono perdere mesi prima di trovare la soluzione. Interessante è ovviamente il metodo per costruirli. Narayana, nel suo Ganida-Kamudi, illustrò un metodo di costruzione per i quadrati di lato 4n, 4n+-1, 4n+2. I 4n erano basati sulla mossa del cavallo degli scacchi. Per i primi due gruppi mostrò un criterio di costruzione per sovrapposizione di due quadrati (secoli dopo ripreso da La Hire).

Per i giochi matematici in generale vi consiglio anche Martin Gartner con il suo "Esperienza A-aH!" con cenni al "pensiero laterale", Edouard Lucas con "Il gioco militare" e "Il labirinto". Non sono da meno, per gli appassionati: Yakov Perelman con "Algebra ricreativa" tutto dedicato alla Teoria dei Numeri ed Hernry Dudeney col suo "L'enigma del mandarino".

Edouard Lucas nei suoi libri espone giochi famosi della sua epoca ma anche sue invenzioni: "La presa della bastiglia", la Torre di Hanoi, il gioco Paradoxal, il problema delle otto regine, problemi di Dama, gioco del Domino, problemi di giochi militari, problemi sui labirinti, problemi di teoria dei numeri etc.

Lucas ovviamente è famosissimo per i suoi enormi contributi alla Teoria dei Numeri (procedimento della sequenza di Lucas e vari Teoremi).

Il TRIS
Chi non ha mai giocato a TRIS? Si tratta di un quadrato 3x3 dove a turno ogni giocatore mette una 'x' oppure un cerchietto 'o' ad occupare le caselle.In esso vince chi riesce a mettere insieme tre simboli di fila in diagonale o lungo una traversa verticale o orizzontale. OK, il TRIS non ha niente di magico, ma capiremo con il gioco del quindici perchè l'ho introdotto.

La strategia da adottare nel TRIS è semplice. Si occupa quella casella che offre più potenziali tris successivi. Ad esempio se si occupa il centro ci sono 4 potenziali tris, se si occupa un angolo si hanno 3 potenziali tris.
Le risposte devono seguire lo stesso criterio. Se giocato in questo modo si giunge sempre alla patta, cioè il TRIS è un gioco a "somma zero" (Teoria dei giochi).

Un esempio di giocata è il seguente:
| |    |
|   |X |
|   |    |

|   |    |O
|   |X |
|   |    |

|    |    |O
|    |X |
|X |    |

|    |O |O
|    |X |
|X |    |

|X |O |O
|    |X |
|X |    |

Ha vinto il giocatore delle X. Se invece
|   |    |
|   |X |
|   |    |

|   |    |O
|   |X |
|   |    |

|    |    |O
|    |X |
|X |    |

|O |    |O
|    |X |
|X |    |

|O |X |O
|    |X |
|X |    |

|O |X |O
|    |X |
|X |O |

|O |X |O
|    |X |O
|X |O |

|O |X |O
|    |X |O
|X |O |X

Patta.

Il gioco del quindici

Supponiamo di avere una fila di 9 caselle in successione: due giocatori a turno devono mettere un numero in una posizione qualsiasi.Vince chi fa somma 15 per prima. Che strategia si adotta? Se non lo si sa si è notevolmente svantaggiati.

Lucas dimostrò che il gioco del 15 equivale ad un quadrato magico 3x3 con somma 15, da tenere a memoria:

|4 |9 |2
|3 |5 |7
|8 |1 |6

E la strategia di gioco da attuare? Quella del TRIS! La probabilità di vittoria è buona, se l'avversario ignora di dover giocare a TRIS su un quadrato magico, ma si arriva alla patta in caso contrario.

Alla prox

Le riduzioni dell'esponente - i conti della serva

2010-10-07T11:46:00.000-07:00

Abbiamo visto nei due blog precedenti il Piccolo Teorema di Fermat (PTF) e la generalizzazione di Eulero,
che qui riassumiamo brevemente:

a^n-1 mod n = 1 mod n (1)

a^phi(n) mod n = 1 mod n (2)

dove phi(n) è la funzione totiente di Eulero. Se p=n phi(n) = p-1 e la (2) e la (1) sono equivalenti. La funzione totiente phi(n) è l'insieme di numeri minori di n coprimi con n. Ad esempio phi(8) = 4, perchè i numeri minori di 8 e coprimi con esso sono: 1,3,5,7. Se n è un numero primo ad esempio phi(7) = 6; infatti coprimi con 7 sono: 1,2,3,4,5,6.

La cosa funziona sia con a e n coprimi che non. Se non sono coprimi, si parla di pseudo-primalità di n
rispetto alla base a.

Questo torna utile in vari tipi di problemi. Ad esempio se volessimo sapere qual è l'ultima cifra di 7^222?
Oppure ridurre l'esponente nel calcolo del modulo? Qua è importante che a e n siano coprimi.

Ora 7^222 mod 10 hanno 7 e 10 coprimi e phi(10)=4 {1,3,7,9}.
Dalla (2) allora è 7^4 mod 10 = 1 mod 10 (3).

Per cui tenendo conto della (3)
7^222 mod 10 = 7^4*55+2 mod 10 = 7^(4*55) * 7^2 mod 10 = 1^55 * 7^2 mod 10 = 9 mod 10

Questa tecnica funziona se a ed n sono coprimi e si ottiene elevando la base a al valore phi(n); difatti
se x = y mod phi(n) allora a^x = a^y mod n. Inoltre è quella più "rapida".

Cosa si risparmia? Facciamo il binary(x)

? binary(222)
%1 = [1, 1, 0, 1, 1, 1, 1, 0]
? binary(2)
%2 = [1, 0]

Si risparmia molto, ma è un metodo lento per il test di primalità; adesso vediamo perchè.

Prima beffa
Nel caso di 2^240 mod 241 = 1 mod 241 possiamo fare phi(241)=240 [qua già sappiamo che 241 è primo],
il problema è di avere una eulerphi() che deve fare il MCD (algoritmo di Euclide) di tutti i numeri tra 1 e 241, contando quelli che hanno MCD(x,241)=1. Se il numero è molto più grande di 241, il metodo è lento e richiede, tra l'altro, una pre-elaborazione per la riduzione.

Seconda beffa
Nella primalità quanto si risparmia in bit? nulla : 2^240 mod 241 = 2^240*1 mod 241.

Un'altra idea
L'idea allora è quella di ridurre l'esponente dividendolo per un divisore e trasformare il test:

a^n-1 mod n = 1 mod n

La relazione di sopra comporta che se n è il numero dispari sotto test, n-1 è un pari sicuramente divisibile per 2 ... Per grossi valori di n (n-1)/2 è intero; allora nel caso precedente avremo 2^120 mod 241. Ma quanto abbiamo risparmiato? Facciamo anche qui il binary(x)

? binary(240)
%9 = [1, 1, 1, 1, 0, 0, 0, 0]
? binary(120)
%10 = [1, 1, 1, 1, 0, 0, 0]

Si risparmia un solo bit!! Poco se vogliamo. Conviene quasi di lasciar fare al ModExp col numero integro.
La discussione dimostra in modo semplice, senza tirar fuori la teoria della complessità che la velocità non si ottiene dalla riduzione dell'esponente ma dal numero di step necessari all'operazione modulo. Inoltre il test di primalità se vuole diventare più veloce necessita di ridurre molto il numero di basi di prova.

Alla prox.

Miller-Rabin e i Numeri di Carmichael croce e delizia di Fermat

2010-10-06T14:32:00.000-07:00

Il Piccolo Teorema di Fermat (PTF), dovuto a Pierre de Fermat e dimostrato successivamente da Eulero ha un fascino inesauribile pur provenendo dal lontano Seicento. E' quasi sempre tirato in ballo, anche nei nuovi metodi di primalità come AKS etc.

Vediamo in che consiste.

PTF:
se a^n mod n = a mod n allora n è primo (1) o alternativamente
se a^n-1 mod n = 1 mod n allora n è primo. (2)

La versione di Eulero tiene conto della funzione totiente phi(n) per cui: a^phi(n) mod n = a mod n.

Pierre de Fermat all'epoca pensava al solo test 2^n mod n = 2 mod n, che se era verificato allora n era un numero primo.

Solo che ci si accorse presto che alcuni composti, detti 'numeri di Carmichael', superavano il test e per cui affinchè il PTF fosse valido l'idea fu quello di testare n per vari valori di a, almeno un centinaio. In tal modo, visto che i numeri di Carmichael tendono al crescere di n ad essere rarefatti e molto distanti,allora il test era ancora valido e forniva una pseudo-primalità a-SPRP, cioè n risulta 'molto probabilmente' primo, se ha superato il test (1) per 100 valori di a.

Se n molto è grande, testarne la primalità per 100 basi è un test troppo lento, anche se di solito siamo abituati, purtroppo, a lasciare lavorare i computer per diversi giorni.

L'obiettivo di chi fa tali attività è trovare scorciatoie, per cercare di ottenere la primalità con poche risorse macchina e con poco tempo. Il che è difficilissimo, in molti casi impossibile!

Però a pensarci, possiamo ideare insieme un metodo. Poi dopo vediamo quanto è veloce e con quale complessità (cercherò di non annoiarvi).

Il problema del PTF non è il PTF stesso ma i numeri di Carmichael. Una lista di numeri Carmichael
è presente a http://oeis.org/classic/A002997.

Il bello della faccenda che il PTF funziona bene alla rovescia: certifica con certezza i composti ma fornisce una pseudo-primalità per i primi! Ma questo è vero per tutti i test probabilistici (Miller-Rabin etc).

Le domande che ci si può porre sono:
1) Potremmo rendere l'algoritmo che si basa sul PTF un pò meno di pseudo-primalità?
2) Possiamo fare solo un paio di test?

Forse sì, forse no. Solo due test: uno che dovrebbe ridurre di parecchio il fatto che n sia un numero di Carmichael ed uno costituito dal PTF con a=2. Un sogno finora...

Il Teorema di Chernick dice che i numeri di Carmichael generici sono tali da avere una forma
(6k+1)*(12k+1)*(18k+1) con ogni fattore primo.

Un'idea semplice è allora scrivere in PARI/GP un Charmichael's Test:

/*
* Carmichael's test
*
*/
CT(number)= local(ret=0,x=0); {
/* Se lo trova esce 0 */
if( number == 561 | number == 1105, return(0););
trap( , return(1),
   x=solve(k=1,number,(6*k+1)*(12*k+1)*(18*k+1) - number);
   if(frac(x)!=0.0, ret=1); /* Only integer */
);
return(ret);
}

Fissato number l'idea è quella di risolvere una equazione cubica (6*k+1)*(12*k+1)*(18*k+1) - number = 0, se ha una soluzione intera abbiamo individuato un composto di Carmichael e sicuramente i tre fattori sono primi. E' stato introdotto il correttivo che l'equazione non individua cioè i due numeri 561 e 1105.

Purtroppo sono possibili forme di Carmichael anche a più di 3 fattori:
(7k+1)(8k+1)(11k+1)
(6k+1)(12k+1)(18k+1)(36k+1)
(18k+1)(36k+1)(108k+1)(162k+1)
(24k+1)(72k+1)(192k+1)(288k+1)
(60k+1)(90k+1)(300k+1)(450k+1)
(60k+1)(240k+1)(300k+1)(600k+1)
(42k+1)(252k+1)(588k+1)(882k+1)
etc.

Inoltre il test di sopra andrebbe male ad esempio con 885 (altra forma del tipo kl(n)+1), anch'esso numero di
Carmichael.

Versione generalizzata del Teorema di Chernick
Se un numero di Carmichael n è considerato nella sua forma canonica n = k lambda(n) + 1 e se qualche divisore d di k è tale che il numero   p = d l(n) + 1 sia primo, allora pn è un altro numero di Carmichael, dove lambda(n) è la funzione ridotta totiente, detta anche funzione lambda di Carmichael.

lambda(n) è il più piccolo intero positivo tale che x^m = 1 (mod n) per tutti gli x relativamente primi a n; in tal caso m=lambda(n); lambda(n) è anche l'esponente del gruppo moltiplicativo Zn.

La funzione lambda di Charmichael può essere calcolata nel seguente modo:
   lambda(1) = 1,
   lambda(2) = 1,
   lambda(2^2) = 2,
   lambda(2^e) = 2^(e-2) for e > 2,
   lambda(p^e) = (p-1)*p^(e-1) for p > 2 and prime,
   lambda(p[1]^e[1]*...*p[r]^e[r]) =
                   LCM[lambda(p[1]^e[1]),...,lambda(p[r]^e[r])],
                                                all p[i]'s prime.
LCM è il minimo comune multiplo.
Inoltre l(q) = phi(q) se q è una potenza di un primo.

Ad esempio:
   lambda(2^e*5^f) = 2^(e-2)*5^(f-1), e > 3.

Per valutare 9^170489 = a (mod 5000000), si puà calcolare nell'ordine

   9^2 = 81 (mod 5000000)
   9^4 = (9^2)^2 = 81^2 = 6561 (mod 5000000)
   9^5 = (9^4)*9 = 6561*9 = 59049 (mod 5000000)
   9^10 = (9^5)^2 = 59049^2 = 1784401 (mod 5000000)
   9^20 = (9^10)^2 = 1784401^2 = 1928801 (mod 5000000)
   9^40 = (9^20)^2 = 1928801^2 = ...
   9^41 = 9^40*9 = ...
   9^82 = (9^41)^2 = ...
   9^83 = ...
   9^166 = ...
   9^332 = ...
   9^664 = ...
   9^665 = ...
   9^1330 = ...
   9^1331 = ...
   9^2662 = ...
   9^2663 = ...
   9^5326 = ...
   9^5327 = ...
   9^10654 = ...
   9^10655 = ...
   9^21310 = ...
   9^21311 = ...
   9^42622 = ...
   9^85244 = ...
   9^170488 = ...
   9^170489 = ... = a (mod 5000000).

Ad ogni step si fa il quadrato dell'esponente (by squaring) oppure aggiungendo 1 ad esso (multiplying by 9). Ciò è relazionato alla espansione binaria di 170489. Possiamo ricordare tutti i numeri relativamente piccoli con la riduzione modulo 5000000 dopo ogni step.

Anzicchè usare il lambda(n), forse la tecnica di esponenziazione by squaring del blog precedente, simile, ma risulta più rapida.

Repunit
Se stiamo testando dei Repunit abbiamo meno problemi: un numero Repunit difficilmente è un numero di Carmichael! I repunit sono i numeri ottenibili ad esempio da (10^n-1)/9 e caratterizzati da tutti 1.

Ad esempio
(10^n - 1)/9 = (6*k+1)*(12*k+1)*(18*k+1) difficilmente ha soluzione intera.

Seppoi lo trovate il Repunit-Carmichael siete da record!

Quanto conta ridurre un esponente? Quasi sicuramente non serve. Si riduce di 1 bit o qualcosina di più.

Ma è più veloce:
2^a mod a = 2 mod a

piuttosto che
2^a-1 mod a = 1 mod a

o addirittura tecniche ulteriori di divisione di a-1 per fattori anche primi.

Quello che conta è, invece, il numero di operazioni impiegate per il ModExp. Più si riducono e più il software diventa veloce (Sapreste trovare un metodo più corto?).

Un altro Metodo simile
Nei primi 100 milioni di numeri ci sono solo 255 numeri di Carmichael e
più si va oltre e più si rerafanno. Solo che è stato dimostrato il Teorema:"I numeri di Carmichael sono infiniti." (Uffa!)

L'idea delle equazioni però è sempre alla base di queste cose ed ha fatto già accendere la lampadina a qualcun altro (gli americani la lampadina la chiamano quoziente intelletivo "ah!") : Miller-Rabin.

Se nella (2) poniamo che n-1= 2^t * u dove u è dispari e t>=1, allora la (2) è equivalente a:

(3) a^u*(2t) = mod n

In sostanza la (3) suggerisce di calcolare a^u mod n e poi di elevare il risultato al quadrato per t volte!

Inizialmente è:
x0 = a^u mod n
ad ogni step invece:
xi = xi-1^2 mod n

per cui alla fine abbiamo l'equazione xt^n-1 = 1 mod n (oppure -1 mod n)

Poichè l'unità mod n ha radici non banali se e solo se il numero non è un primo, allora è possibile creare una funzione witness(a,n) che se durante l'elevazione al quadrato trova una radice banale dell'unità modulo n allora restituisce subito 0, se non trova radici non banali restituisce alla fine 1. Si deve però provare con diverse basi tra 1 e n: per tutte deve essere verificato.

Vediamo come si comporta con un numero primo. Supponiamo che n=29 allora n-1 = 28 = 2^2 * 7.

Sia a=10. Qui 2^t=2^2 u=7, t=2 allora è:
x0 = 10^u mod n = 10^7 mod 29 = 17
x1 = x0^2 mod n = 17^2 mod 29 = 28
x2 = x1^2 mod n = 28^2 mod 29 = 1 STOP (la radice banale sintomo di primo!)

Sia a=2. Qui 2^t=2^2 u=7, t=2 allora è:
x0 = 2^u mod n = 2^7 mod 29 = 12
x1 = x0^2 mod n = 12^2 mod 29 = 28
x2 = x1^2 mod n = 28^2 mod 29 = 1 STOP (la radice banale sintomo di primo!)

Se si verifica tra 1 e n, è sempre lo stesso discorso. Quindi è primo.

Vediamo n=561 che è un numero di Carmichael, allora n-1 = 560 = 2^4 * 35. Supponiamo che la base scelta sia 2. Qui 2^t=2^4 u=35, t=4 allora è:

x0 = 2^u mod n = 2^35 mod 560 = 368
x1 = x0^2 mod n = 368^2 mod 560 = 464
x2 = x1^2 mod n = 464^2 mod 560 = 256
x3 = x2^2 mod n = 256^2 mod 560 = 16
x4 = x3^2 mod n = 16^2 mod 560 = 16

Se si ripete per a=10

x0 = 10^u mod n = 10^35 mod 560 = 320

x1 = x0^2 mod n = 320^2 mod 560 = 480
x2 = x1^2 mod n = 464^2 mod 560 = 240
x3 = x2^2 mod n = 256^2 mod 560 = 480
x4 = x3^2 mod n = 16^2 mod 560 = 240

Uhmmm ...

E' composto.

Quante basi?
Ce lo suggeriscono due teoremi

Teorema 1
Se n e' un numero dispari non primo, allora il numero di elementi per cui la funzione witness da esito positivo sono almeno (n−1)/2.

Teorema 2
Per ogni intero dispari n > 2 e per ogni intero positivo b (numero di base), la probabilità che Miller-Rabin(n,b) si sbagli è al massimo 2^−b.

Quindi la scelta di b >= 40 potrebbero essere sufficienti, grazie ad una probabilità migliore al solo PTF su 100 basi.

Riferimentihttp://www.numericana.com/answer/modular.htm#carmlarge
http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html

Il modulo: strumento per test di primalità e crittografia

2010-10-03T02:15:00.000-07:00

I test di primalità sono spesso una combinazione di due tecniche:
- evidenziano rapidamente se un numero è composto
- se non è composto devono avere un algoritmo rapido di primalità: deterministico (AKS, Lehmer, etc) o
probabilistico (Miller-Rabin, Fermat, etc)

Oggi la "grande sfida numerica" per gli sviluppatori, i matematici e chi si interessa di hardware per tali tipi di problemi (primalità), è realizzare hw e/o algoritmi più efficienti di quelli disponibili, anche attraverso lo sviluppo di nuovi Teoremi di Teoria dei numeri.

E' noto che per verificare la primalità di un numero primo o anche per generare le chiavi pubbliche e private
(vedi RSA) nella crittografia, si fa uso dell'operatore aritmetico modulo, che restituisce il resto della divisione intera.

Ad esempio nel Piccolo Teorema di Fermat è noto che "se a^p-1 mod p = 1 mod p allora p è primo. Per evitare i numeri di Carmichel si testa per diverse basi per cui si individua un numero che molto probabilmente è primo.

Il problema che nasce è che se p-1 è un numero molto elevato a^p-1 mod p richiede un tempo notevole di calcolo.

Per tale motivo si usano "tecniche di riduzione" per velocizzare il calcolo, effetto che si nota soprattutto se il numero è di "grandissime dimensioni".

Se ad esempio a=2345 b=2345678 c=341 allora a^b mod c si può sostituire con a^c mod b. Se questo è conveniente perchè adesso l'esponente è minore, col Piccolo Teorema di Fermat non è conveniente; difatti da a^p-1 mod p si passa a a^p mod p-1 come l'algoritmo che segue (ma abbiamo peggiorato le cose sostituendo p-1 con p):

/*
** Simple Method
*/
pMod(base,exponent,modulus)= local(ret=1); {
ret = lift(Mod(base, modulus)^exponent);
return(ret);
}

Un'altra possibilità, se l'esponente è troppo grande, in Mod(a,N)^n è di usare una riduazione del tipo Mod(n, phi(N)), dove phi(N) è la funzione totiente di Eulero.

Una modalità più efficiente è di lavorare con gli esponenti in binario ( tra l'altro sono possibili creazioni
di processori che lavorano in questo modo): tale tecnica è nota come "exponentiation squaring", proposta
da Bruce Schneier nel suo Applied Cryptography, 2e, ISBN 0471117099. Questo metodo richiede un tempo costante indipendente dall'input, si dice che è a complessità lineare.

/*
** Fast Mod Exp: exponentiation by squaring
**
** Concrete implementation by R. Turco
*/
ModExp(base,exponent, modulus) = local(ret=1,i=1); {
b = binary(exponent);
i = length(b);
while(exponent>0 & i>0,
        if(b[i]==1,
           ret = lift(Mod((ret * base), modulus));
        );
        exponent = exponent >> 1;
        base = lift(Mod((base * base), modulus));
        i--;
);
return(ret);
}

La tecnica mette insieme anche l'altra tecnica dello "Square e Multiply" che vediamo di seguito, anche questa con esponenziazione binaria:

/*
** Square & Multiply
**
*/
SqMod(base,exponent,modulus)= local(residue=1); {
b = binary(exponent);
len = length(b);
for(i=1,len,
      residue=(lift(Mod(residue,modulus)^2)*(base^b[i])) % modulus;
);
return(residue);

}

Lo square & multiply, usato nel RSA o altri come AES per le chiavi, potrebbe essere soggetto ad attacchi furbi per il crack delle chiavi stesse.

Esistono anche altri algoritmi basati sulla tecnica "Montgomery reduction" e varianti come la "Barrett’s reduction" che usano un pre-processing e che sono interessanti per la produzione di HW ad hoc (sia basati sul binario ma preferibilmente sulle word). La "Montgomery reduction" è possibile anche sulle curve ellittiche GF(2^k).

Riferimenti
http://en.wikipedia.org/wiki/Montgomery_reduction
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
http://en.wikipedia.org/wiki/RSA
http://www.it.uu.se/edu/course/homepage/security/vt09/labs/lab2

Propri lavori su tecniche di primalità
http://www.gruppoeratostene.com/articoli/PrimTech.pdf
http://www.gruppoeratostene.com/articoli/Rtc2009.pdf
http://www.gruppoeratostene.com/articoli/PDC.pdf
http://www.gruppoeratostene.com/articoli/Mersenne.pdf
http://www.gruppoeratostene.com/articoli/Rtac.pdf

Implementazioni Software
http://www.gruppoeratostene.com/programmi/programmi.htm

Prolog, Web Semantico e Social Network

2010-09-26T10:56:00.000-07:00

All'università e per scopi personali, per 3-4 anni ho sperimentato il Prolog. Tale linguaggio fa parte della famiglia dei linguaggi della Logical Programming, molto interessante e basato su predicati e clausule, con uno schema tipico Soggetto Predicato Valore.

Dopo una fase in cui il Prolog si era stagnato, ecco che i progetti Open Source tirano fuori dal cilindro
il pacchetto software SWI-PROLOG, dal nome dell'università di Amsterdam "Sociaal-Wetenschappelijke Informatica", e il cui autore principale è Jan Wielemaker (Vedi http://it.wikipedia.org/wiki/SWI-Prolog ).

L'importanza del SWI-Prolog e della sua ripresa risiede tutto dietro a 4 cose: il Web semantico e la Social Network Analysis, i motori di ricerca e la problematica del knowledge Management nelle aziende.

Il concetto è questo: "Se nel pubblicare su Web i dati, essi sono accompagnati da particolari metadati semantici che permettono di relazionare le informazioni e la loro rilevanza, allora successivamente è possibile studiare i grafi, statici e dinamici, che si formano a seguito delle relazioni di aggregazione stabilite naturalmente tra le persone e comprendere il loro comportamento. In tal modo si possono a scopo di marketing segmentare le persone, sui gusti etc e poter fare advertising mirato, pubblicità e offerte".

Il fine ultimo è la Social Network Analisys, analizzando i grafi e i "cluster di dati" che si formano, con algoritmi particolari (vedi l'articolo "Introduzione agli algoritmi di clustering http://www.gruppoeratostene.com/articoli/Algoritmi%20di%20clustering.pdf).

Per ottenere tali dati, il "trucco" è di offrire tools di aggregazione sociale: Facebook, Google, Twitter, etc. I vostri dati saranno valutati, verrete osservati come interagite nel gruppo, se siete dei leader, se siete l'anello di congiunzione tra più gruppi, se avete peso sugli altri, quanto interagite etc. (leggetevi cosa sono le Social Network e i grafi associati è interessante tutta la teoria, altrimenti suggeritemi cosa non avete ben compreso e proverò a spiegarvelo).

Ma per ottenere qualcosa di meglio non si può rinunciare al Web semantico: non basta HTML, XML etc. Si devono introdurre concetti di relazione e gli strumenti adatti a tale scopo discendono da concetti di Prolog: Soggetto Predicato Valore.
Ad esempio questo si può ottenere con tre risorse già esistenti: l'XML, gli URI e i namaspace ma in una forma più attinente. Difatti si usano:
- RDF (Resource Description Framework)
- N3 ed N3 con namespace (un miglioramento rispetto a RDF)
- OWL
- etc.

Se occorre aggiungere metadati in abbondanza, occorre anche produrre strumenti di produttività che possano snellire la fase di aggiunta dei metadati tra le pagine web o tra i Referee dei documenti scientifici o altro etc. In tal modo si avrà un web che "ragiona", che possa trovare cose attinenti con una maggiore precisione, distinguire se un riferimento è già stato trovato e presentato.

Si possono creare Page Searcher logici o meta-crowler logici (Meta-PrologCrowler) ed efficaci XML-PrologParser per rendere migliori i motori di ricerca attuali e far decollare il Knowledge Management.

A tal proposito si potranno creare anche Web server ad hoc, o aggiungere plug-in a quelli esistenti. Intanto sono nate librerie come PiLLoW per integrare la Logic Programming ed il WWW.

Comunque il prolog è efficace anche nell'analisi dei grafi (e non solo). Non ci credete? Installatevi SWI-Prolog e ricopiate il programmino che vi propongo (mettendolo in un file grafo.pl):

arco(a,b,5).
arco(b,c,5).
arco(c,d,7).
arco(d,a,4).
arco(b,d,9).
arco(d,e,5).
arco(a,e,7).
arco(c,e,8).

/* connessione a doppio senso di marcia */
andare(X,Y,K) :- arco(X,Y,K).
andare(X,Y,K) :- arco(Y,X,K).

/* raggiungibile con 1,2,3 passi */
raggiungibili(A,B) :- andare(A,B,_).
raggiungibili(A,B) :- andare(A,X,_), andare(X,B,_).
raggiungibili(A,Z) :- andare(A,X,_), andare(X,Y,_), andare(Y,Z,_).

/* raggiungibile con calcolo della LUNGHEZZA */
percorso1(A,Z,K) :- andare(A,Z,K).
percorso2(A,Z,K) :- andare(A,Z,K1), percorso1(X,Z,K2), K is K1+K2.
percorso3(A,Z,K) :- andare(A,Z,K1), percorso2(X,Z,K2), K is K1+K2.

A questo punto avviate SWI-Prolog. Fate: File->Consult->grafo.pl ed ora proviamo a fare delle domande.

Vogliamo sapere se esiste un percorso tra a e d (attenzione a digitare il punto che è importante).
percorso1(a,d,X).
X=4
La risposta è Sì: è a distanza 4

Vogliamo sapere se esistono altri percorsi tra a e d? digitiamo ";" ed esce false.

Proviamo:
percorso1(b,e,X).
false.

Proviamo:
percorso2(a,e,X).
X=12;
X=14;
X=15;
false.

Proviamo invece:
percorso3(a,e,X).
X = 17 ;
X = 19 ;
X = 20 ;
X = 19 ;
X = 21 ;
X = 22 ;
X = 20 ;
X = 22 ;
X = 23 ;
false.

Come si vede realizza anche una base dati di conoscenza tutto sommato, e potrebbe essere utile, questo esempio, per delle tabelle di routing di rete.

Alla prox.

Riferimenti
www.swi-prolog.org
http://it.wikipedia.org/wiki/Web_semantico

Schedulazioni vincenti e labirinti tenebrosi, con il bastone da maresciallo nello zaino ...

2010-09-25T07:27:00.000-07:00

Il vantaggio di usare strumenti LP è di astrarsi dalla programmazione software e concentrarsi solo sulla formulazione matematica. Ciò non toglie che si può programmare in progetti più grandi con C/C++/Java e librerie LP disponibili (come le API offerte da GNUWin32 o anche per Linux/Unix con l'uso di Database).

Vediamo un classico: dovete fare con Microsoft Project un diagramma di GANTT con risorse, task in cascata o parallelizzabile e le milestone con ogni opportuna data e descrizione; poi vi hanno richiesto il diagramma di Pert per comprendere i task critici. Sapete l'inizio e la fine desiderata, quanto serve per ogni attività, quante persone, ma occorre far entrare il tutto nel periodo richiesto. E' possibile o impossibile? Come e quali attività si devono parallelizzare? Quello ottenuto è il meglio possibile o esistono anche altre soluzioni?

Al di là di ulteriori elementi che dipendono dal tipo di lavoro in gioco, stiamo parlando di un problema di pianificazione o scheduling, che rientra tra i problemi NP-completi!

In sostanza le stesse informazioni accennate sopra, come barre nel GANTT e le timeline si possono tradurre in un grafo matematico dove i nodi possono essere i nomi dei task, gli archi orientati il cambio di sequenza da un task ad un altro (e la dipedendenza anche tra essi sequenziale), mentre i pesi sugli archi possono rappresentare il tempo necessario allo svolgimento del task. Nel grafo potremmo avere anche parallelizzazioni di task , cioè situazioni in cui da un nodo escono contemporaneamente più archi verso altri nodi.

Con un grafo, quindi, si possono formulare varie tipologie di problemi. Per grafo pesato orientato intendiamo
una struttura G(N, A), con N insieme dei nodi e cardinalità | N |, ed A insieme degli archi e cardinalità | A |.
L'insieme degli archi, A, è caratterizzato da un orientamento da nodo origine ad uno destinazione i,j.

In generale l'obiettivo di un "problema di scheduling" matematico è di ottimizzare una o più grandezze di
performance tra le seguenti:
- minimizzare la massima "lateness" o il massimo ritardo (non dite che ve l'ho detto io!)
- minimizzare i costi/tempi del setup
- minimizzare il "makespan" (la massima lunghezza temporale o l'elapsed time totale)

Per risolvere, nel miglior modo possibile, un tale problema sono possibili varie strategie:
1 - algoritmi tipici della teoria dello scheduling
2 - algoritmi legati ai grafi

Un algoritmo tipico della teoria dello scheduling è quello MST (Minimum Spanning Tree) o minimo albero ricoprente. Nel MST il problema è definito nel seguente modo: sia dato un grafo orientato pesato G(N, A), con un insieme di interi senza segno definito sugli archi, allora l'obiettivo è quello di determinare una struttura che connetta tutti i nodi del grafo con archi di peso minimo.

Un albero ricoprente di costo minimo è tipicamente una struttura con un unico nodo origine, detto radice, ed una serie di rami; il "cammino" da individuare è composto dall'insieme dei nodi in una sequenza tale che la somma dei pesi sui rami sia la minima possibile.

E' evidente che l'MST ci porta a minimizzare il "makespan". Poichè abbiamo a che fare con un grafo a numero di nodi fissi, (ricordate cosa abbiamo detto circa il problema di Steiner?) allora è possibile usare l'algoritmo di Kruskal (vi rimando al blog precedente per tale algoritmo).

Ma dobbiamo aprire una parentesi sui labirinti per comprendere il punto 2 precedente e concludere il discorso sullo scheduling. Quindi c'è un interrupt e salvate un attimo il contesto sullo stack.

Come vedremo le tecniche di ottimizzazione congiunte spesso vengono utilizzate per risolvere problemi complessi che non ricadono in una branca specifica dell'ottimizzazione.

Un tipico algoritmo per trattare i labirinti è l'algoritmo di Tremaux. Ne esistono anche altri per la robotica, euristici e random (vedi Wikipedia) ma qui è sufficiente quello classico.

L'algoritmo di Tremaux consiste nel seguire un percorso, scelto a caso all'interno del labirinto, fino a raggiungere un incrocio, marcando la via che è stata percorsa fino a quel momento (nel caso in cui il corridoio conduca a un vicolo cieco è necessario tornare indietro fino all'incrocio precedente, marcando la via all'andata e al ritorno).

Quando si giunge a un incrocio di più corridoi si prende preferibilmente una via che non è stata segnata come percorsa in precedenza, e se ciò non è possibile si prende una via percorsa una sola volta. In ogni caso non è permesso scegliere una via che è stata già marcata due volte. Iterando il procedimento per ogni incrocio che si trova sul proprio percorso, l'algoritmo permette di raggiungere l'uscita (o se il labirinto non ha altre uscite oltre a quella imboccata per entrare, di tornare all'entrata).

La "tecnica di backtracking" è una tecnica euristica generale utilizzabile nei grafi e negli alberi; serve a tracciarsi i percorsi e durante esso appena si ottiene una informazione che il cammino fatto è peggiore di un altro si scarta e si ritorna indietro per un ramo non percorso. Alla fine si rimane col miglior percorso tracciato.

Se ci riflettiamo, una pianificazione assomiglia un pò all'attraversamento di un labirinto, dove ci sono un ingresso/inizio ed una uscita/fine, e dove occorre scegliere i percorsi e marcandoli, in che direzione li percorriamo (grafo orientato) e se una o due volte.

Il percorso o cammino in effetti è l'insieme dei rami/task da scegliere da legare insieme; mentre lungo il ramo del percorso troviamo degli oggetti di un certo peso da mettere in uno zaino, che potrebbero essere anche dei job da fare per ottenere un oggetto finito.

Mi direte ma nel labirinto non c'è parallelismo ... non è detto: dipende da quante persone lo percorrono contemporaneamente.

E' come se il problema dello scheduling fosse riconducibile a vari sottoproblemi:
- teoria dei grafi e dei labirinti
- algoritmi della teoria scheduling
- il problema dello zaino

In effetti di un labirinto, almeno inizialmente, nessuno ne conosce i percorsi, così come nelle pianificazioni che occorre studiare bene come ottenere una pianificazione decente e coerente.

Da quanto detto un labirinto è rappresentabile con un grafo orientato ed in esso occorre:
- individuare il percorso
- individuare gli elementi secondo una tecnica di backtracking

In particolare durante l'attraversamento di un labirinto ci si segna i nodi e gli archi orientati e il relativo peso.

Una volta individuato il labirinto occorre iniziare a vedere quale oggetto/task ooccorre estrarre per arrivare alla successiva lavorazione. Occorre stare attenti a semplificare il problema altrimenti si arriva ad aggiungere molte condizioni e vincoli che aumentano il costo dell'elaborazione. La strategia di scelta degli oggetti/task deve essere, difatti, quella che è in relazione alla sequenza ottima che minimizza il makespan, il peso degli oggetti e i tempi di computazione.

Non si può usare prima la tecnica dello zaino e poi la tecnica del MST perchè si arriverebbe ad una soluzione non necessariamente la migliore in termini di schedulazione; per cui la soluzione migliore è di fare prima un algoritmo che restittuisca il makespan a cui si applica la tecnica dello zaino.

Supponiamo che ci siano n task che m macchine possono lavorare in parallelo, col vincolo di preemption, e che un task startato su una macchina può continuare su una macchina differente, a seguito di interruzione sulla macchina precedente.

Chiamiamo Cmax il tempo massimo di lavorazione in cui le m macchine devono completare gli n task:

Cmax = max(1<=j<=n) Cj

Mentre xij= frazione di task j lavorata sulla macchina i, col vincolo che Sum(i=1,m, xji) = 1 (Che esprime che una sola macchina per volta lavora un task: non è consentita la preemption). In particolare xji={0,1}.

Il tempo totale di lavoro della macchina i è: ki=Sum(j=1,n,pj*xji).

Riassumendo la formulazione in LP è:

min Cmax
Sum(j=1,n,pj*xji) <= Cmax
Sum(i=1,m, xij) = 1
xji>=0

E' vera la seguente affermazione: Sia x* una soluzione che soddisfa tutte le condizioni e vincoli, allora x* è la soluzione ottima.

Infatti rispetto a x* tutte le macchine hanno lo stesso carico e terminano in Cmax. Se x* non fosse la soluzione ottima e le macchine lavorassero con carico sbilanciato, significa che si potrebbe ridurre lo stesso il makespan ridistribuendo il lavoro sulle varie macchine il carico che era maggiore su una delle macchine. Ma questo ci riporterebbe a dire che x* non era ottimo ma che ne esiste un altro valore ottimo (ma che soprattutto non erano soddisfatte bene tutte le condizioni).

In particolare Cmax(x*) = 1/m * Sum(j=1,m,pj). Quindi siamo alla ricerca di un vettore x* delle variabili decisionali e una volta trovato x* si può passare a studiare il problema del sacco (knapsack).

Il problema, come già più volte evidenziato, può essere formulato nel seguente modo. Si hanno a disposizione n oggetti, ciascuno con valore vi e costo ci; nella fattispecie, tali parametri possono essere rivisti come tempo di processamento e peso. In questo caso il problema può essere espresso come massimizzazione del valore, nel rispetto della sequenza makespan e minimizzazione del peso, visto che dovranno essere effettuati diversi viaggi.

Se C è la disponibilità massima del trasporto, si avrà:

max F = Sum(i=1,n,vi*xi)
Sum(i=1,n,ci*xi)<=C con xi={0,1}

La programmazione dinamica si può espletare nel seguente modo:
- determinare il cammino e la lista di oggetti;
- implementare il makespan e determinare la sequenza di schedulazione;
- entrare nel labirinto e con la procedura di knapsack riempire il sacco, uscire ed avviare il processamento; mentre ciò avviene, rientrare nel labirinto e prelevare un altro sottoinsieme di oggetti fintantochè tutti gli oggetti non sono stati rimossi dal labirinto stesso.

Un'ulteriore complicazione può essere data dall'inserimento nel vincolo di rispetto della sequenza, e che negli intervalli di tempo in cui l'operatore sta asportando gli oggetti dal labirinto, almeno un processamento sia in atto; cioè l'insieme delle macchine non deve mai essere inoperoso. Chiaramente tale fatto complica notevolmente la soluzione del problema.

Per fissare i concetti di sopra vediamo però un esempio concreto in LP di una pianificazione di task e risorse umane, potrebbe essere anche un orario scolastico ad esempio.

Si possono risolvere problemi molto complessi (in questi ambiti basta poco per complicarli) e realizzare sistemi con Database Oracle, PL/SQL e con un motore risolutore GPLK. Nel seguito esamineremo un
problemino di schedulazione semplice.

Problemino di schedulazione
In un impianto di produzione di tutti i giorni un certo numero di personale è necessario. Il personale può essere essere assunto per un minimo fino ad un numero massimo di giorni consecutivi, richiede un numero minimo di giorni di ferie prima di poter essere nuovamente utilizzati. Il compito è di trovare
l'orario di lavoro riducendo al minimo salario totale da pagare.

Ecco come formuliamo il problemqa in CMLP:

# Personnel assignment problem
#
#

# workload (day, workload)
set L, dimen 2;

# workers (name, min workdays, max workdays, minimum leave, wage)
set W, dimen 5;

# names of workers
set V := setof{(v, b, c, d, e) in W} v;

# periods
set B := ( (min{(b,c) in L} b) .. (max{(b,c) in L} b) );

# minimum number of workdays in row
param ri{v in V} := min{(v, b, c, d, e) in W} b;

# maximum number of workdays in row
param ra{v in V} := min{(v, b, c, d, e) in W} c;

# minimum leave days in row
param ml{v in V} := min{(v, b, c, d, e) in W} d;

# wage
param wa{v in V} := min{(v, b, c, d, e) in W} e;

# work offer [worker, start, duration]
# (for large problems consider column generation to create work offers)
set O := setof{ v in V, s in B, d in {ri[v]..ra[v]}}( v, s, d);

# workday
param wd{b in B, (v, s, d) in O} :=
if b < s then 0 else if b - s > d - 1 then 0 else 1;

# leaveday
param ld{b in B, (v, s, d) in O} :=
if b < s + d then 0 else if b - s > d + ml[v] - 1 then 0 else 1;

# work offer used
var x{(v,s,d) in O}, binary;

# minimze total wage
minimize wage :
sum{b in B, (v,s,d) in O} x[v,s,d] * wd[b,v,s,d] * wa[v];

# worker can do one job only
s.t. j1{b in B, v in V} :
sum{(v,s,d) in O} x[v,s,d] * ( wd[b,v,s,d] + ld[b,v,s,d] ) <= 1;

# do all jobs
s.t. ja{b in B} :
sum{(v,s,d) in O} x[v,s,d] * wd[b,v,s,d] >= sum{(b, w) in L} w;

solve;

# output solution
printf "\n%-10s", "Day";
for {v in V}
printf "| %-10s", v;
printf "\n";
printf "%-10s", '----------';
for {v in V}
printf "+-%-10s", '----------';
printf "\n";
for {b in B}
{
printf "%9i ", b;
for {v in V}
    printf "| %-9s ",
      if sum{(v,s,d) in O} x[v,s,d] * wd[b,v,s,d] then "working"
      else "on leave";
printf "\n";
}
printf "\n";

data;

# workload
set L := # day, workload
( 1, 3)
( 2, 1)
( 3, 1)
( 4, 1)
( 5, 1)
( 6, 2)
( 7, 2)
( 8, 2)
( 9, 3)
(10, 2)
(11, 2)
(12, 2)
(14, 1)
(15, 2)
(17, 3)
(18, 3)
(19, 2)
(21, 3)
(23, 1)
(24, 3)
(25, 3)
(26, 3)
(27, 2)
(28, 1)
(29, 1)
(30, 2)
(31, 1)
(32, 3)
(33, 2)
(35, 3)
(36, 3)
(37, 1)
(38, 3)
(39, 2)
(40, 3)
(43, 1)
(44, 1)
(45, 2)
(46, 2)
(47, 3)
(48, 2)
(49, 1)
(50, 2);

# workers
set W := # name, min workdays, max workdays, minimum leave, wage
( 'Anna',   5, 8, 2, 470 )
( 'Isabel', 5, 8, 2, 500 )
( 'Jack',   1, 8, 2, 1000 )
( 'John',   5, 8, 2, 600 )
( 'Lisa',   3, 5, 3, 640 );
end;

Ora eseguiamo il file scritto.

K:\Work\LP>glpsol --model workload.txt
Reading model section from workload.txt...
Reading data section from workload.txt...
147 lines were read
Generating wage...
Generating j1...
Generating ja...
Model has been successfully generated
ipp_basic_tech: 8 row(s) and 8 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 293 rows, 1142 columns, 13200 non-zeros
glp_intopt: 1142 integer columns, all of which are binary
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Crashing...
Size of triangular part = 293
Solving LP relaxation...
      0: obj = 0.000000000e+000 infeas = 8.700e+001 (0)
*   100: obj = 8.699000000e+004 infeas = 0.000e+000 (0)
*   200: obj = 5.981000000e+004 infeas = 6.106e-016 (0)
*   338: obj = 5.253000000e+004 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+   338: mip =     not found yet >=              -inf        (1; 0)
+   361: >>>>> 5.263000000e+004 >= 5.254000000e+004   0.2% (3; 0)
+   371: mip = 5.263000000e+004 >=     tree is empty   0.0% (0; 5)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.2 secs
Memory used: 20.6 Mb (21554667 bytes)

Day       | Anna      | Isabel    | Jack      | John      | Lisa
----------+-----------+-----------+-----------+-----------+-----------
        1 | on leave | working   | working   | on leave | working
        2 | on leave | working   | on leave | on leave | working
        3 | on leave | working   | on leave | on leave | working
        4 | on leave | working   | on leave | on leave | on leave
        5 | on leave | working   | on leave | on leave | on leave
        6 | working   | working   | on leave | on leave | on leave
        7 | working   | working   | on leave | on leave | on leave
        8 | working   | on leave | on leave | working   | on leave
        9 | working   | on leave | working   | working   | on leave
       10 | working   | on leave | on leave | working   | on leave
       11 | working   | on leave | on leave | working   | on leave
       12 | working   | on leave | on leave | working   | on leave
       13 | on leave | on leave | on leave | on leave | on leave
       14 | on leave | working   | on leave | on leave | on leave
       15 | working   | working   | on leave | on leave | on leave
       16 | working   | working   | on leave | on leave | on leave
       17 | working   | working   | on leave | on leave | working
       18 | working   | working   | on leave | on leave | working
       19 | working   | on leave | on leave | on leave | working
       20 | working   | on leave | on leave | on leave | on leave
       21 | working   | working   | working   | on leave | on leave
       22 | on leave | working   | on leave | on leave | on leave
       23 | on leave | working   | on leave | on leave | on leave
       24 | working   | working   | on leave | on leave | working
       25 | working   | working   | on leave | on leave | working
       26 | working   | working   | on leave | on leave | working
       27 | working   | working   | on leave | on leave | on leave
       28 | working   | on leave | on leave | on leave | on leave
       29 | working   | on leave | on leave | on leave | on leave
       30 | working   | on leave | on leave | on leave | working
       31 | on leave | on leave | on leave | on leave | working
       32 | on leave | working   | on leave | working   | working
       33 | on leave | working   | on leave | working   | on leave
       34 | on leave | working   | on leave | working   | on leave
       35 | working   | working   | on leave | working   | on leave
       36 | working   | working   | on leave | working   | on leave
       37 | working   | working   | on leave | on leave | on leave
       38 | working   | working   | on leave | on leave | working
       39 | working   | on leave | on leave | on leave | working
       40 | working   | on leave | working   | on leave | working
       41 | on leave | on leave | on leave | on leave | on leave
       42 | on leave | on leave | on leave | on leave | on leave
       43 | working   | on leave | on leave | on leave | on leave
       44 | working   | on leave | on leave | on leave | on leave
       45 | working   | on leave | on leave | on leave | working
       46 | working   | on leave | on leave | on leave | working
       47 | working   | working   | on leave | on leave | working
       48 | working   | working   | on leave | on leave | on leave
       49 | on leave | working   | on leave | on leave | on leave
       50 | on leave | working   | on leave | working   | on leave

Model has been successfully processed

Un consiglio. E' ovvio che lo strumento vi calcola il tutto in base ai dati che gli avete fornito e funziona benissimo quando la durata del tempo è ben fissata da regole, come nell'organizzazione di orari, turni etc.

Mentre nelle pianificazioni di lavori come realizzazione di un software, molto della pianificazione dipende da voi nel saper ben valutare il tempo, le persone disponibili e l'organizzazione e professionalità necessarie per svolgere un task, etc. Per questo vi affiderete a statistiche che avete raccolto nel tempo nell'effettuare quel lavoro o a metodologie specifiche o a regolamentazioni previste per quel lavoro.

Alla prox

Un sacco di mal di testa: Il problema dello zaino (Knapsack)

2010-09-21T14:07:00.000-07:00

Il problema dello zaino è uno dei “21 problemi NP-completi della lista di Karp”. Esso si può formulare nel seguente modo: sia N, il numero totale di oggetti xi, sia wi il peso del singolo oggetto xi, ci il valore del singolo oggetto xi e W il peso totale sopportabile dallo zaino.

La funzione obiettivo da massimizzare è in tal caso, considerando xi=1 se si inserisce nello zaino o 0 in caso
contrario: maxZ=Sum{i=1..N}c_{i}*x_{i} mentre il vincolo impone che:sum_{i=1..N} x_{i}*w_{i} <= W

In sostanza maxZ è il massimo valore ottenibile come oggetti che posso mettere nello zaino, non necessariamente N, ma nello stesso tempo il massimo numero di oggetti è limitato dal massimo peso trasportabile.

Ovviamente il problema dello zaino è isomorfo ad altri problemi simili, anzicchè dello zaino potrebbe essere la stiva di un aereo, o di una barca etc. e il valore ed il peso possono avere un differente significato, ma trattabile allo stesso modo matematicamente.

A seconda dei valori assunti da xi il problema è classificato in modalità diversa. Se xi={0,1} allora si definisce
“problema dello zaino binario o 0-1”; se xi <= bi si definisce “problema dello zaino con limiti” ed infine se
xi appartiene a N e per ogni i appartenente a N con i>0 allora si parla di “problema dello zaino senza limiti”.

Esso è risolvibile attraverso una “programmazione dinamica”, termine non finalizzato ad un fine informatico, ma entrato in uso negli anni Quaranta ad indicare la suddivisione in sottoproblemi e strutture ottimali. Sulla strada del “Subset-sum” furno ideate anche tecniche crittografiche a chiave pubblica, come quella Markle-Hellman successivamente abbandonata poichè facilmente risolvibile con algoritmi lineari.

Facciamo un esempio, Nella tabella successiva abbiamo 9 possibili oggetti, con peso e valore, che potremmo mettere nello zaino tenendo presente che il massimo peso trasportabile è W=27Kg :

Oggetto    Peso (kg)    Valore (euro)    Valore/Peso
x1               10                    200     20
x2               12                    225    18,75
x3               15                    250            16,67
x4                 9                    150            16,67
x5                 7                    125            17,86
x6                 6                    125            20,83
x7                 6                    120            20
x8                 6                    120            20
x9                 4                      75            18,75

Esistono varie strategie algoritmiche euristiche e di rilassamento che per la sua soluzione non richiede molto tempo, ad esempio con tecnica “Branch e bound” in ambito della Linear Programming e dovuto a A.H. Land e A.G.Doig nel 1960. Tale tecnica è una enumerazione implicita cioè prova a enumerare tutte le possibilità, individuando quella ottima o quella possibile, scartando le altre.

L'algoritmo Greedy di tipo euristico è dovuto, invece, a Martello e Toth (1990). Esso ordina gli oggetti in ordine decrescente di peso, per inserirli nello zaino fino all'esaurimento dello spazio disponibile. Se k è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo Greedy garantisce che ne siano inseriti nello zaino almeno k/2.

Sono possibili molte variazioni di questo algoritmo, la più efficiente prevede di ordinare gli elementi in base al loro costo unitario, vale a dire ci/wi ed inserirli in ordine decrescente (euristica CUD). Questi algoritmi essendo euristici non garantiscono l'ottimalità della soluzione ma sono in grado di fornire una "buona" soluzione in tempo ragionevole. Possiamo usare GnuWin32 (gplsol), scrivendo un file in formato GMPL oppure LP; ma se volessimo adottare strategie senza “aiuti software” potremmo avere diverse soluzioni (esaminiamo il problema dello zaino binario):

• Soluzione 1: prendo gli oggetti più pesanti che non superano i 27 kg: ad esempio x2+x3 che mi danno 27 kg ed un valore di 475 euro

• Soluzione 2: prendo gli oggetti più leggeri per aumentarne il numero ad esempio x6+x7+x8+x9 in questo caso si ottiene 22Kg ed un valore di 530 euro (meno peso e maggior valore).

• Soluzione 3: prendo gli oggetti di maggiore valore in base al rapporto valore/peso x1+x6+x7+x9 ovvero 26kg e 520 euro

• Soluzione 4: raggiungo i 27 kg con gli oggetti di maggiore valore x1+x5+x6+x9 ovvero 27Kg e 525 euro

La soluzione 4, come si vede, massimizza la funzione del valore. In questo caso erano poche le variabili in gioco ma se fossero state molte sarebbe stato necessario l'”aiuto software”.

OK, vi do la formulazione del problema di sopra in formato GMPL da risolvere con GLPSOL.

Eccola:

# This file shows how to model a knapsack problem in GMPL.

# Size of knapsack
param c;

# Items: index, size, profit
set I, dimen 3;

# Indices
set J := setof{(i,s,p) in I} i;

# Assignment
var a{J}, binary;

maximize obj :
sum{(i,s,p) in I} p*a[i];

s.t. size :
sum{(i,s,p) in I} s*a[i] <= c;

solve;

printf "The knapsack contains:\n";
printf {(i,s,p) in I: a[i] == 1} " %i", i;
printf "\n";

data;

# Size of the knapsack
param c := 27;

# Items: index, size, profit
set I :=
1 10 200
2 12 225
3 15 250
4 9 150
5 7 125
6 6 125
7 6 120
8 6 120
9 4 75;

end;

Ora che avete il file knapsack.txt lanciate il comando:

glpsol --model knapsack.txt

e otterrete l'output:

K:\Work\LP>glpsol --model knapsack.txt
Reading model section from knapsack.txt...
Reading data section from knapsack.txt...
44 lines were read
Generating obj...
Generating size...
Model has been successfully generated
ipp_basic_tech: 1 row(s) and 0 column(s) removed
ipp_reduce_bnds: 1 pass(es) made, 0 bound(s) reduced
ipp_basic_tech: 0 row(s) and 0 column(s) removed
ipp_reduce_coef: 1 pass(es) made, 0 coefficient(s) reduced
glp_intopt: presolved MIP has 1 row, 9 columns, 9 non-zeros
glp_intopt: 9 integer columns, all of which are binary
Scaling...
A: min|aij| = 4.000e+000 max|aij| = 1.500e+001 ratio = 3.750e+000
GM: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
EQ: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
2N: min|aij| = 7.500e-001 max|aij| = 1.250e+000 ratio = 1.667e+000
Crashing...
Size of triangular part = 1
Solving LP relaxation...
      0: obj = 5.400000000e+002 infeas = 1.360e+001 (0)
*     2: obj = 3.500000000e+002 infeas = 0.000e+000 (0)
*     8: obj = 5.450000000e+002 infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     8: mip =     not found yet <=              +inf        (1; 0)
+    15: >>>>> 5.150000000e+002 <= 5.350000000e+002   3.9% (4; 0)
+    25: >>>>> 5.200000000e+002 <= 5.350000000e+002   2.9% (6; 4)
+    29: >>>>> 5.250000000e+002 <= 5.250000000e+002   0.0% (1; 11)
+    29: mip = 5.250000000e+002 <=     tree is empty   0.0% (0; 17)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   0.1 secs
Memory used: 0.1 Mb (155039 bytes)
The knapsack contains:
1 5 6 9
Model has been successfully processed

Alla prox

Problemi matematici minori ?

2010-09-16T11:16:00.000-07:00

In Matematica esistono innumerevoli problemi, apparentemente minori, nel senso che non sono direttamente classificati tra i "problemi del Millennio"; ma che tuttavia se risolti avrebbero un impatto tecnologico notevole nella vita odierna.

Soprattutto permetterebbero pianificazioni ed uso di risorse in modo mirato e a minor costo.

Non solo ma risolvendo un problema, si risolverebbero problemi "isomorfi in altri contesti".

Per farvi comprendere di che si tratta pensate a: traffico aereo, percorsi idrici, gas, fognature in una città, distensione dei cavi e delle fibre ottiche, creazione di circuiti integrati con aggiunta di nuovi nodi o vertici, ma anche nelle trasmissioni audio, video, etc. 

Avete mai fatto delle audio col numero verde 800 dove si collegano e si scollegano varie persone? Ebbene un sistema efficiente deve ricalcolare ogni volta l'albero di Steiner più efficace per poter riequilibrare QoS (Quality of Service) e percorsi di minor costo o banda.

In poche parole si tratta del “problema di Steiner”. Per introdurvi al problema immaginate di avere un grafo G di cui inizialmente avete solo i nodi (i vertici) V e volete creare un albero (albero di Steiner) col numero minimo di collegamenti pesati. 

Chiariamo subito che  per “pesati” occorre immaginare un costo che può essere, ad esempio, in un’audio telefonica il tempo di trasmissione o di ritardo e la qualità del segnale QoS; mentre per albero intendiamo dei collegamenti senza percorsi chiusi (no ad anelli o a circuiti). Ad esempio con quattro vertici colleghiamo solo 3 lati di un quadrato (l'ultimo lato non lo disegniamo).

Se il grafo fosse statico cioè con vertici fissi, l’algoritmo ottimizzato di Kruskal risolverebbe benissimo la cosa; ma se c’è una dinamicità nel tempo dei vertici n=|V|, allora la cosa si complica di parecchio (anche se è risolvibile ma non in maniera ottimale assoluta). 

La tecnica dell'algoritmo di Kruskal con vertici statici è semplice. Immaginiamo di avere di ogni coppia di vertici il costo e ordiniamoli dal costo più basso al costo più alto. A questo punto colleghiamo (senza creare percorsi chiusi altrimenti non avremo un albero) i nodi a costo minore, via via arrivando a quelli di costo maggiore e ci arrestiamo se abbiamo collegato già tutti i vertici statici. 

Siamo, quindi, nella teoria dei grafi, quella iniziata nel Settecento con Eulero e il problema dei ponti di Konigsberg. 

Nel problema di Steiner l'obiettivo è di cercare, ad ogni variazione del numero di vertici(aggiunta o rimozione) , l’albero dei collegamenti minimi che ottimizza le risorse (i costi) che variano nel tempo. 

Pensate alla banda di trasmissione e il QoS che deve essere rispettato all'aumentare dei nodi che si collegano o alla variazione delle località dei nodi. 

E’ dimostrato che il problema di Steiner è NP-completo; per cui il problema di Steiner rientra 'indirettamente' nel "problema del millennio P=NP".

A questa famiglia ne appartengono molti : il problema dello zaino o sacco da viaggio, del commesso viaggiatore, il problema di Steiner, il problemino dell'individuare il maggior numero di mopnetine di ogni taglio disponibile per pagare un conto, la fattorizzazione del RSA, il logaritmo discreto etc.  

Come tutti i problemi NP-completi,  non riuscendo a trovare un algoritmo deterministico polinomiale si cerca di trovare almeno non l’ "ottimo in assoluto" ma il "miglior ottimo disponibile" con tecniche euristiche o altre. Il che non significa che non esiste una soluzione, anzi la soluzione esiste ma è di tipo esponenziale rispetto ai dati di input e, quindi, poco efficiente.

Sono nati,a tal proposito, molto algoritmi a risoluzione del problema; ad esempio troviamo tra:

Algoritmi ottimi

Spanning Tree Enumeration Algorithm (STEA)
Dynamic Programming Algorithm (DPA)

Euristiche per il problema di Steiner 

Pruned Dijkstra Heuristic (PDH)
Distance Network Heuristic (DNH)
Shortest Path Heuristic (SPH)
Kruskal based – Shortest Path Heuristic (K-SPH)
Repetitive Shortest Path Heuristics
Average Distance Heuristic (ADH)

Tecniche di Post-processing

Ma esistono anche tanti altri SAT, 3SAT etc.

Come in tutte le discipline ingegneristiche, dove non esiste una soluzione ottima assoluta, allora ognuno degli algoritmi trovati è forte in un "certo range di quantità", per cui anche quelli di cui parlavo prima hanno una efficienza che li avvantaggia o li svantaggia all’aumentare del numero di vertici. Spesso un software di gestione delle risorse dispone più algoritmi, che sceglie in base alla quantità di vertici in cui si ritrova.

OK, starete già su Wikipedia a vedere la corretta definizione del problema. Bravi! Si inizia da lì, altrimenti vi ritrovereste a risolvere un problema mal definito e vi illudereste di aver trovato la soluzione!

Esistono anche varie versioni del problema di Steiner:
problema di Steiner nelle reti (la versione generale che interessa)
problema di Steiner rettilineo: la topologia è data dal piano R^2 con la metrica indotta dalla 'distanza Manhattan';
problema di Steiner euclideo: anche in questo caso la topologia è data dal piano R^2, con la metrica indotta dalla distanza euclidea;
Il problema che interessa dovrebbe esser formulato come segue: 
 
"Data una rete connessa e non diretta G = (V, E, w), w : E -> R, e un insieme Z sottoinsieme di V,trovare il sottografo connesso Gs = (Vs, Es, w) di G tale che:
a) Z sottoinsieme di Vs (strettamente incluso o incluso in Vs);
b) w(Gs) = Sum(i,j,w(i,j)) sia minimo con i,j appartenenti a Es".


L’insieme Z è detto, con riferimento al problema trattato, 'insieme di multicast'; mentre l’insieme Vs – Z viene denotato con S ed è costituito dai 'nodi di Steiner'.


Se la funzione di costo w(i, j) degli archi assume sempre valori positivi il sottografo soluzione è un albero, detto 'albero di Steiner', che verrà indicato nel seguito con Tz. Si pone inoltre n = |V|, m = |E|, p = |Z|, s = |S|.Alcuni casi limite del problema di Steiner però ricadono in problemi ben noti della teoria dei grafi:

p = 2: si tratta di trovare il percorso più breve che connetta i due nodi dell’insieme Z; il problema viene risolto dall’algoritmo di Dijkstra, che restituisce un albero di cammini minimi da un nodo verso tutti gli altri nodi della rete;
p = n, cioè Z = V: si tratta di calcolare il minimum spanning tree o MST del grafo dato;in questo caso il problema viene risolto dall’algoritmo di Prim o dalla variante di Kruskal. 
La valutazione della qualità degli algoritmi di questo genere di solito avviene su due fattori di merito:
la competitività di costo, intesa come bontà della soluzione trovata Th (l'albero di STeiner trovato) rispetto a quella ottima Tz e in formule : 
                        ch = w(Th)/w(Tz)

la complessità computazionale, in notazione O(f(n))

Molti altri problemi sono importanti per l'industria alimentare come quello dell'impacchettamento (pensate al problema dell'impacchettamento delle sfere di Keplero) o della realizzazione di scatole al minor costo e con determinate qualità. 

Pensate alle buste del latte o ai nuovi contenitori ideati i cosiddetti 'tetrapack' o anche a mobili in alluminio/acciao o a macchine per catene di montaggio; ma ne parleremo la prossima volta. Aggiungo solo una nota di colore: Steiner era svizzero e la sua cultura era autodidatta. Imparò a leggere e scrivere a 14 anni e si dimostrò un genio matematico tale da insegnare a 20 anni.

Ma soprattutto era uno genio della geometria: molti teoremi li dimostrava visivamente, grazie alla geometria, come la dimostrazione del "problema di Didone" e del "problema isoperimetrico".

Alla prox

Programmazione lineare

2010-09-12T02:42:00.000-07:00

Esiste una categoria di problemi di matematica che rientrano nella Linear Programming (LP) o anche programmi interi misti (MIPS). In questi problemi l'obiettivo è di massimizzare o minimizzare una risorsa (funzione obiettivo), che è soggetta a dei vincoli.

Con queste tecniche si possono risolvere problemi come quello del commesso viaggiatore, il SUDOKU, tecniche bancarie etc.

Molti di questi problemi possono risolversi sia graficamente che con strumenti di calcolo usando, nel caso LP, il metodo del simplex (vedi Wikipedia), del punto intermedio (primal-dual interior point); mentre nel caso MIPS tecniche come "Branch and bound".

Spesso un problema di massimizzazione è anche affrontabile come una minimizzazione al contrario.

La tecnica grafica, che deve essere altrettanto dominata, va bene se il problema ha poche dimensioni in gioco; appena il numero di dimensioni diventano moltissime, serve uno strumento automatico che risolvi il problema.

Molti di questi problemi sono isomorfi, nel senso che capito come si risolve uno di essi, tutti gli altri problemi, anche se con descrizione diversa, possono essere ricondotti ad una tale tecnica.

Un sito proposto per gli approfondimenti è http://www.sce.carleton.ca/faculty/chinneck/StudentOR.html

Esempio
Supponiamo che la Fargo è una società che produce barattoli di pittura bianca, gialla, nera e rossa. Per
fare queste pitture la Fargo usa tre materiali grezzi: 40 litri di olio, 25 litri di solvente e 20 litri di pigmenti.

Per fare il bianco si spendono 12 euro, con 0.8 litri di pigmento, 0.4 di solvente e 0.5 di olio.
Per fare il giallo si spendono 8 euro, con 0.5 litri di pigmento, 0.2 di solvente e 0.7 di olio.
Per fare il nero si spendono 9 euro, con 0.2 litri di pigmento, 0.5 litri di solvente, 0.6 di olio.
Per fare il rosso si spendono 11 euro, con 0.3 litri di pigmento, 0.6 litri di solvente e 0.4 litri di olio.

L'obiettivo è di massimizzare il profitto della Fargo.

Si possono usare molti strumenti: alcuni professionali (LINDO etc) ed altri open source (GNUWin32 con GLPSOL). Noi useremo GNUWin32 nel seguito per l'esempio didattico (http://www.gnu.org/software/glpk).

Installiamo GNUWin32 e inseriamo nel PATH di windows il percorso fino alla directory bin.

Il primo passo è formalizzare il problema. Esistono molti formati per farlo (GMPL, LP etc).

Nel seguito useremo il formato più intuitivo LP per la formalizzazione algebrica, poi successivamente quello GMPL.

Scriviamo con Notepad un file Fargo.txt del tipo:

\\ Problem Fargo.txt - LP format

Maximize
    obj: 12 x1 + 8 x2 + 9 x3 + 11 x4

Subject to
    c1:    .8 x1 + .5 x2 + .2 x3 + .3 x4 <= 20
    c2:    .4 x1 + .2 x2 + .5 x3 + .6 x4 <= 25
    c3:    .5 x1 + .7 x2 + .6 x3 + .4 x4 <= 40
End

Da DOS sotto Windows (comando cmd) ci posizioniamo nella directory del file Fargo.txt.

Proviamo prima l'help per vedere se l'installazione funziona: glpsol --help

Adesso dobbiamo istruire GLPSOL che abbiamo un file in formato LP:
glpsol --cpxlp fargo.txt --output fargo.out

e otterrete la soluzione a video e sul file di output fargo.out. Se c'è la scritta OPTIMAL SOLUTIONS FOUND, significa che ha trovato anche la soluzione ottimale.

L'output si presenta come segue
Problem:
Rows:       3
Columns:    4
Non-zeros: 12
Status:     OPTIMAL
Objective: obj = 553.7037037 (MAXimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 c1           NU            20                          20       9.25926
     2 c2           NU            25                          25        12.963
     3 c3           NU            40                          40       1.11111

   No. Column name St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                    -1.14815
     2 x2           B        23.4568             0
     3 x3           B        37.6543             0
     4 x4           B        2.46914             0

Karush-Kuhn-Tucker optimality conditions:

KKT.PE: max.abs.err. = 1.48e-015 on row 2
        max.rel.err. = 5.68e-017 on row 2
        High quality

KKT.PB: max.abs.err. = 0.00e+000 on row 0
        max.rel.err. = 0.00e+000 on row 0
        High quality

KKT.DE: max.abs.err. = 8.68e-016 on column 4
        max.rel.err. = 7.24e-017 on column 4
        High quality

KKT.DB: max.abs.err. = 0.00e+000 on row 0
        max.rel.err. = 0.00e+000 on row 0
        High quality

End of output

Potreste usare anche le opzioni:
glpsol --cpxlp fargo.txt --output fargo.out --bound fargo.bnd

In questo modo otterrete anche un file di spiegazione. Il vantaggio di GLPK è che è open source e fornisce non solo il tool GLPSOL per la risoluzione interattiva di problemi, ma anche API per linguaggio C/C++.

In formato GMPL occorre scrivere prima il file modello fargo.gmpl:

# FARGO’S PRODUCTION PLANNING MODEL
# MODEL file
set R; /* resources */
set P; /* paint products */
param b{r in R}; /* on-hand levels of paint resources (in liters) */
param c{p in P}; /* profit contribution (per liter of paint) */
param a{p in P, r in R}; /* amount of resource consumed from producing paint */
var x{p in P} >= 0; /* amount of paint p to be produced */
s.t. rc{r in R}: sum{p in P} a[p,r] * x[p] <= b[r];
/* resource capacity */
maximize profit: sum{p in P} c[p] * x[p];
/* total profit (dollars) */
end;

poi va scritto il file dati fargo.data:

data;
set R := Pigment Solvent Oil;
set P := PaintA PaintB PaintC PaintD;
param : b :=
Pigment 20 /* liters */
Solvent 25 /* liters */
Oil 40 /* liters */ ;
param : c :=
PaintA 12 /* euros */
PaintB 8 /* euros */
PaintC 9 /* euros */
PaintD 11 /* euros */ ;
param a : PaintA PaintB PaintC PaintD :=
Pigment 0.8 0.5 0.2 0.3
Solvent 0.4 0.2 0.5 0.6
Oil 0.5 0.7 0.6 0.4 ;
end;

I comandi dovranno usare questa volta le opzioni --model e --data

Per una introduzione teorica dei problemi LP vi segnalo il pdf "Linear Programming
A Concise Introduction - Thomas S. Ferguson" che potrete scaricare da internet.

Alla prox

Algoritmica Ricreativa

2010-08-26T08:23:00.000-07:00

Nella vita di tutti i giorni ognuno di noi applica algoritmi in modo consapevole o inconsapevole:

come fare meglio un'attività,
come organizzare, in sequenza e/o in parallelo, delle attività (pianificazioni),
come massimizzare ottimizzare delle risorse (tempo, memoria, spiccioli, probabilità, ricchezza, etc),
come individuare gruppi di informazioni nascoste rispetto a determinate dimensioni (clustering),
come individuare relazioni e reti di comportamento (organizzazioni, mercati, etc)
come individuare gerarchi ad albero (es: parentele etc)
etc.

I nostri algoritmi vengono "implementati" meccanicamente, intuitivamente.

Possono essere algoritmi deterministici o non deterministici. Quelli deterministici si sviluppano facilmente basandosi su delle regole esprimibili matematicamente, quelli non deterministici spesso si devono basare su probabilità e/o su euristica.

Molti sono i problemi matematici-informatici non ancora soddisfacentemente risolti. Molti di essi fanno parte del problema del millennio "P=NP?". I problemi P sono problemi che si risolvono in un tempo polinomiale, ovvero in un tempo al più potenza dell'input. I problemi NP sono, invece, quelli "non polinomiali", molto spesso NP-completi (vedi Wikipedia).

Fanno parte della famiglia NP la fattorizzazione di un numero con molte cifre (su cui si basa l'inviolabilità del RSA), il problema del logaritmo discreto, il problema del commesso viaggiatore, il problema dell'ottimizzazione del sacco, delle pesate etc.

Non crediate che solo i problemi famosi sono di questo tipo. Pensate al fastidio degli innumerevoli spiccioli che dobbiamo portarci dietro, questa estate, nel piccolo taschino dei pantaloni.

E' ovvio che chiunque che debba pagare un caffè, cercherà di levarsi quanti più spiccioli è possibile.

Ecco un problema ricreativo: "Come lavora un algoritmo per massimizzare il numero di monete in centesimi ed euro con cui pagare il bar?"

Supponiamo di avere:

S la somma da pagare
Q1 monete da taglio T1 (1 cent)
Q2 monete da taglio T2 (5 cent)
Q3 monete da taglio T3 (10 cent)
Q4 monete da taglio T4 (20 cent)
Q5 monete da taglio T5 (50 cent)
Q6 monete da taglio T6 (1 euro)

Dopo vari tentativi è sufficiente in ciclo individuare il valore dell'indice i tale che Sum(Qi*Ti) > S e in tal modo individuiamo la prima moneta di taglio Ti da usare.

A questo punto si ripete come se la somma da pagare nuova è Sn= S - Ti. Se Sn= S- Ti è positivo si ripete il ciclo per individuare un'altro taglio di moneta Ti e così via; se invece S - Ti < 0 significa che occorre ricevere resto e l'algoritmo si arresta.

In tal caso col resto ricevuto si cercherà di farsi cambiare dalla cassa le ulteriori monetine rimaste con poche altre monete di taglio maggiore.

Supponiamo S=85 centesimi, Q1=9, Q2=3, Q3=6, Q4=3, Q5=2, Q6=1. Allora se provate ad applicare più volte l'algoritmo, otterrete che ci possiamo liberare in prima battuta di 13 monetine su 28: una da 20 c, cinque da 10 c, due da 5 c, cinque da 1c.

Stesso problema, altra prospettiva: "Dobbiamo pagare una lavatrice, non abbiamo assegni ma contante e spiccioli".

Se dobbiamo pagare 400 euro con l'algoritmo di sopra ci linciano! L'algoritmo in questo caso è simile a quello di sopra ma tenta di prendere prima le monete di taglio maggiore (es: 500 euro, 100 euro, 50 euro, 10 euro) in assoluto.

I due problemi di sopra sono semplici e usano una tecnica lineare per trovare la soluzione. Se pensiamo, invece, allo stesso problema da un punto di vista ulteriore le cose si possono complicare un poco soprattutto per l'efficienza perchè si passa ad un problema esponenziale.

Problemi inutili? Pensate all'algoritmo "intelligente" che deve avere un distributore bancomat. Sa che dispone di una somma totale iniziale che varia ad ogni cliente, sa che in generale ha tagli da 10 euro, 20 e 50 con una certa quantità iniziale (anche nulla per certi tagli nel tempo), deve cercare di dare la somma richiesta dal cliente rispetto al massimo consentitogli (esempio 250 euro) cercando di dare diversi tagli e di proporre le somme che si avvicinano alla somma in denaro richiesta.

Corrispondenza esatta
Analizzate il problema: "Trovare le monete che paghino esattamente 85 centesimi". L'algoritmo in tal caso deve fare tutte le somme possibili tra 1 o più combinazioni di monete disponibili e vedere quali somme danno 85 come risultato; certamente è un algoritmo esponenziale.

Spesso il trucco, se non ci sono vincoli al problema, è di massimizzare o minimizzare una risorsa per portarsi in un problema lineare, ma in alcuni casi non è nemmeno semplice, come nel caso del problema del commesso viaggiatore: in tale problema il commesso viaggiatore deve fare in modo di fare il minimo percorso tale che si passi per una stessa strada una sola volta, partendo da casa e passando per ogni strada dove deve fare la commissione, e poi ritornare alla fine del percorso di nuovo a casa.

Purtroppo in questo caso occorre verificare tutti i percorsi, marcarli con un peso e alla fine trovare decidere il percorso migliore; esistono anche dei trucchi per ridurre tale ricerca, ma in ogni caso un algoritmo efficiente non di natura esponenziale finora non è stato individuato.

Alla prox

Numeri Creazionali, la metafora dell'aquilone e la sequenza di Collatz, gli automi cellulari

2010-08-07T13:33:00.000-07:00

Introduzione
In questo blog introduciamo prima una problematica ancora vicina alla Teoria dei Numeri, poi successivamente problemi di settori apparentemente diversi ma dove la struttura sottostante è sempre guidata da modelli matematici.

Numeri creazionali

Il numero creazionale di un numero n, che indichiamo col simbolo C(n), è il minor numero di cifre che occorre usare per costruire n.

Facciamo delle "ipotesi creazionali di base":
1) è possibile usare le operazioni +,*,-,/,^
2) è possibile usare i digit D=1,2 ma non necessariamente da usare insieme

Se n=80, D=1 allora C(80) <= 13

Difatti:

80=5*4*4=(1+1+1+1+1)*(1+1+1+1)*(1+1+1+1)

Abbiamo usato solo il digit 1, ma se usassimo anche il 2?
Esempio:
n=81, D=1,2 allora C(81)<=5
81=(2^(2+1)+1)^2

n = 20 D=1,2 C(20) <= 5
20 = 2^(2+2)+2+2

n=120 D=1,2 C(120)<=6
120 = ((2+1)^2+2)^2-1

n=567 D=1,2 C(567)<=8
567 = (2^(2+2+2)-1)*(2+1)^2

Una strategia algoritmica semplice è:
a) ritenere il massimo valore pari al numero n stesso (come somma di 1);
b) individuare il minimo valore possiamo con la potenza k di 2 più grande ma tale che il tutto sia minore o uguale a n stesso (2^k <= n), con k trasformato come somma di 2 e/o 1 o anche prodotti o potenze di 2, sommando, infine, se necessario 1 o altre potenze di 2.

Ad esempio:
C(21)<=6
21 = 2^(2^2) + 2^2 + 1

C(27)<=8
27 = 2^(2^2) + 2^(2+1) + 2 + 1

E' possibile per un fissato n, D=1,2 e le 5 operazioni considerate poter calcolare direttamente, senza algoritmo ma con una formula, il numero minimo di cifre necessarie a creare n?

Sequenza di Collatz
Un problema di interesse in ambito studio del chaos è quello suggerito dalla metafora dell'aquilone o dei chicchi di grandine.

Immaginiamo che ci siano folate di vento che portano verso l'alto oggetti leggeri come i chicchi di grandine o aeroplanini di carta, meglio ancora degli aquiloni.

Immaginiamo che l'aquilone parta da una altezza h (un numero), scende in basso in picchiata e poi una folata di vento lo riporta in alto, poi di nuovo scende in basso e così via fino ad atterrare al suolo (suolo = 1).

Ebbene il problema di Collatz o la sequenza di Collatz si genera a partire da un numero n, se n è pari lo si divide per 2, se n è dispari lo si moltiplica per 3 e si somma 1. Il procedimento si itera sul risultato.

La sequenza termina sempre a 1? E' ciclica, aciclica o convergente a 1?

Un lavoro su questo argomento è al link http://www.rudimathematici.com/Bookshelf/notes/RTC03.pdf
Il software è disponibile su www.gruppoeratostene.com

Solo oggi si sta iniziando ad usare la "computer graphic" per comprendere la struttura esistente dietro la matematica.Perchè ci sono schemi nascosti?

I numeri che si ottengono come output sono le traettorie seguite dall'aquilone prima di giungere al suolo (=1); ma alcuni numeri si presentano più frequentemente e il valore massimo raggiungibile nella traettoria o glide è un numero abbastanza interessante (gli autori presentano una Congettura sul Massimo nella glide); ad esempio 9232 è un massimo che si presenta in più di 350 numeri tra i gli iniziali 1000 interi.

Ma perchè nell'ambito della glide alcuni numeri sono più frequenti e ci sono determinati raggruppamenti?

Il problema di Collatz è scollegato dalla Teoria dei numeri? Gli autori mostrano anche un possibile legame con i numeri di Mersenne ed indagano su diversi teoremi.

Il problema di Collatz rientra in settori tipici molto importanti: Automi Cellulari (AC), Social Network Analisys, Chaos, Frattali, Robotica, batrachioni, Sistemi complessi etc. settori oggi molto studiati.

In ambito AC la sequenza di Collatz è in effetti un AC monodimensionale (d=1) lineare con raggio r=2/3 (infatti in ambito computer graphic il grafico è indicativo di chaos o di frattale) e secondo la classificazione dello studioso Stephen Wolfram è un AC di Classe 1, cioè partendo da n la sua evoluzione porta ad uno stato omeogeneo (sempre lo stesso, l'1) indipendentemente dall'input n.

Batrachioni e chaos
In una rete (Social Network o una rete di automi cellulari) l'evoluzione tiene almeno conto di quello che è accaduto nelle vicinanze, o anche NON immediatamente vicino (dipende dal problema). Il chaos, i batrachioni, i frattali, le trasformazioni lineari, le funzioni biettive e i mapping sono argomenti di notevole interesse per diverse discipline, tra cui anche la Social Network Analisys.

Una cosa che potrebbe sembrare inaspettata è la complessità che può emergere da semplici formule iterative, dando luogo a rappresentazioni di chaos, di frattali etc.

Un pò come le formule iterative di Fibonacci ne esistono altre altrettanto interessanti, come quelle delle curve dei "batrachioni". Il termine deriva dal greco batracen ovvero rana (in letteratura anche "small frog"), proprio perchè le curve che si ottengono sembrano dei saltelli all'infinito di rane che diminuiscono di altezza (ma non di ampiezza). Le curve sono tipicamente frattali perchè sul bordo presentano oscillazioni auto-somiglianti.

Una formula dovuta a Hofstadter-Conway è del tipo:

a[i]=a[a[i-1]]+a[i-a[i-1]]
con a[1]=1 e a[2]=1

Di interesse è il valore a[i]/i. Conway dimostrò che per lim n->inf a[n]=1/2.

Una sequenza caotica altrettanto interessante è:
a[i]=a[a[i-1]]+a[i-a[i-2]-1]
con a[1]=1 e a[2]=1

altre ancora che sono possibili sono:
       a[i]=a[a[i-1]]+a[i-a[i-2]-1];

L'ultima che fa riferimento ad elementi non adiacenti è:
   a[i]=a[a[i-2]]+a[i-a[i-3]-v];   con v=1,2

Vedi http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html

Interessanti sono anche le BlancMange Function Vedi http://mathworld.wolfram.com/BlancmangeFunction.html

Automi cellulari
Gli automi cellulari sono "sistemi complessi" usati per modellare gli dinamica dei flussi dei liquidi, le reazioni chimiche, incendi boschivi, la propagazione e nascita delle piante, di animali, e virus, percolazione del caffè, colata lavica, morfologia urbana e territoriale, inondazioni, diffusione degli inquinanti, etc

Sono spesso dette "strutture omogenee", "strutture cellulari" e "tabelle iterative".

Alcuni di questi automi cellulari si comportano in maniera strana e casuale, altri in modo ordinato, alla "frattale".

Si può avere anche una rete di automi cellulari, ognuno dei quali con regole simili ad altri (omogeneità). Di solito valgono le proprietà di Parallelismo (al tempo t parallelamente avvengono azioni su ogni cella o individuo), Omogeneità (stesse regole al tempo t per tutti i nodi della rete o individui, Località (lo stato di un individuo al tempo discreto t+1 dipende dal proprio stato e quello dei vicini).

Il concetto di automa cellulare è nato negli anni '50 con von Neumann e Stanlislaw Ulam. Conway ideò l'automa cellulare Life (Vita). Martin Gardner pubblicizzò la cosa come un gioco su Scientific American nell'ottobre del '70.

Ogni equazione differenziale si può tradurre in un automa cellulare (equazioni a differenze finite ad esempio). Da qui ad esempio si può usare l'equazione del calore per studiare una rete (anche una Social Network), ipotizzando che per il problema in questione la diffusione del calore sia un modello matematico adatto alla rete.

Life è il punto di partenza per chi vuole apprendere gli automi cellulari. Vedi gioco http://www.bitstorm.org/gameoflife/

Gli automi monodimensionali studiati da Wolfram sono l'altro punto di partenza.
Vedi http://alpha01.dm.unito.it/personalpages/cerruti/Az1/wolfram.html

Per Collatz come AC vedi http://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/
e l'articolo http://arxiv.org/PS_cache/nlin/pdf/0502/0502061v1.pdf   Tra l'altro si tratta di un AC "non invertibile"; difatti se per ogni n si giunge sempre a 1 è difficile risalire al valore n di partenza nella sequenza di Collatz.

Per una introduzione al Social Network Analysis Vedi http://www.slideshare.net/marcomuzza/social-network-analysis-presentation-919991

Gli AC hanno una notevole importanza anche per lo studio di difficili equazioni come le equazioni di Navier-Stokes (altro problema del millennio).

Alla prox

Goldbach e il metodo del cerchio - PARI/GP e la risoluzione delle equazioni - il crivello di Dirichlet

2010-07-09T11:58:00.000-07:00

La congettura di Goldbach è un tema tipico della Teoria dei Numeri, che facilmente attira tutti gli appassionati di Matematica, anche per la sua facilità di comprensione e per la semplicità della definizione del problema, ma è un problema solo apparentemente semplice e ve ne renderete conto nel seguito.

Fin quando si rimane in ambito algebrico, geometrico, di matematica elementare e per bassi valori di interi, allora apparentemente sembra una congettura dimostrabile e vera. Se la congettura, invece, è affrontata in ambito analisi complessa, allora si scoprono ulteriori problematiche che possono mettere in crisi le dimostrazioni elementari trovate. Il metodo del cerchio è una tecnica nata negli anni '20 ad opera di Hardy, Littlewood e Ramanujan, utilizzata per i problemi additivi; successivamente migliorata da Vinogradov.

Un articolo a tal proposito è presente su:
http://www.gruppoeratostene.com/articoli/Cerchio.pdf

http://www.rudimathematici.com/Bookshelf/notes/Cerchio.pdf

Il secondo articolo che vi presentiamo nasce per mostrare l'utilizzo di PARI/GP per la risoluzione di vari tipi di equazioni o sistemi di equazioni: le congruenze lineari, i sistemi di congruenze lineari, le equazioni diofantee, l'equazione di Pell, una equazione di grado N etc. Ovviamente vengono mostrati anche dei sorgenti didattici con PARI/GP (sulla sezione software di www.gruppoeratostene.com).

Il link dell'articolo è http://www.gruppoeratostene.com/articoli/AEQ.pdf

Il terzo articolo mostra come nasce un crivello o setacciatore di numeri primi, a partire dal problema dei divisori di Dirichlet.

Il link è http://www.gruppoeratostene.com/articoli/PDC.pdf

Alla prox.

Calcolo degli zeri della zeta di Riemann

2010-06-12T00:55:00.000-07:00

Calcolo degli zeri della zeta di Riemann

Viene presentato un lavoro di calcolo numerico sulla zeta di Riemann a seguito di tanti appassionati che hanno chiesto via mail come si calcolano gli zeri della zeta di Riemann.

Ne è nato un articolo abbastanza corposo di tali tecniche, spiegate soprattutto in modo intuitivo e dando la possibilità a chi voglia sperimentare di scaricarsi anche il software (da eseguire con PARI/GP) dal sito www.gruppoeratostene.com (sezione Software).

L'articolo, invece, è stato pubblicato sia da www.gruppoeratostene.com che da RudiMathematici ai link:

http://www.gruppoeratostene.com/
http://www.rudimathematici.com/blocknotes.htm

P.S: segnalateci se è stato di vostro gradimento o anche se avete software sviluppato da voi in PARI/GP sull'argomento per mostrarlo ad altri lettori e discuterne.

Alla prox

Serie degli inversi dei primoriali e fattoriali

2010-05-28T22:46:00.000-07:00

La convergenza di una serie è un problema classico di matematica.

Un modo semplice per "sondare" la serie e stabilire se è convergente o divergente è quello di concentrarci sulla somma S della serie ed usare in PARI/GP le funzionalità suminf oppure sum; in tal modo aumentando il numero di elementi considerati si ha una indicazione sulla serie e la somma S.

In alcuni altri casi la sola suminf o la sum non è sufficiente e occorre scrivere un piccolo programma.

Primoriali

Un primoriale p# è uguale al prodotto dei numeri primi, a partire da p, con tutti i numeri primi precedenti.

Se vogliamo avere una indicazione sulla somma S della serie degli inversi dei primoriali,
possiamo scrivere il seguente programma:

SerRevPrimorial(n) = local(S=0,P=1);{

forprime(i=2,n,
     P = ProdPrime(i);
     S = S + (1/P) * 1.0;
);
return(S);
}

ProdPrime(v)= local(p=1);{

forprime(i=2,v,
          p = p * i;
);
return(p);
}

Se lo eseguiamo, otteniamo:

? SerRevPrimorial(1)
%35 = 0
? SerRevPrimorial(2)
%36 = 0.5000000000000000000000000000
? SerRevPrimorial(3)
%37 = 0.6666666666666666666666666667
? SerRevPrimorial(5)
%38 = 0.7000000000000000000000000000
? SerRevPrimorial(7)
%39 = 0.7047619047619047619047619047
? SerRevPrimorial(11)
%40 = 0.7051948051948051948051948052
? SerRevPrimorial(100)
%41 = 0.7052301717918009651474316828
? SerRevPrimorial(1000)
%42 = 0.7052301717918009651474316828
? SerRevPrimorial(10000)
%43 = 0.7052301717918009651474316828

Si osserva che già da p=7 si ottiene che la serie degli inversi dei primoriali converge al valore
0.7047619047619047619047619047, valore leggermente minore della metà della radice quadrata di 2 o del seno di Pigreco/4.

Fattoriali
Se vogliamo, invece, avere indicazioni sulla serie inversa dei fattoriali il programmino è del tipo:

SerRevFactorial(n) = local(S=0,P=1);{

for(i=0,n,
     P = i!;
     S = S + (1/P) * 1.0;
);
return(S);
}

Dobbiamo tenere conto anche che 0!=1.

Se lo eseguiamo, otteniamo:

? SerRevFactorial(0)

%4 = 1.000000000000000000000000000

? SerRevFactorial(1)

%5 = 2.000000000000000000000000000

? SerRevFactorial(2)

%6 = 2.500000000000000000000000000

? SerRevFactorial(3)

%7 = 2.666666666666666666666666667

? SerRevFactorial(4)

%8 = 2.708333333333333333333333333

? SerRevFactorial(7)

%9 = 2.718253968253968253968253968

? SerRevFactorial(1000)

%10 = 2.718281828459045235360287471

Anche qui la serie converge ad un valore già da n=7, ovvero al valore 2.7182818284590452353602874712
che è il numero di Nepero e.

Alla prox

Persiani amichevoli

2010-05-14T13:06:00.000-07:00

Persiani amichevoli

Esiste un legame tra numeri primi e numeri amicabili? Abbiamo visto che i numeri primi hanno solo due divisori diversamente da una coppia di numeri amicabili.

Un quesito: Un numero amicabile è solo pari? Sapreste dimostrare se è vero o falso?

Mentre meditate, vi dico che sicuramente un numero amicabile è composto, perchè ammette un numero di divisori maggiore di 2 e, quindi, scomponibile in numeri primi.

Altra domanda: dati tre numeri primi p,q,r possiamo ottenere dei numeri amicabili?

Al-Faris, vissuto in Persia attorno al 1300, nel suo testo sulle coppie amicabili, fornì la coppia (2^k)pq, (2^k)r, che è amicabile se e solo se:

p = (3*(2^(k-1)))-1,
q = (3*(2^k))-1
r = 9*(2^(2k-1))-1

sono tutti numeri primi, per k maggiore o uguale a 2.

E' evidente, per la definizione di Al Faris su come trovare i numeri amicabili tramite tre primi, che si tratta di potenze di 2 (pari) moltiplicate per dei dispari, il cui risultato è obbligatoriamente un pari.

Se si fissa k=2, si ottiene ad esempio p=5, q=11, r=71 tutti primi e quindi la coppia amicabile 220 e 284.

Per vedere quali coppie di numeri sono amichevoli con p,q,r primi è possibile scrivere un programmino in PARI/GP o in MAXIMA. In realtà si potrebbe tentare anche di risolvere un sistema di equazioni.

Il metodo di Al-Faris però non dà tutte le coppie di numeri amicabili, ma solo quelle ottenibili con le condizioni di cui sopra (vedi lista amichevoli noti http://amicable.homepage.dk/knwnc2.htm).

Ad esempio sono amichevoli anche le coppie (1184,1210) (2620,2924) (5020,5564) (6232,6368) che storicamente furono trovate da Eulero. Oggi il totale di coppie note, grazie ai computer è notevole: un totale di circa 11994387 coppie e si continua a trovarne altre.

Ecco un semplice programma in PARI/GP che sfrutta l'algoritmo di Al-Faris.
Samic(n1=2, n2=1000)=local();{
if( n1<2, error("deve essere n1>=2"););
for(k=n1,n2,
     p=(3*(2^(k-1)))-1;
     q=(3*(2^(k)))-1;
     r=(9*(2^(2*k-1)))-1;
     if(isprime(p) & isprime(q) & isprime(r) == 1,
         N=(2^k)*(p*q);
         M=(2^k)*r;
         print("(",N,",",M,")");
     );
);
print("Numeri esaminati ", n2-n1+1 );
return;
}

Ecco cosa fornisce con k tra 2 e 1000:
(220,284)
(17296,18416)
(9363584,9437056)

Vi do adesso la risposta al quesito iniziale: è falso. Esistono anche coppie di numeri amichevoli dispari e coppie di numeri amichevoli pari; ma non si trovano miste, ovvero uno pari e l'altro dispari. E' dimostrabile?
La lascio a voi la dimostrazione. Un suggerimento: partite dalla somma dei divisori (escluso se stesso) di un numero amichevole pari; che cosa vi da e perchè?

Altre osservazioni

1. Nessun numero amichevole è un quadrato

2. Esistono coppie di numeri amichevoli la cui somma delle cifre è uguale (mod 9); esempio:

(69615,87633) da cui 6+9+6+1+5 = 27 e 8+7+6+3+3 = 27

il mod 9 = 0 per entrambi

3. Esistono coppie amichevole che ogni numero è divisibile per la somma delle sue cifre; esempio:

(2620, 2924). Qui 2+6+2+0=10 difatti 2610 è divisibile per 10; mentre 2+9+2+4=17 e 2924 è

divisibile per 17. Un numero divisibile per la somma delle sue cifre è detto Harshad number;

per cui la coppia amichevole è una Harshad amicable pair (HsAP).

Esempi sono le coppie:

(2620, 2924)

   (10634085,14084763),
     (23389695, 25132545),
     (34256222, 35997346)
   etc.

4 Spesso i numeri amichevoli di una coppia terminano con 0 e 5.

5 Il rapporto minimo n/m con n minore di m è tra 0.598343 e

0.999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998

6. Un Happy number è un numero tale che prendendo il quadrato delle sue cifre e sommandole e iterando il

processo si ottiene alla fine 1. Ad esempio prendiamo 7, si ottiene la sequenza:

7,7x7=49,4x4+9x9=97,9x9+7x7=130,1x1+3x3=10,1x1=1.

Le coppie di numeri amichevoli che sono costituite da Happy number sono definite Happy amicable

pair (HyAP)

Esempi sono le coppie:

     (10572550, 10854650),
     (32685250, 34538270),
     (35361326, 40117714),
     (35390008, 39259592)

     etc.

Algoritmo che cerca tutti i numeri amichevoli
Un algoritmo semplice che cerca, invece, tutti i numeri amichevoli può essere come quello che segue

Allamic(n1=2, n2=1000)=local(s=0, prec1=0);{
if( n1<2, error("deve essere n1>=2"););
for(k=n1,n2,
     s=AlqSum(k);
     if( AlqSum(s) == k && k! = s & k != prec1,
         print("(",k,",",s,")");
         prec1=s;
    );

);
print("Numeri esaminati ", n2-n1+1 );
return;
}

AlqSum(n)=local(ret=1);{
vec = divisors(n);
ret = sum(i=1, length(vec)-1, vec[i] );
return(ret);
}

Alla prox.

Parti aliquote e successioni aliquote

2010-05-01T00:00:00.000-07:00

Parti aliquote e successioni aliquote

Definiamo con s(n) la somma dei divisori (parti aliquote) di n, escluso n.

Si definisce n numero perfetto se s(n) = n, oppure numero abbondante se s(n)>n, difettivo se s(n)<n

Si definisce "successione aliquota", invece, la successione dei valori di s(x), arrestandosi a s(x)=0,che si ottiene nel seguente modo:

s(n) = k
s(k) = m
s(m) = ... etc

Esempio
s(15)=1+3+5=9, s(9)=1+3=4,s(4)=1+2=3,s(3)=1,s(1)=0

Nota: L'arresto a s(x)=0 è perchè infiniti numeri sono divisibili per 0.

Classi di comportamento
Ogni successione aliquota potenzialmente potrebbe ricadere in una delle seguenti classi di comportamento:
1. termina a 0
2. finisce in un ciclo, di lunghezza 1, di lunghezza 2 o maggiore
3. potrebbe crescere all'infinito

Successioni che terminano a 0
E' il caso dell'esempio di cui prima.

Successioni di lunghezza 1
I numeri perfetti hanno tale caratteristica. Ad esempio s(6)=6, s(28)=28, etc.

Congettura sui numeri perfetti
Si ipotizza che sono infiniti.

Successioni di lunghezza 2
I numeri amichevoli hanno questa caratteristica. Due numeri amichevoli a e b sono così definiti perchè la s(a)=b e s(b)=a.

Ad esempio la più piccola coppia di numeri amichevoli è (220,284).

Congettura sui numeri amichevoli
Si ipotizza che sono infiniti.

Liste di numeri amichevoli
http://djm.cc/amicable.txt
http://amicable.homepage.dk/knwnap.htm

Successioni di lunghezza maggiore di 2
I numeri che danno luogo a sequenze di lunghezza maggiore di 2 sono detti numeri socievoli

Lista di numeri socievoli
http://djm.cc/sociable.txt

Congettura di Catalan e Dickson
Tale congettura ipotizza che tutte le sequenze aliquote a partire da un valore n intero terminano nelle prime due classi di comportamento e mai crescendo all'infinito.

La congettura non è ancora provata e attualmente anche a livello di test al computer finora non si sono completamente testate tutte le situazioni. Ad esempio una di queste è n=276.

Recentemente si sta mettendo in dubbio la congettura, ovvero si è convinti, sempre come congettura da dimostrare, che in realtà anche la classe di comportamento 3 è possibile (vedi [GUY1977] R. K. Guy, Aliquot sequences, in Number Theory and Algebra (Academic Press, 1977).

Se vi va, trovate un controesempio e avrete posto fine alla congettura di Catalan e Dickson!

Problemi correlati
Sfruttando la tecnica delle parti aliquote e modificandone la funzione in gioco si possono costruire altri tipi di numeri.

Definiamo s+(n) = s(n) + 1

Tutte le potenze di 2 sono di questo tipo e di lunghezza 1 (numeri quasi perfetti).
Esistono anche sequenze s+ di lunghezza 2, dette "coppie amichevoli quasi perfette"; mentre per lunghezze maggiore di 2 si parla di "numeri sociali quasi perfetti".

Vedi:
http://djm.cc/augmented.fmtlist
http://djm.cc/augsoc.fmtlist

Analogamente definiamo s-(n) = s(n) - 1

otterremo numeri definiti nel seguente modo:
numeri ridotti perfetti o quasi perfetti
numeri ridotti amichevoli o quasi amichevoli (o numeri fidanzati)
numeri ridotti socievoli o quasi socievoli

Vedi:
http://djm.cc/reduced.fmtlist
http://djm.cc/redsoc.fmtlist

Nuove ricerche da fare
Potremmo definire ancora altre funzioni non ancora indagate

s*k(n)          = s(n)*k
s/k(n)           = s(n)/k con k tale che il risultato sia intero
s*k+m(n)     = s(n)*k + m
s/k+m(n)      = s(n)/k + m
s^k(m)         = s(n)^k
s^k+m(n)     = s(n)^k + m

etc...
con k e m interi

Potreste provare a indagare sulle proprietà dei numeri in base a k e m e sulla sequenza.

Eccovi anche un algoritmo semplice con PARI/GP (da migliorare eventualmente) con cui un pò studiare le varie casistiche:

Alq(n,op="+",m=0,k=1) = local(ret=1, str="", str2="");{
str = concat(str,n);
str = concat(str,",");

i = 0;
retp = n;

while(ret!= 0,
       i++;
       vec = divisors(n);
       l = length(vec);
       retp2 = ret;
       ret = sum(i=1, l-1, vec[i] );

       if( op = "+", ret = ret*k + m; );
       if( op = "-", ret = ret*k - m; );
       if( op = "*", ret = ret*k + m; );
       if( op = "^", ret = ret^k + m; );

       if( retp == ret,
           ret = 0;
       );
       if( retp2 == ret,
           retp2 = -1;
           if( retp2==-1, str=concat(str,ret); str=concat(str," cycle"););
           ret = 0;
       );

       if( retp != ret & retp2 != -1,
           if(ret==0,   str= concat(str,ret););
           if(ret!=0,   str= concat(str,ret); str=concat(str,","););
           n = ret;
       );

       if( ret==0 & retp2 != -1, str = concat(str," - len = "); str=concat(str,i));
       if( ret==0 & i==1 & retp2 != -1, str = concat(str," - perfect number"););
       if( ret==0 & i==2 & l > 2 & retp2 != -1, str = concat(str," - amicable number");); /* Not prime number */
       if( ret==0 & i>2 & retp2 != -1, str = concat(str," - sociable number"););
);
print(str);
}

Ad esempio lanciabile come:
Alq(6)
Alq(12)
Individua i numeri perfetti, amicabili (escludendo i numeri primi) e i socievoli.

Sui cicli l'algoritmo lo potrete ovviamente migliorare perchè per semplicità quello presentato si arresta solo se due numeri consecutivi sono uguali, ma non individua sequenze ripetute con più di una cifra.

Ad esempio funziona con Alq(25) poichè si ripete 6, ma non funzionerebbe se si ripetono 4,7,2,4,7,2. Quindi va da voi migliorato.

Se invece si lancia con altre operazioni si possono ottenere cicli.
Ad esempio: Alq(12,"*",1,1)

Se si vogliono gestire elevati numeri di cifre, conviene riscrivere il programma con GMP; altrimenti PARI/GP si interrompe laddove non è in grado di proseguire..

Alla prox

Numeri ciclici ed un po' magici

2010-04-24T01:09:00.000-07:00

Numeri ciclici ed un po' magici

Alcuni numeri hanno una proprietà caratteristica. Prendiamo ad esempio 142.857.

E' un numero come un altro a prima vista. Ebbene se si moltiplica per un valore si ottiene un numero al cui interno si ripresenta il numero di partenza con cifre nello stesso ordine.

Se poi a tale risultato si moltiplica ulteriormente, il numero di partenza si ripresenta con cifre shiftate in modo circolare.

Ecco degli esempi:

142.857 x 2 = 285.714 142.857 x 5 = 714.285

142.857 x 3 = 428.571 142.857 x 6 = 857.142

142.857 x 4 = 571.428 142.857 x 7 = 999.999

E' facile osservare che le 6 cifre del numero compaiono, tra l’altro nello stesso ordine, anche nei risultati. Moltiplicando il numero magico per 7 si ottiene invece 999.999.

Disponendo le cifre in cerchio e iniziando a leggere in un punto qualsiasi procedendo in senso orario si ottiene sempre un numero multiplo di 142.857: ecco perché questo viene chiamato numero ciclico.

Forse avete anche osservato che sommando le due cifre opposte nella disposizione circolare si ottiene sempre 9.

Ad esempio spezziamo il numero in due parti uguali, e scriviamole incolonnate:

142
857

Cosa si nota ? Sommando le cifre in posizione corrispondente, si ottiene sempre 9: 1 + 8 = 4 + 5 = 2 + 7 = 9.

Ciò vale anche per tutti i multipli, eccetto ovviamente quelli caratteristici dati dal primo generatore e suoi multipli!

Queste proprietà appartengono a tutti i numeri ciclici.

Alcuni di essi si possono generare con frazioni periodiche.

Ad esempio 142.857 è il più piccolo di questi numeri ciclici e si ottiene dividendo 1 per 7 e considerando le prime 6 cifre decimali del periodo.

Un altro numero di questo genere si ottiene dividendo 1 per 17:
si tratta esattamente di 588.235.294.117.647.

Dividendo 1 per 97, invece, si ottiene un numero ciclico di ben 96 cifre!

Un alro modo per generarli è secondo la formuletta C(p)=(b^{p-1}-1)/p

ove b è la base numerica prescelta e p è il numero primo dato, che non sia un divisore della base.

Ovviamente non ogni numero primo genera un numero ciclico.

In sintesi si definisce numero ciclico quel numero di n cifre in base b che ha le seguenti caratteristiche:
1 moltiplicato per un numero da 1 a n, dà come risultato un numero che contiene le stesse cifre del numero di partenza, in ordine traslato
2 moltiplicato per n+1, dà come risultato una sequenza di n cifre b-1 (ovvero b^n-1)
3 sono caratterizzati dall'essere sempre espressi con p - 1 cifre, il che spiega la loro strettissima correlazione con la rappresentazione e quindi la base numerica prescelta

Alla prox

Teoria dei numeri - Il problema di Riesel e di Sierpinski

2010-04-18T00:34:00.000-07:00

Il problema di Riesel e il problema di Sierpinski

Nella teoria dei Numeri si definisce numero di Riesel un valore k dispari tale che, per ogni n,
il termine k*2^n-1 è un numero composto.

Nel 1956 Hans Riesel dimostrò che esistono infiniti numeri di Riesel, con una tecnica di "insieme ricoprente".

Un insieme ricoprente è un insieme di numeri primi piccoli tali che ogni termine di una successione sia
divisibile per uno di essi (da qui il nome di "ricoprente").

In base a tale tecnica Riesel mostrò che 509203 era un numero di Riesel.

Poichè finora non è stato trovato nessun insieme ricoprente per valori di k inferiori a 509203, si ipotizza
che esso sia il più piccolo numero di Riesel.

Il "problema di Riesel" è di determinare il più piccolo numero di Riesel.

Esempi
k=5 non può essere un numero di Riesel, perchè già con n=2 si ottiene che 5*2^2-1=19 è un numero primo.
k=509203 se lo si prova per 10 mila o 1 milione di valori di n non si ottiene un primo; ad esempio di fatti
con PARI/GP si possono scrivere due linee di comando del tipo:

a=509203
for(i=1,10000, b=a*2^i-1; if(isprime(b)==1,print("prime ",b," for n: ", i);); );

Il problema di Sierpinski
Tale problema è analogo a quello di Riesel. E' definito numero di Sierpinski un numero k dispari, che per ogni n, produce numeri composti k*2^n+1.

Qual è il più piccolo numero di Sierpinski? Nel 1962 John Selfridge propose come il più piccolo numero di Sierpinski 78557. Per dimostrare che esso è il più piccolo occorre dimostrare che i dispari precedenti non sono numeri di Sierpinski. Finora è stato dimostrato per tutti i numeri eccetto per diciassette di essi.

Ricerca algoritmica
Il progetto Riesel Sieve (analogo a Seventeen oppure Bust), progetto di calcolo distribuito, sta analizzando almeno 75 valori di k minori di 509203, che possono considerarsi PRN ("Probable Riesel's number").

Un interessante valore è il 659.

Un algoritmo proponibile in PARI/GP, per entrambi i problemi, che si può ulteriormente ottimizzare, è il seguente da me proposto.

/*
* Riesel's Number Research
* Sierpinski's Number Research
*
* Author   : Rosario Turco
* Date       : 16/04/2010
* Revision   : 1.0
*/

RSL(start=3, end=1001, s=1, n=1000, r=1)=local();{
if( start%2 == 0, error("inserire uno start dispari"););
i = start;
while(i
       RSLR(i,s,n,r);
       i = i+2;
);
print("start : ", start," end : ", end);
}

RSLR(val,s=1,n=1000,r=1)=local(out="",trovato=0); {
    for(j=s,n,
        if( r == 1,
            a = (val*2^j) - 1;
        );
        if( r == 0,
            a = (val*2^j) + 1;
        );
        if( isprime(a) == 1,
            trovato=1;
            print("Nok at n: ", j);
            j=n+1;
        );
     );

     if(trovato == 0,
        if( r == 1,
            out = concat( out, "Probable Riesel's number: k=");
        );
        if( r == 0,
            out = concat( out, "Probable Sierpinski's number: k=");
        );
        out = concat( out, val);
        out = concat( out, " on ");
        out = concat( out, n);
        out = concat( out, " values ...");
        print(out);
     );
}

Riferimenti
Wikipedia
http://www.seventeenorbust.com

Alla prox

Commenti sui lavori di matematica

2010-04-17T11:25:00.000-07:00

Commenti sui lavori di Matematica

Ho letto con attenzione vari commenti lasciati sul sito dell'amico e coautore dott. Michele Nardelli
http://nardelli.xoom.it/virgiliowizard/commenti

I commenti benevoli si riferivano spesso sia a lavori congiunti che del dott. Nardelli, mio ottimo amico e valido matematico, con un interesse specifico nell'ambito della teoria delle stringhe e della Fisica matematica.

Ringrazio i lettori, e vi segnalo i tantissimi lavori del dott. Nardelli ed il suo sito http://nardelli.xoom.it/

Aggiungo anche il sito del prof. Watkins dell'università Exeter
http://www.secamlocal.ex.ac.uk/people/staff/mrwatkin/zeta/tutorial.htm
su cui sono pubblicati articoli miei, della prof. Colonnese, del dott. Nardelli e del gruppo ERATOSTENE.

In ultimo vi segnalo articoli presenti sia sul sito www.gruppoeratostene.com

che sul sito Rudi Mathematici http://www.rudimathematici.com/blocknotes.htm

Ed un link del prof. Ignazio Licata (fisico teorico)
http://www.i-sem.net/profile/ignazio_licata.asp

Alla prox

Teoria dei numeri - Numeri di Keith inversi

2010-04-14T11:48:00.000-07:00

L'inverso del Repfigit? E' il revRepfigit!

Se i Repfigit sono strani e rari oltre il milione, ancora più strabilianti sono gli inversi. I numeri revRepfigit sono come il 12: la loro sequenza con la stessa tecnica dei Repfigit dà il rovescio di 12 ovvero 21.

Altri revRepfigit sono ad esempio:
12, 24, 36, 48, 52, 71, 341, 682, 1285, 5532, 8166, 17593, 28421, 74733, 90711, 759664, 901921, 1593583, 4808691, 6615651, 6738984, 8366363, 8422611, 26435142, 54734431, 57133931, 79112422, 351247542, 428899438, 489044741, 578989902, 3207761244, 4156222103, 5426705064, 5785766973, 6336657062, 48980740972, 51149725354, 83626284302, 94183600081, 98665175305, 1935391095868, 6002181268035, 6334708806271, 12348924235856, 27488180694681, 76365591939888, 309217509306732, 352062080376812, 714692062325732, 723735537269331, 2437358882180001, 6792079280704301, 62244424802562056, 203414193894268461, 217049132946408803, 415499563488189604, 561624665953167171, ... (Sloane's A097060; A. Vrba, pers. comm., Dec. 28, 2006).

Vedi anche http://mathworld.wolfram.com/KeithNumber.html

Ok. Le congetture da verificare sono almeno due (vedi blog precedente); ma le curiosità sono molte di più.

Ad esempio: esiste una proprietà di qualche tipo che ci permette di dire che un numero intero è Repfigit o un revRepfigit?Al momento occorre farsi la sequenza ... molti studiosi cercano la proprietà.

Seconda curiosità: esiste un modo per contare tali numeri in un intervallo da 1 a N? Una sorta di pi(N)?

Altra curiosità. A che possono servire?.

Nel frattempo che meditate, ho apportato una modifica all'algoritmo già presentato precedentemente in modo da permettere di gestire sia Repfigit che revRepfigit. Ottimizzazioni ulteriori sono possibili: le lascio ai volenterosi! Se riportate il tutto in linguaggio GMP e usate un bel dual core avete speranze di trovare nuovi record di Repfigit a 34 e oltre cifre ...

/*
*   Keith's numbers Research (Repfigit and RevRepfigit)
*   R. Turco
*   rep=1 if I search Repfigit
*   rep=0 if I search RevRepfigit
*
*/

KNRA(start=10, end=10000000, rep=1)=local();{

for(i=start,end,
      KNR(i,rep);
);

}

KNR(val,rep)=local(value=0,p=0,s="",str="", out="", m=0, j=0, s0=0, s1=0, s2=0, trovato=0); {

     s = concat(s,val);
     m = length(s);
     MyW=Vecsmall(s);
     MyW2=Vecsmall(s);

     v=vector(m);
     v2=vector(m);

     /* Reverse Vector */
     MyW2=RevVect(s,m);

     /* I calculate the sums */
     for( j=1,m,
          v[j] = MyW[j]-48;
          v2[j] = MyW2[j]-48;
          out = concat( out, v[j] );
          out = concat( out, "," );
          str = concat(str, v2[j]);
          s1 = s1 + v[j];
     );
     out = concat( out, s1 );
     out = concat( out, "," );
     v[1]=s1;

     /*
         I calculate the first value of the vector.
         This is important in the revRepfigit
     */

     value=GetValStr(s,m);

     /* I get the value of the reverse vector */

     s2=GetValStr(str,m);

     p=1;

     /* I search the Repfigit */
     if( rep == 1,

         while( trovato == 0 & s1
            p++;
            if( p>m, p=1;);
            s1 = 0;

            for( j=1,m,
              s1 = s1 + v[j];
            );
            out = concat( out, s1 );
            if( s1 == val, print("Repfigit trovato : ", val, " len : ", m); trovato = 1; print(out););
            if( s1 != val, out = concat( out, "," ););
            v[p] = s1;

        );
     );

     /* RevRepfigit */
     if( rep == 0 & (10 < s2) & (value%10)!=0,

         while( trovato == 0 & s1
            p++;
            if( p>m, p=1;);
            s1 = 0;
            for( j=1,m,
              s1 = s1 + v[j];
            );
            out = concat( out, s1 );
            if( s2 == s1, print("revRepfigit trovato : ", val, " len : ", m); trovato = 1; print(out););
            if( s1 != val, out = concat( out, "," ););
            v[p] = s1;
        );
    );
}

GetValStr(str,len)=local(val=0,weight=0);{
MyStr=Vecsmall(str);
weight=len-1;
for(k=1,len,
         val = (MyStr[k]-48)*(10^(weight)) + val;
         weight--;
);
return(val);
}

RevVect(str,len)=local(k=0,j=0);{
     MyWA=Vecsmall(str);
     MyWB=Vecsmall(str);

     k=len;
     j=1;
     while( k>0,
            MyWB[k]=MyWA[j];
            k--;
            j++;
     );
     return(MyWB);
}

Alla prox

Setacciatore di Repfigit

2010-04-12T11:38:00.000-07:00

Algoritmo per i numeri di Keith

Vi presentiamo un algoritmo piuttosto veloce, per la ricerca dei numeri Repfigit o numeri di Keith, che occupa poca memoria grazie ad una semplice tecnica di shifting ciclico su un vettore di dimensione pari agli m digit, che costituiscono un numero. Con esso potrete ritrovare tutti i valori oggi noti e tentare di spingervi sui Repfigit oltre i fatidici 34 digit ... vi servirà un pò di tempo però.

L'algoritmo eventualmente potrete modificarvelo anche per stampare su file i risultati. L'ho proposto anche su Wikipedia.

/*
*   Keith's numbers Research (Repfigit) - R. Turco
*
*/
KNRA(start=10, end=100000)=local();{
for(i=start,end,
      KNR(i);
);

}

KNR(i)=local(p=0,s="",out="",m=0,j=0, s0=0,s1=0,s2=0, trovato=0); {
     s = concat(s,i);
     m = length(s);
     MyW=Vecsmall(s);
     v=vector(m);
     for( j=1,m,
          v[j] = MyW[j]-48;

          out = concat( out, v[j] );
          out = concat( out, "," );

          s1 = s1 + v[j];
     );
     out = concat( out, s1 );
     out = concat( out, "," );
     v[1]=s1;

     p=1;
     while( trovato == 0 '&' s1 '<' i+1
            p++;
            if( p>m, p=1;);
            s1 = 0;
            for( j=1,m,
              s1 = s1 + v[j];
            );
            out = concat( out, s1 );
            if( s1 == i, print("Esempio trovato : ", i, " len : ", m); trovato = 1; print(out););
            if( s1 != i, out = concat( out, "," ););
            v[p] = s1;
     );
}

Teoria dei numeri - Numeri Repfigit o numeri di Keith

2010-04-11T02:01:00.000-07:00

Teoria dei numeri - Numeri Repfigit o numeri di Keith

Il nome deriva da "replicating Fibonacci digit" ed indica i "numeri riproduttori di Fibonacci".

Si definisce numero repfigit o numero di Keith un numero n intero, costituito da m digit d1d2...dm, che
si rigenera all'interno di una sequenza del tipo:

d1, d2, ..., dm, s1=d1+d2+d3+...+dm, s2=s1+d2+...+dm, s3=s2+s1+d3+...+dm, ...

Generalizzando si consideri la sequenza definita da:

sk = dk (k = 1, 2, …, m) e
sk= sum(i=1,m,sk-i) (k>m).

Se sk=n per qualche k, allora n è un numero riproduttore di Fibonacci o numero di Keith o numero repfigit.

Esempi di repfigit

n=47 m=2 digit
4,7,11,18, 29, 47

n=1537 m=4 digit
1, 5, 3, 7, 16, 31, 57, 111, 215, 414, 797, 1537

E' nel 1987, che Michael Keith ha introdotto il concetto dei numeri riproduttori di Fibonacci.

Nel 1987 il numero repfigit più grande conosciuto era un numero di 7 cifre, 7.913.837. Nel novembre 1989, fu scoperto 44.121.607 e nello stesso anno il dottor Googol trovò che i numeri 129.572.008 e 251.133.297 sono repfigit nell'intervallo definito tra 100 e 1.000 milioni. Oggi sono stati scoperti numeri di questo tipo molto più grandi.

Nella tab. seguente i numeri riproduttori di Fibonacci fino a m=5 cifre

m=2     14     19     28     47     61     75
m=3     197     742
m=4     1104     1537     2208     2580     3684     4788     7385     7647     7909
m=5     31331     34285     34348     55604     62662     86935     93993

Congettura di Keith
I numeri repfigit sono infiniti.

Altro problema
Esistono repfigit con m>34?

Riferimenti
La Magia dei numeri – Clifford Pickover – Sfide Matematiche
http://planetmath.org/encyclopedia/KeithNumber.html
http://it.wikipedia.org/wiki/Successione_di_Fibonacci#Voci_correlate (dove l'autore ha contribuito)

Teoria dei numeri - Bateman

2010-04-03T01:37:00.000-07:00

Teoria dei numeri - Bateman, zeta di Fibonacci e connessioni con la teoria delle stringhe
- La politica delle Cicale e delle formiche.

Siamo a Pasqua 2010, speriamo che sia un anno "buono" e benevolo per gli Informatici e per tanti lavoratori a rischio del posto di lavoro, che negli anni si sono sacrificati anche all'estero.

L'informatica non è un settore regolarizzato e specializzato come altri; ad esempio in edilizia un palazzo non lo può progettare ed eseguire uno qualsiasi! Nemmeno il geometra che, però, se iscritto all'albo può effettuare determinati tipi di lavori.

Oggi la moda di determinate aziende è di esternalizzare l'Information Technology, liberarsi degli informatici, perchè un costo per l'azienda; sembra quasi che quando ne hanno bisogno possano andare al supermercato a procurarseli (la commodity) acquistandosi anche prodotti buy, di moda e chiavi in mano (non ho mai conosciuto un prodotto buy che non si dovesse poi customizzare oppure che vada perfettamente d'accordo con i processi in essere dell'azienda).

Per i costi è più facile esternalizzare gli informatici verso società che in qualche modo negli anni tra mobilità, prepensionamenti, cassa integrazione e licenziamenti farà la "parte sporca". Che futuro per per tante famiglie italiane dal nord al sud? E' più facile distruggere che costruire in italia ...

Di solito accade che le forniture, a bassi costi, vengono fatte da ditte esterne con molti giovani, senza neanche un anno di lavoro oppure la gestione dei call center viene remotizzata, in un angolo qualsiasi della terra (India, Pakistan, Tunisia, Libia, etc) con scarsa qualità, fidelizzazione, sicurezza e riservatezza sulla fonia (voce) e i dati (fax, contratti etc). La mobilità del lavoro e non del lavoratore è un'arma a doppio taglio, che all alunga provoca disastri.

Non è la stessa cosa tra una situazione in cui il software viene fatto da un ragazzino, con contratto a progetto e assoldato per pochi spiccioli (e su cui spesso non viene richiesto nemmeno il certificato penale) o da un professionista del software (diplomato o laureato) e conoscitore delle esigenze della propria azienda. I dati trattati e gli strumenti, le metodologie ed il know-how devono essere nelle mani dell'azienda. Non esiste azienda senza informatica, ma soprattutto non esiste una azienda senza una informatica adatta a sè, cioè propria.

Il ragazzino bravo può fare sicuramente programmi per piccoli uffici, ma si hanno dei limiti per i sistemi enterprise end to end: non conosce bene tecnologie, metodologie (best practices), sicurezza e riservatezza, la necessaria qualità, i necessari test; ma soprattutto non conosce le logiche dei processi di business che sono legate all'azienda da almeno un ventennio, che sono quelle che le hanno permesso il prestigio raggiunto.

E' come se il software per l'analisi della staticità della vostro palazzo o di un ponte fosse affidato ad un ragazzino; oppure pensate al software biomedico che deve far funzionare le macchine per le operazioni a cui tutti noi oggi siamo abituati (perchè automatizzate e rese semplici) come cataratte, cuore o a tutto quello che deve garantire sicurezza umana (shuttle, computer, satelliti, sistemi di controllo). Per cui stiamo parlando di tempo di progettazione adeguati, qualità del software, sicurezza e riservatezza del personale, metodologia di progettazione, esecuzione di test di sistema, professionalità e skill.

Lo stesso dicasi per attività remote, complicate anche dalla differenza di lingua dove il costo tenderà comunque ad aumentare, perchè il processo di un progetto non può più essere light. Se è light ogni anomalia diventa un requisito non espresso da pagare, mentre se si scrivono tutti i dettagli possibili, i tempi di progetto e i costi aumentano.

Pensate che già attualmente i dati di traffico nazionale o internazionali compresi i vostri contratti ADSL, dei telefonini, delle linee, dei fax etc potrebbero essere gestiti, da persone a contratto a progetto o anche da sconosciuti remoti (In Tunisia, Libia, etc) dell'oriente o dei paesi arabi o di chissà quale paese.

I dati delle cause penali e civili o delle prove dei magistrati, procuratori e della polizia, se gestiti da ditte esterne, i cui dipendenti a contratto a progetto non hanno presentato nemmeno il certificato penale, potenzialmente potrebbero essere sotto gli occhi o le mani di persone poco raccomandabili.

Il remotizzare, poi, le attività (di supporto delle linee, ADSL, dei PC, call center etc) significa dipendere dall'estero, come la benzina, l'energia elettrica etc. Oggi risparmieremo dei soldi, poi all'innalzarsi del tenore di vita dei paesi poveri aumenterà il costo, per conseguenza, mentre sarà sparito dal nostro paese la figura professionale dell'informatico ...

Qua il problema non è l'eta di chi fa l'informatica, ma il know-how specifico, la regolamentazione dell'informatica e di chi la fa, per i diversi settori strategici: telecomunicazioni, giustizia, polizia, settori medici, settori di controllo, etc.

Lo stesso titolo di studio, che dovrebbe comportare livelli di conoscenza e potenzialità diverse, non è ben utilizzato in italia e nelle aziende; nè è a priori incanalato in un adeguato sistema di insegnamento e di selezione sul mercato del lavoro ...Oggi come oggi lo studio non paga, non significa meritocrazia, non significa riuscire a contribuire ad avere il proprio paese tra i più tecnologicamente avanzati ...

Vi piacerebbe tutto questo? Eppure sta succedendo sotto i vostri occhi ... L'informatica, cari italiani, vi costerà, tra qualche anno, molto di più di oggi perchè oggi è bistrattata, resa inutile da strategie e leggi che poco hanno a che fare con la creazione di unn volano fonte di ripresa economica, e che hanno molto a che fare con la logica degli utili da restituire alle banche e agli azionisti. E soprattutto intere generazioni saranno distolte su altri settori se più redditizi: lo troveremo un informatico italiano in Italia? Forse siamo l'ultima razza, l'ultimo dei moicani ... Anche qui c'è una principessa Pocahontas da immolare sull'altare dell'avidità. Si ragiona solo con i numeri ? E' corretto nell'immediato ma, poi, è fallimentare alla lunga: ma per i manager è meglio l'uovo ricco oggi, che la gallina domani! E' questa è la differenza tra le cicale e le formiche.

Nel frattempo che medidate sulle miserie umane, indotte da leggi e politiche senza senso e all'italiana, in un'era dove tutto è automatizzato e serve l'informatica per questo, dove la privacy e la sicurezza sono determinanti e ciecamente si creano falle di sicurezza di gestione dell'informatica, vi presentiamo la congettura di Bateman ed un articolo legato alla zeta di Fibonacci.

Eccovi i link:
http://www.gruppoeratostene.com/articoli/Bateman.pdf

In più vi segnaliamo l'articolo che fornisce una connessione tra la zeta di Fibonacci e la teoria delle stringhe:
http://www.gruppoeratostene.com/articoli/Fibonacci%27s%20zeta%20function.pdf

Un augurio di Buona Pasqua.

L'infinito, Andrica, Cramer, la gravità ...

2010-03-04T13:49:00.000-08:00

Piace a chiunque filosofeggiare sull'infinito, sulla correttezza della matematica o meno.

L'infinito e l'infinitesimo non sono dei numeri ma dei concetti. L'infinito viene considerato come un NaN="Not a Number" in qualsiasi linguaggio di programmazione ed ora anche in matematica. L'infinitesimo?
Lo stesso: è il più piccolo numero reale (più esattamente razionale o irrazionale) rispetto a qualsiasi altro numero che stiamo trattando nel nostro contesto.

Eppure essi portano a delle contraddizioni. I limiti, le derivate, gli integrali e le serie sono basati su questi concetti di infinito ed infinitesimo, che furono ideati tra il '600 e il '700, quando molte altre cose non erano state rigorosamente definite e dimostrate.

Eulero trattava l'infinito come una quantità finita e arrivava stupendamente a risultati validi. In realtà infinito e infinitesimo sono concetti risalenti ai greci quando Euclide sosteneva che "la parte è più piccola del tutto". Gli arabi "sopravvalutarono" le cose intendendo che il "tutto" fosse l'1 e la "parte" le sue frazioni. Oggi è nata una parte della matematica chiamata "Analisi non standard" dovuta a Robinson (1966).

Un buon articolo è al link: http://www.gruppoeratostene.com/articoli/ANS.pdf

Esistono congetture sottovalutate della Teoria dei Numeri che se dimostrate, producono un "effetto domino" di dimostrazione a catena. Una di questa è la congettura di Andrica, che se ben impostata, dimostra rapidamente anche la congettura di Cramer. Buoni link sono:

http://www.gruppoeratostene.com/articoli/Andrica2.pdf
http://www.gruppoeratostene.com/articoli/Cramer.pdf

La congettura di Andrica fa nascere, inaspettatamente, anche un'altra teoria:"Due numeri primi consecutivi, ad eccezione ad esempio di numeri primi come 23 e 29, se appartengono a intervalli quadratici distinti I = [n^2, (n+k)^2], con k maggiore di 1, la loro differenza D non è mai sia pari che multiplo di 3 (ovvero D=6k con k>1). Poichè ciò è vero la congettura di Andrica è vera (la differenza delle radici quadrate di due numeri primi consecutivi è sempre minore di 1); il che comporta che R(p), il rapporto di Cramer-Shank, è minore di 1.

Oggi la gravità è un altro tema importante. Il tema dell'anti-gravità se ben sfruttato e studiato potrebbe aprire nuove aspettative in campo spaziale per la creazione di propulsioni nuove, oppure a immaginare "scudi antigravitazionali" per la terra, per respingere masse meteoritiche minacciose o altro. Ammesso che si arrivi a forze in gioco tali da avere una tale fattibilità.

La gravità è sempre stata un tema di studio e di discussione e poichè deve essere valida sia nel mondo macroscopico e cosmologico che nel mondo microscopico e della quantistica, allora deve esistere un modello unificatrice della relatività e della quantistica che contenga anche la gravità. La teoria di Burkhard Heim oggi ha un grande interesse, tale da rivaleggiare anche con la teoria delle stringhe.

Un buon articolo è al link:
http://www.gruppoeratostene.com/articoli/Heim.pdf

Alla prox

La congettura EUTF

2010-02-06T11:36:00.000-08:00

La congettura EUTF

Il problema della ricerca delle soluzioni intere di una equazione a più variabili, tutte dello stesso grado n, è
un problema classico, che coinvolge le equazioni diofantee, l'ultimo Teorema di Fermat etc.

L'Ultimo Teorema di Fermat (UTF) afferma che l'equazione x ^ n + y ^ n = c ^ n, con n>2, non ammette
soluzioni intere .

Una possibile estensione dell UTF potrebbe essere la Congettura EUTF e da dimostrare:

Congettura EUTF
"L' equazione x1^n + x2^n + x3^n + +xk ^n = c ^n ammette sempre soluzioni intere se e solo se n = k".

La congettura ipotizza che si otterrebbero sempre soluzioni intere se il numero di variabili (o dimensioni) è
uguale al grado n dell'equazione.

Il nome EUTF deriva dal fatto che la congettura rappresenta una estensione dell'UTF; in particolare se è vera la congettura EUTF, di conseguenza, è vero anche l'UTF, già dimostrato da Andrew Wiles; l'EUTF sarebbe, in altri termini, un ulteriore percorso dimostrativo dell UTF.

Nell'articolo al link http://www.gruppoeratostene.com/articoli/Eqrt.pdf sono mostrate le evidenze e gli eventuali percorsi di dimostrazione dell'EUTF.

Se qualche lettore vuole cimentrasi sulla dimostrazione ... è il benvenuto.

Alla prox

La zeta di Fibonacci

2010-01-23T10:43:00.000-08:00

La zeta di Fibonacci

Fra le serie di grosso interesse non c'è solo la zeta di Riemann. In realtà è possibile studiare qualsiasi serie inverso di determinati valori numerici generabili con una formula. Se i valori generabili sono i numeri di Fibonacci, allora traslando il tutto nel piano complesso, possiamo lavorare con la zeta di Fibonacci, definita come:

F(s) = suminf(k=1, 1.0/(fibonacci(k)^s))

Tale serie è di interesse sia per indagare nuovi metodi, sia per la sua somiglianza alla zeta di Riemann.

Essa è oggi studiata soprattutto nel mondo orientale; ed è difficile trovare su INTERNET materiale e informazioni su tale argomento, se non su libri da acquistare o su articoli tecnici riservati e a pagamento.

Un articolo libero per farvi rendere conto della problematica è al link:
http://www.gruppoeratostene.com/articoli/ZFRT.pdf

Buona lettura.

Guazzabugli palindromi

2010-01-20T13:16:00.000-08:00

Guazzabugli palindromi

Sia a = (10^n+1)^k, con n>0 e k>0

I quesiti che ci poniamo sono:

1 che tipo di numero è a per ogni n e k?
2 quale è il numero di cifre nc che si ottiene?
3 nc dipende da n o da k?
4 quanto vale "a" senza fare calcoli, esiste
una regola?

Un metodo di indagine è quello numerico che aiuta subito a farsi delle idee. Per cui scriviamo qualche
riga di comando su PARI/GP del tipo:

k=1
for(n=1,4,a=(10^n+1)^k;if(isprime(a)==1,print1("Yes"));print(a));

poi variamo k e vediamo cosa otteniamo ripetendo le righe precedenti.

Scopriamo subito che possiamo rispondere alla prima domanda che possiamo ottenere numeri palindromi (non per tutti i valori di k) e non sempre numeri primi.

Un numero palindromo è un numero la cui metà è una versione riflessa rispetto ad un asse verticale. Se ad esempio scriviamo 10 e lo ribaltiamo in 01 e mettiamo insieme le cose otteniamo 1001 che è un numero palindromo.

Se usiamo la forma generatrice precedente per k=1 otteniamo:
11
101
1001
10001

E' n o k da cui dipende il numero di cifre nc? Nel seguito intendiamo con nc il valore del numero di cifre del primo numero che otterremo con n=1 e k fissato.

Ad esempio se poniamo k=2 e facciamo sempre variare n nel for tra 1 e 4 ci accorgiamo che dipende da k: nc = k+1.

Per k=2 otteniamo:
121
10201
1002001
100020001

121, il primo numero, è di nc=k+1=3 cifre difatti.

Per k=3 otteniamo:
1331
1030301
1003003001
1000300030001

Per k=4 otteniamo:
14641
104060401
1004006004001
10004000600040001

Per k=5 otteniamo:
161051
10510100501
1005010010005001
100050010001000050001

Da qui vediamo che la "palindromia" viene meno in alcuni casi a partire da k>4. Se nc è pari non c'è un valore centrale rispetto al quale c'è la riflessione. Se nc è dispari esiste un valore centrale o pivot.

Alcune regole che possiamo fissare sono le seguenti:

A) agli estremi esiste sia un 1 a destra che un 1 a sinistra.

B) il gruppo di zeri che appaiono sono n-1 ed il gruppo si ripete per ogni cifra non nulla per intervallarle. Se n=1 non ci sono zeri.

C) esiste una regola per passare dal numero ottenuto con n=1 e k=b al numero con n=1 k=b+1 in particolare si sommano le cifre del numero con n=1 e k=b aggiungendo alla fine un 1 a destra e sinistra

esempio n=1 e k=3
1 3 3 1

dalla destra:
3+1=4
3+3=6
1+3=4

numero ricavato:
1 4 6   4 1

D) esiste una regola per passare dal numero ottenuto con n=1 e k=b al numero con n=2 k=b
in particolare si aggiungono zeri in quantità pari a n-1

Esempio:
numero ricavato per n=1 e k=3
1   4   6   4   1
1 0 4 0 6 0 4 0 1

Esempi più complessi

n=1 k=4
1 4 6 4 1

n=1 k=5
Da destra è:
4+1=5
6+4=10 0 si scrive e si riporta 1
4+6=10 0 questa somma non si fa perchè nel caso nc dispari il pivot si somma una sola volta
1+4+1 il +1 è il resto del 10 precedente

1 6   1 0   5 1

Per n=1 e k=6
5+1=6
5+0=5
1+0=1
6+1=7
1+6=7

1 7 7 1 5 6 1

Per n=1 e k=7
6+1=7
5+6=11 1 si scrive e 1 di riporto
1+5+1=7
7+1=8
7+7=14 4 si scrive e 1 di riporto
1+7+1=9

1 9 4 8 7 1 7 1

Convinti?

Se vogliamo poi vedere quali sono numeri primi, nel caso che dobbiamo lavorare su molti numeri, allora vi consiglio di farli stampare prima su file da PARI/GP e poi usare WinPFGW.

Alla prox.

Numeri primi e WinPFGW

2010-01-19T11:19:00.000-08:00

Numeri primi e WinPFGW
La prima cosa è scaricare il programma da INTERNET al link che vi ho segnalato al blog precedente; unzippare il tutto in una cartella e lanciare l'eseguibile WinPFGW.exe col click del mouse.

La prima cosa da imparare sono i comandi che possiamo digitare sulla "command line". Clicchiamo su Help, poi su Contents, poi mettiamo il check in Pfgwdoc.txt, clicchiamo su Print e stampiamo sul Desktop un file
di tipo .xps che chiamiamo Help. Otterremo un documento di help da consultare.

Un primo esempio di uso sono le "query" col comando -q, per verificare la primalità di un numero.
Verifichiamo ad esempio se è primo il numero 1+3*10^5825+100^5825. Scriviamo nella "command line" la riga:

-q1+3*10^5825+100^5825

e premiamo Start. Scopriremo che è un 3-PRP (un probabile primo). Se vogliamo salvare il nostro lavoro in append ad un file di nome work.txt scriveremo invece:

-q1+3*10^5825+100^5825 -lwork.txt (Vedi figura).

Se, invece, abbiamo molti numeri da fargli valutare apriamo un file di nome pfgw.txt nella stessa directory.
Usiamo ad esempio WordPad come editor e scriviamo:
2^3-1
2^31-1
3
7
6
e salviamolo

A questo punto lasciamo vuota la "command line". WinPFGW esaminerà il file e produrrà un file denominato pfgw-prime.txt dove metterà solo i numeri primi.

Di solito il file potrebbe essere generato da un Programma in PARI/GP. Ad esempio potremmo scrivere un file pfgw.txt che al variare di i da 1 a 100 calcola (10^i-1)^2 e siamo interessati a vedere quali sono i numeri primi. Il file prodotto lo dobbiamo però aprire prima in WordPad, che riconosce i "carriage return" di PARI/GP, e salvarlo. A questo punto il file lo possiamo dare in pasto a WinPFGW per controllare la primalità dei numeri prodotti. Semplice no?

Gli altri comandi e possibilità sperimentatele col doc di help.

Alla prox

Numeri primi: tools e linguaggi

2010-01-18T13:23:00.000-08:00

Numeri primi: tools e linguaggi
Lo studio della Teoria dei Numeri, richiede non solo la conoscenza della teoria, ma anche sperimentazione numerica. Spesso essa è fatta con tools scaricabili da INTERNET, realizzati da gruppi internazionali di studio, oppure implementabili con le proprie mani con un linguaggio matematico adeguato. Vi segnalo una serie di risorse indispensabili, a volte free e ottenibili da INTERNET.

Per i linguaggi il problema fondamentale è disporre di un linguaggio capace di trattare numeri con moltissime cifre, possibilmente senza limiti molto bassi sul numero di cifre e con una ottima velocità di esecuzione. Se non ha questa caratteristica lo sforzo per programmare non vale la candela. A volte sono necessari computer a 64 bit, ma nella maggior parte dei casi è sufficiente un linguaggio con adeguate librerie software (e un PC a 32 bit), che permetta di trattare tali numeri, anche se, spesso un pò a discapito della semplicità e della chiarezza, a causa delle funzionalità fornite dalla libreria. Ovviamente se l'obiettivo è di grande valore la difficoltà passa in secondo piano. Sia i tools, sia i linguaggi che i CAS permettono grafici 2D e 3D (zeta di Riemann, grafici di funzione, etc).

Linguaggi consigliabili

- GMP Arithmetic without limitations
http://www.gmplib.org/

E' un linguaggio C-like, con una sua libreria che permette di poter lavorare con numeri interi di grosse dimensioni. Ha una ottima velocità di esecuzione, tale da essere superiore a tanti altri linguaggi (compreso PARI/GP), ma a discapito della chiarezza di programmazione. Lo preferisco quando mi è chiaro l'algoritmo, il problema o la congettura perchè l'ho provata, ad esempio, prima con PARI/GP, su numero di cifre più bassi.

Quando però si ha a che fare con numeri molto grandi, il tempo di elaborazione aumenta ed avere un linguaggio veloce e poi un PC veloce (frequenza di clock) aiuta molto. Spesso i programmi si possono compilare in modo da sfruttare al massimo anche l'architettura hardware disponibile (AMD, INTEL, etc)

Poi dipende anche dal problema che si affronta, se si può lavorare in parallelo, allora avere un PC del tipo Core 2 Quad o superiore e a 64 bit, questo ci migliora la qualità della vita!

Un avvertimento classico sulle congetture: attenzione che spesso le più belle congetture si infrangono su numeri di moltissime cifre! Non provatele solo su numeri bassi.

- PARI/GP
http://pari.math.u-bordeaux.fr/

E' un linguaggio di scripting di matematica che permette, grazie a molte funzionalità, di poter scrivere programmi di test per le proprie prove, congetture e calcoli. Spesso è preferibile realizzare prima l'algoritmo in PARI/GP, che richiede meno tempo, meno complicazioni e maggiore linearità per fare la verifica delle proprie idee, per poi realizzare successivamente il tutto con GMP per poter lavorare con numeri grandissimi, maggiore velocità e minor impegno di RAM.

- WinHugs
   http://www.haskell.org/haskellwiki/WinHugs

E' un linguaggio funzionale di programmazione, per chi è più attratto dalla notazione matematica come programmazione.Ha minori prestazioni rispetto ai primi due.

CAS
Poi esistono tool di calcolo e di grafica, definiti CAS=Computer Aided System, per calcolare derivate, integrali, espressioni etc. come:

- Maxima
http://maxima.sourceforge.net/
Eccellente

- R
http://www.r-project.org/
Eccellente

Motori
Esistono anche motori che permettono di valutare equazioni ed espressioni come quello Wolfram. La scelta di uno di essi dipende anche dal tipo di problema da affrontare.

Tools analisi numerica per recordman

I tools per l'analisi dei numeri primi, composti, di Mersenne, di Fermat, di Proth etc, sono quelli di maggiore fascino per i recordman.

Nel seguito vi segnalo dei siti, che di solito danno anche informazioni sull'utilizzo o sui numeri che può ricercare. In ogni caso vi consiglio un pò di pratica.

A che possono servire?
- a verificare se un numero è primo se non si dispone di un sito su cui verificare
- a creare liste di numeri che rispettano delle regole (palinfromi, formule, etc)
per dare la lista ottenuta in pasto ad un successivo tool per determinare se nella lista
c'è un numero primo

Ecco una lista molto valida, di tolls veri 'coltellini svizzeri' del ricercatore di matematica applicata o dell'informatico e del recordman:

- WinPFGW
http://www.fermatsearch.org/download.html

- NewPGen
http://primes.utm.edu/programs/NewPGen/

Se cerchiamo grandi numeri primi della forma kb^n +1 o kb^n -1; oppure coppie di numeri gemelli molto grandi, o di Sophie Germain primes, o una catena di lunghezza due. In poche parole è un 'setacciatore'. Può servire per creare liste di 'numeri candidati primi' di un certo tipo da sottoporre ad altri tools.

- Proth
http://primes.utm.edu/programs/gallot/
Implementazione del Teorema di Proth per la ricerca di primi nella forma Proth
Si può sfruttare NewPGen per creare una lista da dare in pasto poi a Proth

Teorema di Proth (1878): Sia N = k2^n + 1 with 2^n > k.   Se vi è un intero a tale che
    a^((N-1)/2) = -1 (mod N),
allora N is prime.

E' un test utile : si applica ai primi di Cullen, ai fattori di Fermat, ai primi della congettura di Sierpinski etc.

- Primeform
http://pages.prodigy.net/chris_nash/primeform.html#Download
Per trovare Probable Prime

- FermFact
http://www.fermatsearch.org
Per i numeri di Fermat

- Generalized Fermat Prime search
http://pagesperso-orange.fr/yves.gallot/primes/download.html

- Primo oppure New Primo
http://www.ellipsa.eu/
Primalità de numeri, Basato sulle curve ECPP

Alla prox

Fibonacci e dintorni

2010-01-03T04:04:00.000-08:00

Proseguiamo con qualche altra strabiliante cosa legata ai numeri di Fibonacci.

Triangoli pitagorici
Charles Raine trovò che se si considerano 4 numeri di Fibonacci di seguito Fk,Fk+1,Fk+2,Fk+3
e consideriamo un triangolo rettangolo con cateti a, b e ipotenusa c, allora è:

a=Fk*Fk+3
b=2*(Fk+1*Fk+2)
c^2 = a^2+b^2

esaminiamo ad esempio la sequenza di Fibonacci:
1,1,2,3,5,8,13,21,34,...

Se prendiamo ..3,5,8,13,...
a=3*13=39
b=2(5*8)=80
c=89

P. Simson, matematico scozzese, trovò invece che:

Fk-1Fk+1-Fk^2=(-1)^k

Catalan, invece, che:

2^(n-1)Fn = Sum(i=0,n,5^i* (n i) )

dove (n i) per semplicità di notazione è il coefficiente binomiale.

Lo so, la formula di Catalan vi ricorda i numeri primi di Mersenne! Purtroppo la primalità dei numeri di Mersenne non è legabile alla primabilità dei numeri di Fibonacci. Ad esempio se poniamo che:

n-1=p n=p+1 con p numero primo allora è:

2^p - 1 = [1/Fp+1 Sum ( i=0, p+1,5^i * (p+1 i) )] -1

Se 2^p - 1 = Mp è primo allora p è primo e non è vero il contrario.
Per i numeri di Fibonacci se l'indice è primo è primo anche il valore Fn.
Ora le domande sono:
1 Se Mp è primo è primo anche Fp+1?
2 Se Fp+1 è primo lo è anche Mp?

Risposta alla prima domanda: Non sempre .
La serie di Fibonacci è tale che
F(0)=0, F(1)=1 e F(k)=F(k-1)+F(k-2)
quindi:
1,1,2,3,5,8,13,21,34,...

Se p=3 Mp=7 primo allora Fp+1=F4=3 primo

Se p=5 Mp=31 primo allora Fp+1=F6=8 NON PRIMO! (contro-esempio)

Quindi non ha senso nemmeno la seconda domanda se non è verificata la prima.

Diversi contributi dell'autore sono su:
http://it.wikipedia.org/wiki/Successione_di_Fibonacci

In tale contributo c'è anche come la primalità di un numero di Mersenne è legata invece a quello di un numero di Fibonacci.

Alla prox

Giochiamo con i numeri di Fibonacci

2010-01-01T10:56:00.000-08:00

Iniziamo ad esaminare un tema apparentemente semplice ma che ha ancora vasti settori in cui indagare ulteriormente: i numeri di Fibonacci.

Numeri di Fibonacci classici
I numeri di Fibonacci sono i numeri della successione di Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21,. . . . . ciascuno dei quali, dopo il secondo è la somma dei due precedenti.

In generale è:
F(0)=0
F(1)=1
F(k)= F(k-1)+F(k-2)

I numeri di Fibonacci possono anche essere considerati come una funzione di numeri interi non negativi:
   n = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...
F (n) = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

La soluzione esatta in forma chiusa per questa funzione è chiamata "formula di Binet":

F (n) = (Phi ^ n - Phip ^ n) / sqrt (5) (per tutti intero n> = 0 oppure n <0),

dove

Phi = (1 + sqrt (5)) / 2 = 1,61803398874989484820 ... (Golden Ratio)
Phip = Phi Prime = (1 - sqrt (5)) / 2 = 1 - Phi = -1/Phi = -0,61803398874989484820 ...,

Poiché F (k) è un intero e l'entità delle Phip ^ n / sqrt (5) è inferiore a 1 / 2 per n> = 0,
una forma variante della formula è:

F(k) = ceil (Phi ^ n / sqrt (5)), n> = 0.

Se si dispone di un numero di Fibonacci si può calcolare il suo indice: k = indFib (F (k))

La formula è la seguente:
     indFib(k) = 0 if |k| < 1, altrimenti
     iindFib(k) = ceil (Log (sqrt (5) * abs( k )) / Log (Phi)).

Ad esempio, indFib (144) = 12. E' accurata se k è un numero di Fibonacci.

Un numero di Fibonacci si verifica con isFib (k)
Un numero di Fibonacci deve essere un numero intero e si deve ottenere un quadrato perfetto da 5 * x ^ 2 + 4 o 5 * x ^ 2 - 4.

I numeri di Fibonacci possono essere definiti anche per n negativi:
     F(–2*k) = –F(2*k) F (-2 * k) =-F (2 * k)
     F(–2*k – 1) = F(2*k + 1) F (-2 * k - 1) F = (2 * k + 1)

       n = ..., –6, –5, –4, –3, –2, –1, 0, 1, 2, 3, 4, 5, 6, ...
     F(n) = ..., –8, 5, –3, 2, –1, 1, 0, 1, 1, 2, 3, 5, 8, ...

La funzione continua analitica:
     Fe(x) = (Phi^x – 1 / Phi^x) / Sqrt(5),
passa attraverso tutti i numeri di Fibonacci, anche n = x (n positivo o negativo).

La funzione continua analitica:
     Fo (x) = (Phi ^ x + 1 / Phi ^ x) / sqrt (5),
passa attraverso tutti i numeri di Fibonacci di n dispari = x (n positivo o negativo).

La funzione continua analitica:
     Fib(x) = (1 + cos(x*Pi))*Fe(x)/2 + (1 – cos(x*Pi))*Fo(x)/2,
passa attraverso tutti i numeri di Fibonacci per ogni n = x (n positivo o negativo).

Questa ultima espressione può essere ridotta a:
     Fib(x) = (Phi^x – cos(x*Pi) / Phi^x) / sqrt(5)

Questa formula può anche essere usato per calcolare la funzione di Fibonacci generalizzata di una
variabile complessa.Ad esempio:

Fib (3 + 4 * i) = -5248.51130,72837,20182,8 ... -14195.96228,83530,10885,8 ... * i. * I.

E' pur vero che Fib (x 2) = Fib (x 1) + Fib (x).

Ad esempio Fib (3,6 + 4,7 * i) = Fib (2,6 + 4,7 * i) + Fib (1.6 + 4.7 * I).

Numeri complessi di Fibonacci
Un numero complesso di Fibonacci è un numero complesso z la cui parte reale Re(z) è un numero di Fibonacci F(k).

Ad esempio z=8-i è un numero complesso di Fibonacci perchè Re(z)=8=F(6).

Proprietà dei numeri complessi di Fibonacci

Il rapporto di numeri complessi di Fibonacci con k dispari e n > 0 è tale che:

[F(k) - n*i] / [F(k-1)-(n-1)*i] = [F(k+n)+i*(-1)^(n-1)] / [F(k+(n-1)]

dove F(k+n)=Sum(i=k+1,n-1,F(i))

Ad esempio:
(5 - i ) / 3-i = 8 + i / 5
(13 - i ) / 8-i = 21 + i / 13
(8 - 2i) / (5 - i) = (21 - i) / 13
(13 - 3i)/(8 - 2i) = (55 + i)/34 (13 - 3i) / (8 - 2i) = (55 + i) / 34

Per k pari e n > 0 la formula non vale per i numeri complessi ma solo per i numeri interi sostituendo 1 a i,
ovvero:

[F(k) - n] / [F(k-1)-(n-1)] = [F(k+n)+(-1)^(n-1)] / [F(k+(n-1)]

dove F(k+n)=Sum(i=k+1,n-1,F(i))

(8 - 1) / (5 - 1) = (13 + 1) / 8.
(13 - 2) / 8 - 1) = (34 - 1) / 21
(8 - 3)/(5 - 2) = (34 + 1)/21 (8 - 3) / (5 - 2) = (34 + 1) / 21

Legame con il triangolo di Tartaglia o con i coefficienti binomiali

Il triangolo di Tartaglia o di Pascal è noto. Ebbene se si considerano le diagonali che dall'alto a destra scendono verso sinistra si individuano i numeri di Fibonacci.

La relazione esistente è difatti:
Fib(n)= Sum(k=0,n-1,(n-k-1 k) ) = Sum(k=1,n,(n-k k-1) )

dove per semplicità la notazione (n-k-1 k) rappresenta un coefficiente binomiale

Teorema
Ogni numero di Fibonacci è un fattore di (un numero infinito di) numeri di Fibonacci successivi oppure ogni k-th numero di Fibonacci è un multiplo di F (k)". E' equivalente a dire matematicamente che:
Se Fib(k) = m allora Fib(n*k) = t con m|t

Si dimostra in due modi possibili:
1.mo modo:

Dai coefficienti binomiali

Fib(k)        = Sum(i=1,k-1, (k-i i-1) ) = m

Fib(n*k)    = Sum(i=1,n*k-1, (n*k-i i-1) ) = t

2.do modo:

Costruiamo una tabella mettendo x se il risultato m di m=Fib(k) non è un divisore di Fib(k) e * se lo è:

       i        3 4 5 6 7   8   9 10 11 12

Fib(i) 2 3 5 8 13 21 34 55 89 144

2=Fib(3) * x x * x    x   *   x   x   *

3=Fib(4) x * x x x    *   x   x    x *

5=Fib(5) x x * x x     x   x   *    x x

Proseguendo si vede ad esempio che:
- 2 è un fattore ogni 3 Fib(k)
- 3 è un fattore ogni 4 Fib(k)
- 5 è un fattore ogni 5 Fib(k)
etc

Teorema
I numeri di Fibonacci vicini non hanno fattori in comune oppure Fib (k) e Fib (k +1) sono coprimi.

Se Fib(k)=m*a   e Fib(k+1)=m*b per assurdo allora Fib(k+2)=Fib(k)+Fib(k+1)=m*(a+b)
Il che vorrebbe dire che tutta la serie di Fibonacci dovrebbe avrebbe lo stesso fattore m in comune,
il che non è vero.

=== Teorema di Vorob’ev ===

gcd( F(m), F(n) ) = F( gcd(m,n) )

Numeri di Fibonacci primi
Come corollario di prima, se l'indice di un numero di Fibonacci è un multiplo di k, il numero di Fibonacci è composto.

Se il numero di Fibonacci è un primo lo è anche l'indice.

Non è vero il contrario. Infatti ad esempio

F (19) = 4.181 e F (19) non è primo perché 113x37 = 4.181

Il più grande numero primo di Fibonacci F (81.839) è stato segnalato in aprile 2001 da David Broadbent e Bouk de Water.

La serie di numeri indice dei numeri primi di Fibonacci è A001605 Sloane

Numeri di Fibonacci e fattori primi speciali
Se guardiamo i fattori primi di un numero di Fibonacci, ci sarà almeno uno di loro che non è mai apparso come un fattore in ogni numero di Fibonacci in precedenza.

Questo è noto come teorema di Carmichael e si applica a tutti i numeri di Fibonacci, tranne casi particolari:

Fib (1) = 1 (non ha fattori primi),
Fib (2) = 1 (non ha fattori primi),
Fib (6) = 8, che ha solo il fattore primo 2, che è anche Fib (3),
Fib (12) = 144, che anche solo il 2 e 3, come i suoi fattori primi e questi sono apparsi in precedenza come Fib (3) = 2 e Fib (4) = 3.

Alla prox

Algoritmo antiperiodo di una frazione

2009-12-27T11:18:00.000-08:00

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

2009-12-27T02:12:00.000-08:00

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?

2009-12-18T08:09:00.000-08:00

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

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

2009-12-17T12:57:00.000-08:00

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