Diviseurs de leur somme

Fermeture

Le premier défi d’avril 2021 sur Images des mathématiques propose de chercher les triplets d’entiers positifs (a, b, c) dans l’ordre croissant et sans diviseur premier commun tels que chacun des trois divise la somme des deux autres. Je propose ici une résolution et l’extension du problème à des listes plus longues d’entiers.

Résolution pour les triplets

Chaque entier étant un diviseur de lui-même, la condition du défi est équivalente à la propriété que chacun des entiers du triplet divise leur somme (notée s).

L’absence de diviseur premier commun interdit la solution nulle, donc la somme est strictement positive. Par conséquent aucun des entiers du triplet, qui divisent tous s, ne peut être nul.

Les inégalités abc impliquent s ≤ 3c donc s/c ∈ {1, 2, 3}.

  1. Le cas s = c est impossible car 0 < ab.
  2. Le cas s = 2c implique c = a + b ≤ 2b ≤ 2c donc 2 ≤ s/b ≤ 4. Mais le sous-cas s = 2b donne a = 0. Il ne reste qu’à calculer a dans chacun de ces cas s = 3b et s = 4b, ce qui donne les triplets (s/6, s/3, s/2) et (s/4, s/4, s/2).
  3. Le cas s = 3c donne les inégalités sa + 2c ≤ 3c = s donc il s’agit d’égalités et a = b = c = s/3.

Les seuls triplets solutions sont donc (1, 2, 3), (1, 1, 2) et (1, 1, 1).

Généralisation

Soit n un entier strictement positif. On cherche maintenant les listes (croissantes) (a1, … , an) entiers strictement positifs qui sont tous diviseurs de leur somme s, mais qui n’admettent aucun diviseur premier commun. De façon équivalente, on cherche les décompositions de 1 en n inverses d’entiers positifs di = s/ai.

Y a-t-il toujours un nombre fini de solutions et peut-on l’exprimer ou l’encadrer en fonction de n ? Les solutions vérifient-elles toujours a1 = 1 comme dans le cas n = 3 ?

La finitude découle assez rapidement du fait que snan donc dnn, puis connaissant les diviseurs (dk+1, … , dn), on a s − i=k+1n ai = i=1k aikak donc dk = s/aksk/(si=k+1nai) = k/(1 − i=k+1n1/di).

Pour tout k > 1, l’inégalité stricte ak < i=1k ai = s − i=k+1n ai donne aussi dk > s/(si=k+1nai) = 1/(1 − i=k+1n 1/di).

On peut programmer ensuite la recherche exhaustive des solutions grâce à ces inégalités.

def pgcd(a,b):
    while b:
        a,b=b,a%b
    return a

def partageUnite(n):
    """Recherche de toutes les listes croissantes de n entiers strictement positifs
    (d_1, … , d_n) dont la somme des inverses vaut 1.
    Les solutions sont construites itérativement à l’aide d’une pile
    de quintuplets (k, a, b, m, d)
    où k est le nombre de termes manquants,
    a/b est le complément à 1 de la somme des inverses des termes d de la pile
    m est un majorant pour la valeur de d suivante"""
    n=int(n)
    assert n>1
    pile=[]
    k,a,b,m,d=n,1,1,n,0
    recherche=True
    j=0
    while recherche:
        for i in range(k,2,-1):
            d=max(d,b//a+1)
            pile.append((i,a,b,m,d))
            c=pgcd(b,d)
            f=d//c
            a,b=a*f-b//c,b*f
            m=(i-1)*b//a
        k=2
        d=max(d,b//a+1) # avant-dernier terme
        q,r=a*d-b,b*d
        if r%q==0: # le dernier complément q/r est bien l’inverse d’un entier
            yield [t[4] for t in pile]+[d,r//q]
        while d==m:
            if pile:
                k,a,b,m,d=pile.pop()
            else:
                d,m=0,1
                recherche=False
        d+=1

def diviseursSomme(n):
    """Recherche de toutes les listes croissantes de n entiers strictement positifs
    tous diviseurs de leur somme mais sans diviseur premier commun.
    """
    for l in partageUnite(n):
        p=1
        for j in l:
            p*=j//pgcd(p,j) # calcul du PPCM
        yield [p//j for j in l]

Le nombre de solutions parait croître de façon exponentielle pour n ≤ 6 :

Nombre de solutions par longueur de liste
Longueur de liste23456
Nombre de solutions 13141473462

Mais pour n = 7, le nombre de solutions semble supérieur à 100 000.

Un internaute (drai.david) me signale dans les commentaires de la page du défi que la suite est référencée sur l’encyclopédie en ligne des suites d’entiers (OEIS) sous la référence A002966.