Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
#28 12-08-2018 16:48:39
- Pierrro
- Membre
- Inscription : 12-08-2018
- Messages : 11
Re : Calcul de Tétration
C'est le même résultat que la toute première proposition.
Hors ligne
#29 12-08-2018 16:54:48
- Roubaud
- Invité
Re : Calcul de Tétration
Merci Dattier ! Tu avais vu juste.
Grace à toi j'ai compris mon erreur.
#32 12-08-2018 17:08:33
- Pierrro
- Membre
- Inscription : 12-08-2018
- Messages : 11
Re : Calcul de Tétration
En tous cas, merci pour le coup de main et la trituration de méninges.
Bonne fin de journée.
Hors ligne
#33 12-08-2018 18:43:50
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Rebonjour,
@Dattier. Tu dois confondre avec le C... J'ai quand même vérifié au cas où :
Python integers are effectively big integers, no need of a special
class. Just use normal integers.
D'autre part
un résultat de la 2e itération de ton script : [tex]44^{17592186044416}[/tex] est un nombre d'environ 28 911 925 239 938 chiffres...
En Python les calculs sur les integers n'ont pour limite que la quantité de RAM de la bécane.
J'ai un Python 64 bits et 16 Go de RAM et pourtant... Comment Maple peut-il gérer de tels nombres ????
[tex]44^{17592186044416}[/tex] c'est 17 592 186 044 415 multiplications...
Ce n'est pas pensable : j'ai sûrement mal interprété et traduit ton script...
Ensuite, si je comprends bien, je ne calcule pas [tex]x=\dfrac{1}{2^{44}}[/tex] puis $x$ modulo $5^{44}$
Mais l'inverse modulo $5^{44}$... de $2^{44}$ ce que Python, ne peut me faire directement.
Mais j'ai un petit script qui me le fait :
L'inverse, modulo 5684341886080801486968994140625, de 17592186044416 est : 4363818328044765927417222868811
Fait en 0.0 s
Je vais reprendre à zéro : où était l'erreur de ton programme ?
@+
[EDIT]Puissance rapide implémentée et fonctionnelle
Mais ça n'enlève rien à la problématique du nombre de chiffres à traiter dès la 2e itération...
Maintenant, j'ai assez vite le message : MemoryError
Dernière modification par yoshi (12-08-2018 19:08:35)
Arx Tarpeia Capitoli proxima...
Hors ligne
#35 12-08-2018 20:46:52
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
RE,
Repris le prog en post #27...
Ça tourne correct, et pour cause, dans la boucle, a reste scotché à 1...
j'ai écrit ça :
a=spow(44,a) % (spow(2,m+1-j)*spow(5,j+n-m)) pour ton Power(44,a) mod (2^(m+1-j)*5^(j+n-m))
Pour j=1, on démarre avec a =1, 44**1 = 44
m+1-j=44, j+n-m =1+50-44=7
a=1 % (2**44 * 5**7)=1
et pour j=2, a =1 encore et le nouveau a vaudra encore 1...
@+
[EDIT] Je m'occuperai de l'exponientiation modulaire demain...
Dernière modification par yoshi (12-08-2018 20:50:01)
Arx Tarpeia Capitoli proxima...
Hors ligne
#37 13-08-2018 14:44:03
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Bonjour,
J'ai fini par réussir à faire fonctionner l'exponentiation modulaire.
Je l'ai installée en def comme mon spow, lequel avait un souci : tout est réglé.
Mais je n'ai pas de résultat cohérent en cherchant la réponse que tu as trouvée.
Mais dans ton code, quelque chose qui m'avait échappé hier, me surprend.
Tes 3 dernières lignes :
c:=Power(44,a) mod (5^n);#ici on finit le calcul de T mod 5^44
b:=1/(2^n) mod 5^n;
a*b*2^n mod 10^n;
Tu calcules c , ok !
Pour quoi faire, puisque tu ne le réutilises pas dans les lignes suivantes ???
Ensuite
[tex]1/(2^n) \mod (5^n)[/tex]
* c'est [tex][1/(2^{50})] \mod (5^n)[/tex], soit ici : [tex]0,00000000000000088817841970012523233890533447265625 \mod 5^{50}[/tex] ?
ce que j'ai cru comprendre puisque tu parles de chiffres après la virgule...
* Ou, l'inverse modulo 5^50, de 2^50 : soit ici, 37815596671023757654145018867282374 ?
getcontext().prec=50
# Decimal convertit un nombre en un format défini par le module decimal, getcontext().prec=50 fixe le nombre de décimales à 50
def spow(x,n):
e = (n - n % 2)//2
y = (x**2)**e
if n%2:
y*=x
return y
def powmod(base,n,modulo):
result=1
while n>0:
if (n & 1)>0:
result=(result*base)% modulo
n>>=1
base=(base*base)% modulo
return result
n=50
m,a,p2=44,1,spow(2,n)
for j in range(1,45): # Python s'arrête à 44
a=powmod(44,a,spow(2,m+1-j)*spow(5,j+n-m))
c=powmod(44,a,spow(5,n))
b=D(1)/D(spow(2,n)) % spow(5,n)
nb=str(int(p2*D(a)*D(b))) # je convertis le résultat en un entier, puis l'entier en chaîne
lg=len(nb)-44 # je calcule la position de départ
print (nb[lg:]) # pour extraire les 44 derniers caractères de la chaîne nb
N-B : mon résultat nb ne contient que 35 chiffres (et ses décimales n'étaient que des 0) : même les chiffres de nb sont faux.
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#39 13-08-2018 17:32:26
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Salut,
Je ne mets pas du tout en cause tes éléments théoriques qui me dépassent un peu mais mes recherches parallèles me permettent d'avancer petit à petit..
C'est juste que (j'ai quand même l'habitude de programmer) je n'arrive pa à traduire ton code Maple en code Python et c'est bien la première que je n'arrive pas à passer d'un langage à Python.
J'ai écrit des tas de code dont le calcul de l'indicatrice d'Euler, mais là, je ne comprends pas tes quelques lignes.
Par exemple
1. je t'ai fait remarquer que en sortie de boucle, tu calculais la valeur d'une variable c et que je retrouvais pas cette valeur de c utilisée dans les deux lignes suivantes...
Alors, je cherche à comprendre pourquoi : il m'est arrivé dans mes programmes de constater que telle ou telle variable calculée n'était pourtant pas utilisée et je je l'ai supprimée sans fausser le prog.
J'ai fait le test : j'ai mis la ligne de calcul de c en REM : je retrouve exactement la même valeur finale.
Donc (dans mon code, cette ligne est totalement inutile... Pourquoi ?
J'ai essayé de remplacer c par a (à cause du commentaire de la ligne), le résultat final est différent, mais ne possède encore que 35 chiffres.
Pourquoi ce blocage à 35 ?
2. Je t'ai demandé (parce que je n'ai pas pu trouver la réponse dans un cours de Maple) et que j'ai testé la 2e explication putative que j'ai soulevée, ce que représentait exactement la valeur de b...
Exemple simple :
(1/4**2) % 35 =0.0625 % 35 =0.0625 c'est (l'inverse de 4**2) mod 35
Mais l'inverse, modulo 35, de 4**2 est 9....
La théorie, c'est bien, mais je suis frustré : tes quelques lignes fonctionnent chez toi, donnent le bon résultat et ma traduction en Python est à la rue...
Je préférerais d'abord faire fonctionner mon truc et ensuite me consacrer à la théorie, mais c'est toi qui voit...
Tu écris :
$N=q_i^{\alpha_1}\times ... q_j^{\alpha_j}$ les $\alpha_i\geq 1$, les $q_i$ premiers distincts.
J'ai quand même dû réfléchir pour savoir lorsque tu écris "premiers", tu parlais de "premiers nombres" ou de nombres premiers et j'ai pu trancher avec ton écriture de N et voir qu'il s'agit de la décomposition en produits de facteurs premiers $q_i$ avec pour exposants respectifs $\alpha_i$ (d'où le $\geqslant 1$)
Ensuite e = max(...), oui, ce e existe
Par contre ta première ligne ??? Mais je te fais confiance, tu sais de quoi tu parles...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#43 14-08-2018 07:47:32
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Salut,
Bravo et merci.
Cette fois, ça tourne du 1er coup...
# -*- coding: utf8 -*-
def spow(x,n):
e = (n - n % 2)//2
y = (x**2)**e
if n%2:
y*=x
return y
def powmod(base,n,modulo):
result=1
while n>0:
if (n & 1)>0:
result=(result*base)% modulo
n>>=1
base=(base*base)% modulo
return result
n,t,h=100,44,44
a=t
for j in range(h-1,-1,-1):
a=powmod(t,a,spow(5,n-j)*spow(2,n-j))
print("Valeur de a avec",n," chiffres :\n",a)
print()
print ("Les",t,"derniers chiffres de a sont :\n",str(a)[n-44:])
Exécution :
Valeur de a avec 100 chiffres :
5557690789238586682285142131824201389641731213663548150449376824492757966075731479288470062137081856Les 44 derniers chiffres de a sont :
49376824492757966075731479288470062137081856
Quasiment instantané !
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#45 14-08-2018 10:34:30
- Wiwaxia
- Membre
- Lieu : Paris 75013
- Inscription : 21-12-2017
- Messages : 411
Re : Calcul de Tétration
J'ai regardé sur ma calculatrice le comportement de la suite double vérifiant:
a0 = 44
bn = 44*a(n-1)
an = bn (mod 10c) ( pour tout n>0 )
Il semble que la suite devienne périodique à partir du seuil (l) pour lequel on observe pour la première fois
bl > 10c
et admette pour période: p = 2*5(c-1) .
J'ai trouvé:
c l p
1 1 2
2 1 10
3 1 50
4 2 250
5 3 1250
6 3 6250
Je n'ai pas le temps de mettre tout cela en forme, mais je crois qu'il y a de ce côté une piste pour un calcul raisonnable du nombre 44^(44^44) mod 1044 .
Le recours à l'arithmétique modulaire permet de limiter le nombre de chiffres.
Dernière modification par Wiwaxia (14-08-2018 10:44:24)
Hors ligne
#46 14-08-2018 13:09:30
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Bonjour,
On n'a pas calculé 44^(44^44) mais les 44 derniers chiffres de 44^(44^(^44(^44...(44^44)...))) (44 fois le nombre 44)...
Concernant le "mod 10^44", il est bien plus rapide de convertir le dernier nombre en chaîne, puis d'en découper les 44 derniers chiffres.
Le script présenté en traduction Python de celui de Dattier garde (dans mon essai) 100 chiffres puis affiche les 44 derniers demandés.
Je l'ai depuis un peu enjolivé et il me sort :
* ... TETRATION ... *
* Calcul des 44 derniers chiffres de 44^^44 *
*************************************************
Affichage des 100 derniers chiffres :
5557690789238586682285142131824201389641731213663548150449376824492757966075731479288470062137081856
Extraction des 44 derniers chiffres :
49376824492757966075731479288470062137081856
Calculs exécutés en 0.017000913619995117 s
Noter que le temps de calcul n'est que de 17/1000e de sconde.
Raisonnable.
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#47 14-08-2018 13:39:52
Re : Calcul de Tétration
Bonjour,
@noter que pour le même calcul : j'ai 0.5 s d'attente avec Maple.
PS : j'ai une veille version (Maple 5 student) que j'avais acheté, environs 80 euros, quand j'étais étudiant.
Bonne journée.
Dernière modification par Dattier (14-08-2018 13:40:34)
Raisonnement Exact : A est exacte si avec 10 exemples et pas de contre-exemples connus des concernés
Hors ligne
#49 14-08-2018 19:41:19
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Re,
@Wiwaxia
Voilà, si j'ai bien compris tes notations,les variations de bn et an
Je repars de a=44 à chaque nouveau c.
b 1 = 1936 a 1 = 6
b 2 = 264 a 2 = 4
b 3 = 176 a 3 = 6
b 4 = 264 a 4 = 4
b 5 = 176 a 5 = 6
b 6 = 264 a 6 = 4
b 7 = 176 a 7 = 6
b 8 = 264 a 8 = 4
b 9 = 176 a 9 = 6
b10 = 264 a10 = 4
b11 = 176 a11 = 6
b12 = 264 a12 = 4
b13 = 176 a13 = 6
b14 = 264 a14 = 4
b15 = 176 a15 = 6
b16 = 264 a16 = 4
b17 = 176 a17 = 6
b18 = 264 a18 = 4
b19 = 176 a19 = 6
b20 = 264 a20 = 4
c = 2
b 1 = 1936 a 1 = 36
b 2 = 1584 a 2 = 84
b 3 = 3696 a 3 = 96
b 4 = 4224 a 4 = 24
b 5 = 1056 a 5 = 56
b 6 = 2464 a 6 = 64
b 7 = 2816 a 7 = 16
b 8 = 704 a 8 = 4
b 9 = 176 a 9 = 76
b10 = 3344 a10 = 44
b11 = 1936 a11 = 36
b12 = 1584 a12 = 84
b13 = 3696 a13 = 96
b14 = 4224 a14 = 24
b15 = 1056 a15 = 56
b16 = 2464 a16 = 64
b17 = 2816 a17 = 16
b18 = 704 a18 = 4
b19 = 176 a19 = 76
b20 = 3344 a20 = 44
c = 3
b 1 = 1936 a 1 = 936
b 2 = 41184 a 2 = 184
b 3 = 8096 a 3 = 96
b 4 = 4224 a 4 = 224
b 5 = 9856 a 5 = 856
b 6 = 37664 a 6 = 664
b 7 = 29216 a 7 = 216
b 8 = 9504 a 8 = 504
b 9 = 22176 a 9 = 176
b10 = 7744 a10 = 744
b11 = 32736 a11 = 736
b12 = 32384 a12 = 384
b13 = 16896 a13 = 896
b14 = 39424 a14 = 424
b15 = 18656 a15 = 656
b16 = 28864 a16 = 864
b17 = 38016 a17 = 16
b18 = 704 a18 = 704
b19 = 30976 a19 = 976
b20 = 42944 a20 = 944
c = 4
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 5184
b 3 = 228096 a 3 = 8096
b 4 = 356224 a 4 = 6224
b 5 = 273856 a 5 = 3856
b 6 = 169664 a 6 = 9664
b 7 = 425216 a 7 = 5216
b 8 = 229504 a 8 = 9504
b 9 = 418176 a 9 = 8176
b10 = 359744 a10 = 9744
b11 = 428736 a11 = 8736
b12 = 384384 a12 = 4384
b13 = 192896 a13 = 2896
b14 = 127424 a14 = 7424
b15 = 326656 a15 = 6656
b16 = 292864 a16 = 2864
b17 = 126016 a17 = 6016
b18 = 264704 a18 = 4704
b19 = 206976 a19 = 6976
b20 = 306944 a20 = 6944
c = 5
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 85184
b 3 = 3748096 a 3 = 48096
b 4 = 2116224 a 4 = 16224
b 5 = 713856 a 5 = 13856
b 6 = 609664 a 6 = 9664
b 7 = 425216 a 7 = 25216
b 8 = 1109504 a 8 = 9504
b 9 = 418176 a 9 = 18176
b10 = 799744 a10 = 99744
b11 = 4388736 a11 = 88736
b12 = 3904384 a12 = 4384
b13 = 192896 a13 = 92896
b14 = 4087424 a14 = 87424
b15 = 3846656 a15 = 46656
b16 = 2052864 a16 = 52864
b17 = 2326016 a17 = 26016
b18 = 1144704 a18 = 44704
b19 = 1966976 a19 = 66976
b20 = 2946944 a20 = 46944
c = 6
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 85184
b 3 = 3748096 a 3 = 748096
b 4 = 32916224 a 4 = 916224
b 5 = 40313856 a 5 = 313856
b 6 = 13809664 a 6 = 809664
b 7 = 35625216 a 7 = 625216
b 8 = 27509504 a 8 = 509504
b 9 = 22418176 a 9 = 418176
b10 = 18399744 a10 = 399744
b11 = 17588736 a11 = 588736
b12 = 25904384 a12 = 904384
b13 = 39792896 a13 = 792896
b14 = 34887424 a14 = 887424
b15 = 39046656 a15 = 46656
b16 = 2052864 a16 = 52864
b17 = 2326016 a17 = 326016
b18 = 14344704 a18 = 344704
b19 = 15166976 a19 = 166976
b20 = 7346944 a20 = 346944
c = 7
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 85184
b 3 = 3748096 a 3 = 3748096
b 4 = 164916224 a 4 = 4916224
b 5 = 216313856 a 5 = 6313856
b 6 = 277809664 a 6 = 7809664
b 7 = 343625216 a 7 = 3625216
b 8 = 159509504 a 8 = 9509504
b 9 = 418418176 a 9 = 8418176
b10 = 370399744 a10 = 399744
b11 = 17588736 a11 = 7588736
b12 = 333904384 a12 = 3904384
b13 = 171792896 a13 = 1792896
b14 = 78887424 a14 = 8887424
b15 = 391046656 a15 = 1046656
b16 = 46052864 a16 = 6052864
b17 = 266326016 a17 = 6326016
b18 = 278344704 a18 = 8344704
b19 = 367166976 a19 = 7166976
b20 = 315346944 a20 = 5346944
c = 8
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 85184
b 3 = 3748096 a 3 = 3748096
b 4 = 164916224 a 4 = 64916224
b 5 = 2856313856 a 5 = 56313856
b 6 = 2477809664 a 6 = 77809664
b 7 = 3423625216 a 7 = 23625216
b 8 = 1039509504 a 8 = 39509504
b 9 = 1738418176 a 9 = 38418176
b10 = 1690399744 a10 = 90399744
b11 = 3977588736 a11 = 77588736
b12 = 3413904384 a12 = 13904384
b13 = 611792896 a13 = 11792896
b14 = 518887424 a14 = 18887424
b15 = 831046656 a15 = 31046656
b16 = 1366052864 a16 = 66052864
b17 = 2906326016 a17 = 6326016
b18 = 278344704 a18 = 78344704
b19 = 3447166976 a19 = 47166976
b20 = 2075346944 a20 = 75346944
c = 9
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 85184
b 3 = 3748096 a 3 = 3748096
b 4 = 164916224 a 4 = 164916224
b 5 = 7256313856 a 5 = 256313856
b 6 = 11277809664 a 6 = 277809664
b 7 = 12223625216 a 7 = 223625216
b 8 = 9839509504 a 8 = 839509504
b 9 = 36938418176 a 9 = 938418176
b10 = 41290399744 a10 = 290399744
b11 = 12777588736 a11 = 777588736
b12 = 34213904384 a12 = 213904384
b13 = 9411792896 a13 = 411792896
b14 = 18118887424 a14 = 118887424
b15 = 5231046656 a15 = 231046656
b16 = 10166052864 a16 = 166052864
b17 = 7306326016 a17 = 306326016
b18 = 13478344704 a18 = 478344704
b19 = 21047166976 a19 = 47166976
b20 = 2075346944 a20 = 75346944
c = 10
b 1 = 1936 a 1 = 1936
b 2 = 85184 a 2 = 85184
b 3 = 3748096 a 3 = 3748096
b 4 = 164916224 a 4 = 164916224
b 5 = 7256313856 a 5 = 7256313856
b 6 = 319277809664 a 6 = 9277809664
b 7 = 408223625216 a 7 = 8223625216
b 8 = 361839509504 a 8 = 1839509504
b 9 = 80938418176 a 9 = 938418176
b10 = 41290399744 a10 = 1290399744
b11 = 56777588736 a11 = 6777588736
b12 = 298213904384 a12 = 8213904384
b13 = 361411792896 a13 = 1411792896
b14 = 62118887424 a14 = 2118887424
b15 = 93231046656 a15 = 3231046656
b16 = 142166052864 a16 = 2166052864
b17 = 95306326016 a17 = 5306326016
b18 = 233478344704 a18 = 3478344704
b19 = 153047166976 a19 = 3047166976
b20 = 134075346944 a20 = 4075346944
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
#50 14-08-2018 20:33:20
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 991
Re : Calcul de Tétration
Re,
@Dattier.
J'ai pensé à ton énigme, mais si je veux pouvoir dormir, il vaut mieux que que reporte la suite de mes réflexions à demain...
Donc les 167 derniers chiffres de G : ça devrait peut-être tourner autour de 167, puisque tu mets le doigt dessus.
Serait-il périodique de période 167 ? Ça se saurait...
Alors oui, pourquoi 167 et pas 168 ou 166 ? Déjà, c'est un nb premier. Mais il n'est pas le seul à l'être...
@+
Arx Tarpeia Capitoli proxima...
Hors ligne