[recre] petit (!) calcul
Philippe 92
Un petit calcul pour se distraire :
Trouver la plus petite puissance de 7 qui commence par 7 chiffres 7
Donner les (quelques) chiffres suivants.
Mathematica, Pari et autres Mapple interdits.
On dispose d'une feuille de papier et d'une simple calculette
scientifique (genre celle de Windows).
Amicalement.
--
Philippe C., mail : chephip
avec free.fr comme domaine
site : http://mathafou.free.fr/ (divertissements mathï¿œmatiques)
Sylvain
> Bonjour,
>
> Un petit calcul pour se distraire :
> Trouver la plus petite puissance de 7 qui commence par 7 chiffres 7
> Donner les (quelques) chiffres suivants.
>
> Mathematica, Pari et autres Mapple interdits.
> On dispose d'une feuille de papier et d'une simple calculette
> scientifique (genre celle de Windows).
>
> Amicalement.
ln7777777 / ln7 = 8,153912518
7^8,153912518 = 7777777
--
Ne pas prￜvoir, c'est dￜjￜ gￜmir
Lï¿œonard de Vinci
Philippe 92
> Philippe 92 wrote:
>> Bonjour,
>>
>> Un petit calcul pour se distraire :
>> Trouver la plus petite puissance de 7 qui commence par 7 chiffres 7
>> Donner les (quelques) chiffres suivants.
>>
>> Mathematica, Pari et autres Mapple interdits.
>> On dispose d'une feuille de papier et d'une simple calculette
>> scientifique (genre celle de Windows).
>>
>> Amicalement.
>
> ln7777777 / ln7 = 8,153912518
>
> 7^8,153912518 = 7777777
gnￜgnￜgnￜ ... puissance *** entiￜre ***
Bien essayￜ ;-)
zwim
Philippe 92 a �crit
>
>Un petit calcul pour se distraire :
>Trouver la plus petite puissance de 7 qui commence par 7 chiffres 7
>Donner les (quelques) chiffres suivants.
>
>Mathematica, Pari et autres Mapple interdits.
>On dispose d'une feuille de papier et d'une simple calculette
>scientifique (genre celle de Windows).
>
>Amicalement.
Je suis parti de la s�quence suivante
http://www.research.att.com/~njas/sequences/A018856
Qui pointe sur la r�f�rence ci-dessous :
"Challenging Mathematical Problems With Elementary Solutions"
qu'on peut trouver sur le net.
Je m'en suis donc inspir�.
On doit donc trouver 7 777 777.10^K <= 7^N < 7 777 778. 10^K
Je pose M = 7 777 777
En passant au log d�cimal, soient � trouver p et k tels que :
log(M) + K <= N log(7) < log(M+1) + K
L'id�e est de passer modulo 1 (c�d prendre la partie fractionnaire).
�a donne log(M) <= N.log(7) < log(M+1) [mod 1]
Soit encore
0 <= N log(7) - log(M) < log(1+1/M) [mod 1]
Pour le moment j'en suis l�.
Bien entendu une �num�ration "force brute" donne N = 825794 (qui
devrait convenir, � v�rifier sous maple).
Je n'ai pas encore d'id�e pour trouver N directement.
Une approximation p/q des r�duites de log(M)/log(7) peut-�tre ?
--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...
Philippe 92
> Le Wed, 21 Oct 2009 15:07:03 +0200
>>
>
> http://www.research.att.com/~njas/sequences/A018856
>
Cette sￜquence est "un peu juste" car limitￜe ￜ de trￜs faibles valeurs
de n (n < 73), qui lui permet d'ï¿œtre calculï¿œe par force brute
2^n = 123456789.....est complￜtement hors de portￜe du calcul proposￜ
(la puisance de 2 cherchï¿œe a plus de 18 millions de chiffres)
> Qui pointe sur la rï¿œfï¿œrence ci-dessous :
> "Challenging Mathematical Problems With Elementary Solutions"
> qu'on peut trouver sur le net.
>
Euh... "aperￜu limitￜ" ... ￜ la couverture !
On peut toujours l'acheter...
> Je m'en suis donc inspirￜ.
>
> On doit donc trouver 7 777 777.10^K <= 7^N < 7 777 778. 10^K
> Je pose M = 7 777 777
>
> En passant au log dￜcimal, soient ￜ trouver [N et K] tels que :
> log(M) + K <= N log(7) < log(M+1) + K
>
> L'idï¿œe est de passer modulo 1 (cï¿œd prendre la partie fractionnaire).
> ï¿œa donne log(M) <= N.log(7) < log(M+1) [mod 1]
Euh... ce passage ￜ la partie fractionnaire sur des inￜgalitￜs est
"un peu douteux"
Si A < B on ne peut pas dire si frac(A) > ou < frac(B) sans prï¿œcautions
particuliï¿œres. Mais il y a effectivement de l'idï¿œe.
Ici ï¿œa marche parce que (log(M+1) + K) - (log(M) + K) = log(1 + 1/M)
est indï¿œpendant de K et < 1
> Soit encore
> 0 <= N log(7) - log(M) < log(1+1/M) [mod 1]
>
Oui.
> Pour le moment j'en suis lￜ.
> Bien entendu une ï¿œnumï¿œration "force brute" donne N = 825794 (qui
> devrait convenir, ￜ vￜrifier sous maple).
Bouh le vilain...
Les premiers chiffres de 7^825794 peuvent se calculer ￜ la calculette
ordinaire. Pas les 600000 et quelques chiffres, ni directement en
virgule flottante "ordinaire", limitￜ ￜ 10^308, mais avec un peu
d'astuce, qui est d'ailleurs le but de ma seconde question :
"Donner les (quelques) chiffres suivants"
>
> Je n'ai pas encore d'idï¿œe pour trouver N directement.
> Une approximation p/q des rï¿œduites de log(M)/log(7) peut-ï¿œtre ?
Ca aussi, il y a de l'idï¿œe...
J'ai utilisￜ les rￜduites de log(7), mais c'est peut ￜtre plus
efficace encore avec les rï¿œduites de log(M)/log(7)
Tu tiens le bon bout (logarithmes et rï¿œduites)
Sylvain
zwim
Sylvain a �crit
>7^825794 = 7,77777782488.....*10^697876
Oui, cette partie n'est pas tr�s difficile.
Et puisque comme outil on n'a droit qu'� la calculatrice windows � ce
que j'ai cru comprendre, �a donne simplement :
7 ^825794
= 10^(825794 * log(7))
= 10^697876 * 10^0.89....
= 7.7777778248843309922994815777341 * 10^697876
Le dernier 1 de 341 est faux (ce qui semble normal vu la pr�cision
limit�e), maple donne 344.
zwim
Philippe 92 a �crit
>zwim a �crit :
>> Le Wed, 21 Oct 2009 15:07:03 +0200
>>>
>>> Mathematica, Pari et autres Mapple interdits.
>>
>de n (n < 73), qui lui permet d'�tre calcul�e par force brute
>2^n = 123456789.....est compl�tement hors de port�e du calcul propos�
>(la puisance de 2 cherch�e a plus de 18 millions de chiffres)
>
>> Qui pointe sur la r�f�rence ci-dessous :
>> "Challenging Mathematical Problems With Elementary Solutions"
>> qu'on peut trouver sur le net.
>>
>
>On peut toujours l'acheter...
En cherchant bien, on peut trouver un pdf complet...
>> Je m'en suis donc inspir�.
>>
>> On doit donc trouver 7 777 777.10^K <= 7^N < 7 777 778. 10^K
>> Je pose M = 7 777 777
>>
>> En passant au log d�cimal, soient � trouver [N et K] tels que :
>> log(M) + K <= N log(7) < log(M+1) + K
>>
>> L'id�e est de passer modulo 1 (c�d prendre la partie fractionnaire).
>> �a donne log(M) <= N.log(7) < log(M+1) [mod 1]
>
>
>Euh... ce passage � la partie fractionnaire sur des in�galit�s est
>"un peu douteux"
>Si A < B on ne peut pas dire si frac(A) > ou < frac(B) sans pr�cautions
>particuli�res. Mais il y a effectivement de l'id�e.
>Ici �a marche parce que (log(M+1) + K) - (log(M) + K) = log(1 + 1/M)
>est ind�pendant de K et < 1
Oui, je n'ai pas r�dig� plus que ��, l'id�e c'est que les points
N.log(7) mod 1, �quir�partis sur le cercle (car log(7) irrationnel)
rentrent dans le petit intervalle de longueur log(1+1/M) ~ 1/M.ln(10).
On sait donc qu'il y en a forc�ment, reste � trouver une condition
pour avoir le plus petit N.
>> Soit encore
>> 0 <= N log(7) - log(M) < log(1+1/M) [mod 1]
>>
>
>Oui.
>
>> Pour le moment j'en suis l�.
>> Bien entendu une �num�ration "force brute" donne N = 825794 (qui
>> devrait convenir, � v�rifier sous maple).
>
>Bouh le vilain...
A moiti� seulement, j'ai cherch� un N qui v�rifiait la condition
ci-dessus et pas calcul� 7^N.
>Les premiers chiffres de 7^825794 peuvent se calculer � la calculette
>ordinaire. Pas les 600000 et quelques chiffres, ni directement en
>virgule flottante "ordinaire", limit� � 10^308, mais avec un peu
>d'astuce, qui est d'ailleurs le but de ma seconde question :
>"Donner les (quelques) chiffres suivants"
cf. mon autre post.
>>
>> Je n'ai pas encore d'id�e pour trouver N directement.
>> Une approximation p/q des r�duites de log(M)/log(7) peut-�tre ?
>
>Ca aussi, il y a de l'id�e...
>J'ai utilis� les r�duites de log(7), mais c'est peut �tre plus
>efficace encore avec les r�duites de log(M)/log(7)
>
>Tu tiens le bon bout (logarithmes et r�duites)
Ca je chercherai demain.
En fait le r�sultat que je connais sur les r�duites c'est | x - p/q |
< 1/q� pour x r�el.
Or ici c'est l�g�rement diff�rent, on cherche pour x,y r�els � savoir
si | nx - y | est proche d'un entier
(i.e. ||nx-y|| = min(frac(nx-y),1-frac(nx-y)) < epsilon)
A priori on peut partir sur des r�duites de x, de y, ou de x/y (ou y/x
peu importe). Je n'ai pas encore trop d'id�e sur quoi choisir ?
ast
"Philippe 92" <nos...@free.invalid> a ï¿œcrit dans le message de
news:mn.ab8b7d9a4...@free.fr...
> Bonjour,
>
> Un petit calcul pour se distraire :
> Trouver la plus petite puissance de 7 qui commence par 7 chiffres 7
> Donner les (quelques) chiffres suivants.
>
> Mathematica, Pari et autres Mapple interdits.
> On dispose d'une feuille de papier et d'une simple calculette
> scientifique (genre celle de Windows).
>
> Amicalement.
>
bon, tu nous donnes la solution ?
Philippe 92
Bonjour,
Disons, ma solution...
Apparemment Zwim ne s'est pas sorti de son choix de fraction
continue. Moi non plus d'ailleurs : je garde ma mï¿œthode d'origine.
Reprenons le dï¿œbut des calculs de Zwim, avec mes notations (c'est
plus simple pour copier coller)
Soit M = 7777777
On cherche donc M*10^m <= 7^n < (M+1)*10^m (ￜ rￜsoudre en n)
et en passant au logarithme dï¿œcimal :
log(M) + m <= n*log(7) < log(M+1) + m
ou encore :
log(M)/log(7) + m/log(7) <= n < log(M+1)/log(7) + m/log(7)
La diffï¿œrence entre les deux bornes est
log(M+1)/log(7) - log(M)/log(7) = log(1 + 1/M)/log(7) < 1
Considï¿œrons les parties fractionnaires ("modulo 1")
appelons v = frac(log(M)/log(7) + m/log(7))
et d = log(1 + 1/M)/log(7) = ￜ sa partie fractionnaire car < 1
On cherche donc m tel que
v < 1 < v + d ou v = 0 (il faudrait dï¿œfinir frac(0) = 1 sinon)
ￜ chaque fois qu'on augmente m de 1, on augmente v de frac(1/log7)
modulo 1, c'est ￜ dire de 0.18329...
ￜ m = 0 on est ￜ
v = frac(log(M)/log(7)) = 0.153912....
comme on veut atteindre
v > 1 - d = 0.9999999339....
il faut dï¿œja augmenter m de
(0.9999999339 - 0.153912)/0.18329 = 4.61...
c'est ￜ dire m = 5
On obtient alors v = 0.07038... (modulo 1, car on a dￜpassￜ un "tour")
C'est ici qu'intervient l'astuce des fractions continues de log(7)
ou plus exactement de 1/log(7)
ï¿œcrivons donc 1/log(7) = P/Q + eps avec P/Q une rï¿œduite
on sait que eps est alternativement positif et nï¿œgatif, qu'il tend
vers 0 et mï¿œme que
|1/log(7) - P/Q| < 1/Q^2 (citￜ par Zwim)
ou encore que |Q/log(7) - P| < 1/Q (c'ￜtait lￜ l'astuce)
Si on fait ainsi jouer ￜ Q le rￜle de m dans notre recherche, et que
l'on passe ￜ la partie fractionnaire, on a pour les rￜduites
|frac(Q/log(7))| < 1/Q ￜ condition de reprￜsenter par "frac" une
valeur signï¿œe entre -0.5 et + 0.5 (modulo 1)
Ceci montre que ￜ chaque fois qu'on augmente m de Q, Q ￜtant le
dï¿œnominateur d'une rï¿œduite de 1/log(7), v progresse de cette erreur
(le reste) Q/log(7) - P = Q*eps modulo 1, et qu'ￜ chaque rￜduite
successive, cette erreur diminue, et est alternativement >0 et <0
De plus les rï¿œduites sont les "meilleures" approximations de 1/log(7)
c'est ￜ dire qu'il n'y a pas de fraction plus simple aussi prￜcise.
Ceci va nous garantir un m minimum et donc "la plus petite puissance
de 7" dans le processus suivant :
Pour les rï¿œduites successives P/Q de 1/log(7) (obtenues comme d'hab)
appelons t = Q/log(7) - P
si t>0 augmenter m de ceil((1-e-v)/t)*Q
si t<0 augmenter m de ceil(v/|t|)*Q
jusqu'ￜ ce que la condition v = 0 ou v > 1 - e soit satisfaite.
(quelques petites subtilitï¿œs sur les frac et ceil de nombres entiers
ajoutent quelques dￜtails sordides ￜ cet algorithme)
On obtient ainsi successivement :
(valeurs tronquï¿œes et non pas arrondies)
1/log(7) = [1,5,2,5,6,1,4813,...]
P/Q = 1/1, t = 0.1832946624, v = 0.1539125176, m = 5
P/Q = 6/5, t = -0.0835266877, v = 0.0703858299, m = 5 + 1*5 = 10
P/Q = 13/11, t = 0.0162412870, v = 0.9868591422, m = 10 + 1*11 = 21
P/Q = 71/60, t = -0.0023202527, v = 0.0031004292, m = 21 + 2*60 = 141
P/Q = 439/371, t = 0.0023197707, v = 0.9984599238, m = ... = 512
P/Q = 510/431, t = -0.0000004819, v = 0.0007796946, m = 697870
P/Q = 2455069/2074774, t = 0.0000002826, v = 0.9999999456, m = 697870
v > 1 - d = 0.9999999339 et c'est donc fini.
On a ainsi m, et on en dï¿œduit n comme ceil(log(M)/log(7) + m/log(7))
n = ceil(825793.99999994) = 825794
Pour le calcul de la valeur approchï¿œe de 7^825794, l'explication a
dￜja ￜtￜ donnￜe.
Je donne ma mï¿œthode :
7^825794 = exp(ln(7)*825794 - ln(10)*697876) * 10^697876
la calculette de Windows affiche :
7.77777782488433099229948157773421 * 10^697876
Comme pour tout calcul numï¿œrique, il est nï¿œcessaire d'effectuer un
calcul d'erreurs pour savoir quels sont les chiffres exacts dans le
"rￜsultat" affichￜ (que je donne ici brut de copier coller) !
zwim
Philippe 92 a �crit
>ast a �crit :
>> "Philippe 92" <nos...@free.invalid> a �crit dans le message de
>>> Bonjour,
>>>
>>> Un petit calcul pour se distraire :
>>> Trouver la plus petite puissance de 7 qui commence par 7 chiffres 7
>>> Donner les (quelques) chiffres suivants.
>>>
>>> Mathematica, Pari et autres Mapple interdits.
>>> On dispose d'une feuille de papier et d'une simple calculette
>>> scientifique (genre celle de Windows).
>>>
>>> Amicalement.
>>>
>>
>>
>> bon, tu nous donnes la solution ?
>
>Bonjour,
>
>Disons, ma solution...
>Apparemment Zwim ne s'est pas sorti de son choix de fraction
Arf, en fait j'ai pas cherch�, je n'ai pas eu le temps. J'allais m'y
remettre ce soir.
>Si on fait ainsi jouer � Q le r�le de m dans notre recherche, et que
>l'on passe � la partie fractionnaire, on a pour les r�duites
>|frac(Q/log(7))| < 1/Q � condition de repr�senter par "frac" une
>valeur sign�e entre -0.5 et + 0.5 (modulo 1)
>Ceci montre que � chaque fois qu'on augmente m de Q, Q �tant le
>d�nominateur d'une r�duite de 1/log(7), v progresse de cette erreur
>(le reste) Q/log(7) - P = Q*eps modulo 1, et qu'� chaque r�duite
>successive, cette erreur diminue, et est alternativement >0 et <0
>De plus les r�duites sont les "meilleures" approximations de 1/log(7)
>c'est � dire qu'il n'y a pas de fraction plus simple aussi pr�cise.
>Ceci va nous garantir un m minimum et donc "la plus petite puissance
>de 7" dans le processus suivant :
>
>Pour les r�duites successives P/Q de 1/log(7) (obtenues comme d'hab)
>appelons t = Q/log(7) - P
> si t>0 augmenter m de ceil((1-e-v)/t)*Q
> si t<0 augmenter m de ceil(v/|t|)*Q
>
>jusqu'� ce que la condition v = 0 ou v > 1 - e soit satisfaite.
>(quelques petites subtilit�s sur les frac et ceil de nombres entiers
>ajoutent quelques d�tails sordides � cet algorithme)
>
> [...]
>
>On a ainsi m, et on en d�duit n comme ceil(log(M)/log(7) + m/log(7))
>n = ceil(825793.99999994) = 825794
ok, je comprends ta m�thode, c'est astucieux, bien vu.
Moi j'allais plus sur la piste Nx-y proche d'un entier donc si
x ~ an/bn et y ~ cn/dn les r�duites de x et y, soit � trouver N
pour que
N ai/bi - cj/dj = (N.ai.dj - bi.cj) / bi.cj le plus petit possible,
mais je ne savais pas trop comment g�rer i,j ? A savoir �tudier tous
les couples possibles o� prendre i=j et consid�rer des r�duites
"�quivalentes" de x et y.