Algo décomposition en somme de puissances

Gilles old
Gilles old
dans Arithmétique
Bonjour,

Je débute en Python, j'ai voulu écrire un programme qui me permette de décomposer un entier $n$ en sommes d'exactement $k$ puissances $p$-ièmes d'entiers.

Je suis preneur de toutes améliorations.

Merci.

Gilles
def tri(L):
    L=[tuple(sorted(k)) for k in L]
    L=list(set(L))
    L.sort()
    L=[list(k) for k in L]
    return(L)

def sommespuissances(n,p,k):
    C=[j**p for j in range(0,n+1) if j**p<=n]
    if k==1:
        if n in C:
            return([[len(C)-1]])
        else:
            return([[]])
    else:
        L=[]
        for j in C:
            if j<=n//k:
                M=sommespuissances(n-j,p,k-1)
                if M!=[[]]:
                    for m in M:
                        m.insert(0,C.index(j))
                        L.append(m)
    return(tri(L))

Réponses

  • nicolas.patrois
    nicolas.patrois
    Quelques pistes :
    • sorted renvoie déjà un tuple mais c’est un détail.
    • C n’est pas du tout optimisé, imagine si n est grand. Utilise un while ou n**(1/p) pour borner.
    • si M==[[]], tu peux renvoyer [[]] tout de suite.
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Gilles old
    Gilles old
    Bonjour
    • Tu es sûr ? Si je fais sorted sur une liste, j'ai une liste en sortie.
    • Merci, c'est ce qui ralentissait considérablement mon programme.
    • Je ne peux pas faire ce que tu dis (return([[]])) car il se peut que décomposition fonctionne pour une valeur suivante de $j$
  • Gilles old
    Gilles old
    En revanche ce qui ne sert à rien c'est de faire M=[[]] alors que M=[] suffit.
    def sommespuissances(n,p,k):
    C,j=[],0
    while j**p<=n:
        C.append(j**p)
        j=j+1
    if k==1:
        if n in C:
            return([[len(C)-1]])
        else:
            return([])
    else:
        L=[]
        for j in C:
            if j<=n//k:
                M=sommespuissances(n-j,p,k-1)
                for m in M:
                    m.insert(0,C.index(j))
                    L.append(m)
    return(tri(L))
  • nicolas.patrois
    nicolas.patrois
    Tu voulais peut-être plusieurs décompositions ?
    Algebraic symbols are used when you do not know what you are talking about.
            -- Schnoebelen, Philippe
  • Gilles old
    Gilles old
    Oui je veux afficher toutes les décompositions une seule fois, rangées par ordre lexicographique, d'où ma fonction "tri".
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 7

Amadou +6 Invités