Irrazionali

[salva]

Abbiamo una sequenza S1 di punti lungo l'asse dei reali R con periodo
T, per semplicita' T=1, e cioe' la sequenza dei numeri interi Z, e
un'altra sequenza S2 con periodo sqrt(2). Le due sequenze giacciono
sulla stessa retta infinita.
Quanti elementi di una sequenza si sovrappongono ad elementi della
seconda ? Una sola volta.
Se il rapporto tra i periodi delle due sequenze fosse un razionale,
allora avremmo infinite sovrapposizioni lungo R.
A seconda del rapporto tra i periodi possiamo avere 1 sola o infinite
sovrapposizioni, non c'e' via di mezzo.
Consideriamo ora l'elemento nS1 (un elemento della sequenza S1 scelto
arbitrariamente) e l'elemento mS2, l'elemento di S2 piu' vicino a nS1.
Supponiamo che la distanza D tra i due elementi sia data, ma non
conosciamo n e nemmeno m.

Siamo in grado di identificare 0S1 e 0S2, i due elementi che
coincidono uno con l'altro ? e cioe' la distanza N tra nS1 e
0S1( cioe' l'elemento di S1 che coincide con un elemento di S2)
Si, ... ma come ? dove si trova 0S1, a destra o a sinistra ?

Perdonatemi ...

Salva

[salva]

Diciamo che :
m*sqrt2-n=D , ma
n=(floor)m*sqrt2, percio'
m*sqrt2-(floor)m*sqrt2=D , trovare m !!

A parte il modo di presentare questa osservazione, potrebbe essere
interessante utilizzare la relazione che c'e' tra la distanza D e la
posizione in cui i due termini si sovrappongono in criptografia.


>
> Perdonatemi ...
>
> Salva

[g.resta]

Ho paura che il problema sia piuttosto difficile.
Tra l'altro dovremmo disporre di D con un numero arbitrario di cifre
decimali,
perche' chiaramente m puo' anche avere un milione di cifre.

E' una cosa che avevo gia' visto in passato, ma purtroppo la memoria
mi fa cilecca.

Le parti frazionarie dei multipli di un irrazionale sono distribuite
uniformemente tra 0 e 1.
Una dimostrazione si trova qui:
http://www.mathnerds.com/best/digit/ThA.aspx

A me questo problema (di cui non conosco la risposta), ha fatto
venire in mente le sequenze di Beatty, di cui avevo letto nel
libro Concrete Mathematics.

Se non le conosci sono simpatiche. Puoi leggerne qui:
http://mathworld.wolfram.com/BeattySequence.html
e qui:
http://en.wikipedia.org/wiki/Beatty_sequence

ciao,
g.

[salva]

Grazie, daro' sicuramente un'occhiata.
Ciao
Salva

[g.resta]

> On Aug 27, 7:14 am, "g.resta" <g.re...@iit.cnr.it> wrote:

>> Le parti frazionarie dei multipli di un irrazionale sono distribuite
>> uniformemente tra 0 e 1.

>> http://www.mathnerds.com/best/digit/ThA.aspx

Non avevo pensato che da questa proprieta' discende immediatamente
che il problema non puo' essere risolto.

Ovviamente il valore D non puo' essere dato in forma simbolica,
altrimenti avremmo direttamente il valore di m.

Quello che possiamo immaginare di avere e' un oracolo
che ad ogni invocazione ci fornisca una ulteriore cifra significativa
di D.
Il problema e' che, per la proprieta' di uniformita', se immaginiamo
che l'oracolo ci abbia fornito le prime n cifre (per qualunque n) di
D
abbiamo comunque un numero infinito di possibili m che possono
fornire un residuo coincidente con D nelle prime n cifre.

Un problema diverso, in linea di principio fattibile, e' determinare
il piu' piccolo m tale che il residuo D ottenuto coincida nelle prime
n cifre con un numero dato.

In pratica, se io ti chiedo quale e' il piu' piccolo m tale che la
parte
frazionaria di Sqrt(2)*m cominci con 0.1234567 la risposta la puoi
trovare provando tutti gli m fino a trovare quello giusto (in questo
caso 6150388)
Per la proprieta' di uniformita' so che esistono infiniti m tail che
la parte frazionale di Sqrt(2)*m e' 0.1234567.....
quindi "prima o poi" ne trovero' uno.

Quello che mi chiedo e' se esiste un modo per determinare un
upperbound al valore di m (entro il quale so che trovero' una
soluzione)
e in generale se esiste un modo per velocizzare la ricerca di m.

ciao,
g.