Ce site est optimisé pour être consulté depuis un navigateur moderne dans lequel JavaScript est activé.

Calcul de Tétration

Dattier

choses moins intéressantes

Dattier

choses moins intéressantes

[supprimé]

Salut
Je suis la personne à l'origine de l'énigme.
En calculant un peu plus que les 44 derniers chiffres vous devriez trouver votre erreur.
(A moins que ce soit moi qui me soit planté...)

Dattier

choses moins intéressantes

Pierrro

Apparemment, le 44ème chiffre serait un 4.

Dattier

@Roubaud : oui mes calculs sont faux, à cause de l'incohérence dont j'ai parlé.

Dattier

choses moins intéressantes

Pierrro

C'est le même résultat que la toute première proposition.

[supprimé]

Merci Dattier ! Tu avais vu juste.
Grace à toi j'ai compris mon erreur.

Dattier

choses moins intéressantes

Dattier

@Roubaud : avec plaisir.

Pierrro

En tous cas, merci pour le coup de main et la trituration de méninges.
Bonne fin de journée.

yoshi

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

Dattier

choses moins intéressantes

yoshi

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...

Dattier

A demain.

yoshi

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 ?

from decimal import Decimal as D, getcontext
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.

@+

Dattier

choses moins intéressantes

yoshi

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...

@+

Dattier

choses moins intéressantes

« Page précédente Page suivante »