Suite de double restes par division euclidienne
Aujourd’hui mon ami Fare de NYC, quelques jours en visite à Paris, m’a invité dans son cercle habituel d’amis libertaires (pour que je fasse contre-poids à leurs idées?). Mais on ne parlait pas uniquement d’interactions société/économie et d’un certain monde idéal, mais aussi un peu de math. Comme cadeau d’au-revoir il m’a posé ce joli problème que je souhaite partager avec vous:
un = (10n2+n mod 102n-10n-1) mod 10n.
(Comme d’habitude a mod b désigne le reste de la division euclidienne de a par b.)
Quelle est cette suite et pourquoi?
En posant \(v_n=10^n\) cela revient à évaluer $$(v_n^{n+1}\mod(v_n^2 – v_n -1))\mod v_n.$$ Avec \(w_{n,k} = v_n^k \mod (v_n^2 – v_n -1)\) on établit que
\[w_{n,k+1} = (v_n^k + v_n^{k-1}) \mod (v_n^2 – v_n -1) = w_{n,k} +w_{n,k-1}.\]
On reconnait une récurrence à la Fibonacci où \(w_{n,0}=1\) et \(w_{n,1}=v_n\). On démontre par récurrence que \(w_{n,k+1} = F_k v_n + F_{k-1}\) où \(F_k\) est la suite de Fibonacci. Donc \[w_{n,n+1} \mod v_n = (F_n v_n + F_{n-1}) \mod v_n = F_{n-1} \mod v_n.\]
On démontre facilement que \(F_{n-1}\lt v_n.\) C’est donc la valeur cherchée.
Merci pour votre preuve. Il manque juste une chose : Il n’est pas prouvé que \(F_k v_n + F_{k-1}\) est le reste de la division euclidienne.
Question bonus pour bistraque: quel est la valeur minimale de v_n pour que l’équation fonctionne?
Je revenais sur la page pour voir si le pb tex avait été résolu, et me voilà sous le feu des questions. Je rajeunis de 40 ans 🙂 …
J’ai en effet oublié de borner \(w_{n,n+1}\). Si on adopte \(2^n\) comme majorant de \(F_n\) (même démonstration que pour \(F_{n-1} < v_n\)), on a \[w_{n,n+1} \lt 2^n v_n + 2^{n-1} < 2^n (v_n + 1) \leq (v_n – 2)(v_n + 1) \lt v_n^2 – v_n – 1,\] pour tout \(n\geq1\) (oui il faut démontrer aussi que \(2^n \lt 10^n – 2\)).
Concernant la valeur minimale de \(v_n\), je dirais \(3^n\) sans démonstration car le majorant ci-dessus ne marche qu’à partir de \(v_n = 4^n\).
\(2^n\) ne marche pas car pour \(n=1\) on a \(u_n = 0\), par contre on retrouve \(u_n = F_{n-2}\) avec un décalage de 1 donc. Pour \(v_n = 3^n\), les valeurs de \(u_1\) et \(u_2\) semblent confirmer le résultat. Désolé pour ces réponses imprécises.
1- La formule a été dérivée en partant de la série formelle \(S(X) = \sum(k,\operatorname{fib}(k) X^k)\). En utilisant la formule de récurrence et les deux premiers termes, on a \(S(X) = X + X S(X) + X^2 S(X)\) d’où \(S(X)=X/(1-X-X^2)\). Pour \(A\) assez grand, la partie entière à \(A^n S(1/A) = A^{n+1}/(A^2-A-1)\) est un nombre très grand dont les "chiffres" en base \(A\) sont les n premiers termes de la suite, et le chiffre des unités est \(\operatorname{fib}(n)\). Paul Hankin en tire la formule
\[\operatorname{fib}(n) = (A^{n+1} \operatorname{div}(A^2-A-1)) \mod A,\]
où div est le quotient de la division euclidienne. Mais cela nécessite de calculer un nombre énorme; et si on pouvait remplacer ce quotient par un reste? On peut! En effet, si \(A^{n+1} = q*(A^2-A-1) + r\), alors modulo A, on a \(0 = q*-1 + r\), et donc q = r. On peut donc utiliser \(\mod (A^2-A-1)\) au lieu de div\((A^2-A-1)\). Avec l’exponentiation rapide modulo \(A^2-A-1\), on obtient même un algorithme de calcul compétitif (si on a une bonne approximation supérieure pour \(\log_2(A)\)).
2- La valeur minimale pour \(v_n\) est \(F_{n+1} + 2\). Prouvez-le.
@Mathoman, s’il vous plait … notre ami Faré n’est pas libertaire, mais libertarien.
Anarcho-capitaliste. Strictement rien à voir avec l’idéologie libertaire.