Voici un résumé de l'énoncé du problème 26 "Reciprocal cycles" du Project Euler (traduction complète en français ici) :

Find the value of d < 1000 for which \(1/d\) contains the longest recurring cycle in its decimal fraction part.

Compréhension du problème

Reformulons le problème : il nous faut trouver la valeur de \(d < 1000\) pour laquelle \(1/d\) contient la plus longue période dans son développement décimal. La question à se poser est : comment ferions-nous, manuellement, pour trouver la période, donc la longueur, du développement décimal d'une fraction de type \(1/n\) ? Tout simplement, en procédant au calcul des décimales de la fraction tant qu'un même reste n'est pas obtenu 2 fois. Par exemple, essayons de calculer les décimales de \(1/7\), ce qui nous donne :

• \(1/7 = 0 \times 7 + 1\)
• \(10/7 = 1 \times 7 + 3\)
• \(30/7 = 4 \times 7 + 2\)
• \(20/7 = 2 \times 7 + 6\)
• \(60/7 = 8 \times 7 + 4\)
• \(40/7 = 5 \times 7 + 5\)
• \(50/7 = 7 \times 7 + 1\)

Nous pouvons nous arrêter là dans le calcul des décimales car comme nous avons obtenu une 2ème fois le reste 1 et pouvons donc en déduire que nous allons obtenir de nouveau les mêmes divisions, donc les mêmes quotients/décimales. Nous pouvons donc en déduire que la longueur de la période du développement décimal de \(1/7\) est 6.

Cependant, le cas où \(n = 7\) est relativement pratique car la période commence directement à la première décimale, ce qui n'est pas le cas de toutes les fractions comme par exemple, \(1/4\) ou \(1/6\). Dans ces 2 cas, soit il n'y a pas de période, soit la période ne commence pas à la première décimale. Toutefois, nous pouvons remarquer que ces cas n'ont lieu que lorsque \(n\) est divisible par 2 ou par 5 et pouvons remarquer aussi que si \(n = 2^{j}5^{k}m\) avec \(m\) un nombre entier non divisible par 2 et par 5 et \(j\) et \(k\) des entiers dont au moins l'un des 2 n'est pas nul, alors la longueur de la période de \(1/n\) est égale à la longueur de la période de \(1/m\).

Ainsi, comme nous savons que si \(n\) est divisible par 2 ou par 5, nous n'obtiendrons pas une période plus longue qu'une déjà obtenue, nous pourrons nous permettre de ne prendre en compte, dans notre programme, que les fractions \(1/n\) avec n un entier non divisible par 2 et 5.

Le programme

Voici le programme Python que nous pouvons utiliser pour résoudre ce problème :

def cycle_length(den):
    reste = 10
    i = 0
    #Calcul des décimales tant que le reste n'est pas égal à 10
    while reste != 10 or i < 1:
        reste = (reste % den) * 10
        i += 1
    return i
longest = 0
for i in range(2, 1000):
    if i%2 != 0 and i%5 != 0:
        length = cycle_length(i)
        if length > longest:
            longest = length
            resultat = i
print(resultat)

Le résultat

La réponse à ce problème est 983.