Sequenze di Mersenne 3 - e vuole la sua parte!

[edriv]

Prendiamo il nostro amico e e definiamo la sequenza di interi:
$ ~ x_1 = 1 $
$ ~ x_{n+1} = \left[ e \cdot x_n! \right] $

Lo so che non ci crederete, ma... dimostrate che $ ~ x_n $ è una sequenza di Mersenne.
Ricordo che una sequenza di interi è detta sequenda di Mersenne se:
$ ~ \mbox{gcd}(x_m,n_n) = x_{\mbox{gcd}(m,n)} $ per ogni coppia di interi positivi m,n.

Per chi si fosse perso le prime puntate:
viewtopic.php?t=8138
viewtopic.php?t=8153

[mattilgale]

allora

lemma: $ x_{jn+k}\equiv x_k\ \pmod{x_n} $

adesso mostriamo per induzione su n che dati n ed m interi con n>m si ha che
$ \displaystyle (x_n,\ x_m)=x_{(n,\ m)} $
la tesi è vera a vuoto per n=1, supponiamo quindi che sia vera per ogni intero fino ad n-1.

scriviamo n come n=mk+a con 0<=a<m ovviamente (n,m)=(m,a) e poiché per il lemma $ x_n\equiv x_a\ \pmod{x_m} $ allora
$ \displaystyle (x_n,\ x_m)=(x_m,\ x_a)=x_{(m,\ a)}=x_{(m,\ n)} $ dove nella seconda uguaglianza abbiamo usato l'ipotesi induttiva
CVD

dimostriamo ora il lemma, per farlo è sufficiente osservare che
$ x_{m+1}\equiv 1\ (x_m) $
se $ x_n\equiv b\ (x_m) $ con 0<=b< x_m allora $ x_{n+1}\equiv [e\cdot b!]\ (x_m) $

osserviamo che $ x_{m+1}=2x_m!+\frac{x_m!}{2!}+\cdots+x_m+1 $ cioè $ x_{m+1}\equiv 1\ (x_m) $

mentre se $ x_n\equiv b $ con 0<=b<m allora osserviamo che
$ x_{n+1}=2x_n!+\frac{x_n!}{2!}+\cdots+\frac{x_n!}{(x_n-b)!}+\cdots+x_n+1 $

ovviamente i termini fino a $ \frac{x_n!}{(x_n-b)!} $ escluso sono divisibili per $ x_m $ mentre i termini successivi sono congruenti rispettivamente a $ b!,\ b!,\ \frac{b!}{2!},\ \dots,\ 1 $ e pertanto $ x_{n+1}\equiv 2b!+\frac{b!}{2!}+\cdots+1\equiv [e\cdot b!]\ \pmod{x_m} $

a questo punto si osserva che $ x_{2m}\equiv 0 $ e per induzione si finisce a $ x_{jm+a}\equiv x_a $

fine

[edriv]

osserviamo che $ x_{m+1}=2x_m!+\frac{x_m!}{2!}+\cdots+x_m+1 $ cioè $ x_{m+1}\equiv 1\ (x_m) $


ovviamente i termini fino a $ \frac{x_n!}{(x_n-b)!} $ escluso sono divisibili per $ x_m $ mentre i termini successivi sono congruenti rispettivamente a $ b!,\ b!,\ (b-1)!,\ \dots,\ 1 $ e pertanto $ x_{n+1}\equiv 2b!+(b-1)!+\cdots+1\equiv [e\cdot b!]\ \pmod{x_m} $

Buona soluzione, solo nei passi citati sopra c'è qualche imprecisione:
- nel primo sarebbe buona cosa almeno far notare che usi la definizione di e come:
$ \displaystyle e = \sum_{i=0}^{\infty} \frac{1}{i!} $ e che, moltiplicando per $ ~ k! $, la somma di tutti i termini minori di 1 è ancora minore di 1, il che si fa semplicemente approssimandoli con una serie geometrica.

- nel secondo sono solo le formule un po' sballata ma l'idea è chiara

[mattilgale]

i) buuuuu che pignolo!

ii) ok editato