Diviseurs de leur somme

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 a ≤ b ≤ c impliquent s ≤ 3c donc s/c ∈ {1, 2, 3}.

1. Le cas s = c est impossible car 0 < a ≤ b.
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 s ≤ a + 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) (a₁, … , a_n) 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 d_i = s/a_i.

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 a₁ = 1 comme dans le cas n = 3 ?

La finitude découle assez rapidement du fait que s ≤ na_n donc d_n ≤ n, puis connaissant les diviseurs (d_k+1, … , d_n), on a s − ∑_i=k+1ⁿ a_i = ∑_i=1^k a_i ≤ ka_k donc d_k = s/a_k ≤ sk/(s − ∑_i=k+1ⁿa_i) = k/(1 − ∑_i=k+1ⁿ1/d_i).

Pour tout k > 1, l’inégalité stricte a_k < ∑_i=1^k a_i = s − ∑_i=k+1ⁿ a_i donne aussi d_k > s/(s − ∑_i=k+1ⁿa_i) = 1/(1 − ∑_i=k+1ⁿ 1/d_i).

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 :

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.