Nombres derviches

Soit à faire tourner le nombre x d'un cran vers la droite en le multipliant par 2
Soit b son dernier chiffre et a le nombre formé des autres chiffres.
C'est à dire que x = ab = 10a + b, avec 10^n-1≤ a <10ⁿ, n étant le nombre de chiffres de a.
2x = 20a + 2b = 10ⁿb + a : après rotation circulaire d'un cran à droite ab devient ba
Ceci s'écrit 19a = (10ⁿ - 2)b
Comme b < 10 est premier avec 19, 19 divise 10ⁿ - 2, soit 10ⁿ ≡ 2 mod 19
Le reste de 10ⁱ mod 19 est périodique. La période étant un diviseur de φ(19) = 18.
C'est à dire que 10ⁱ ≡ 1 mod 19 pour un i diviseur de 18, au pire 10¹⁸ ≡ 1 mod 19 (petit théorème de Fermat).

On peut tester les diviseurs de 18 = 2×3² :
10² ≡ 5 mod 19
10³ ≡ 12 mod 19
10⁶ ≡ 144 ≡ 11 mod 19
10⁹ ≡ 132 ≡ 18 mod 19
et donc la période est 18 lui même.
C'est à dire que tous les restes de 10ⁱ, 0 ≤ i < 18 modulo 19 sont différents.
Comme cela fait 18 restes différents, ces restes prennent les 18 valeurs 1 à 18.
En particulier il existe un et un seul exposant 10ⁿ ≡ 2 mod 19, 0 ≤ n < 18
Essayer les 18 exposants serait fastidieux, mais une petite remarque : 2×10 = 20 ≡ 1 ≡ 10¹⁸ mod 19

Donc 10¹⁷ ≡ 2 est l'exposant cherché !
19a = (10¹⁷ - 2)b donne a = 5263157894736842×b
Mais a doit avoir 17 chiffres, ce qui donne b = 2 comme plus petite solution.

105263157894736842 × 2 = 210526315789473684

b = 3 donne 157894736842105263
b = 4 donne 210526315789473684
b = 5 donne 263157894736842105
b = 6 donne 315789473684210526
b = 7 donne 368421052631578947
b = 8 donne 421052631578947368
b = 9 donne 473684210526315789
enfin b = 1 donne 052631578947368421, si on accepte d'écrire ça ainsi (avec le premier chiffre = 0).
On remarque que toutes ces solutions sont des permutations circulaires de 105263157894736842
Le nombre 105263157894736842 est un nombre derviche qui tourne en le multipliant par 2,3,4,5,6,7,8,9.

Une méthode intuitive serait de choisir arbitrairement b = 1 et trouver successivement les chiffres de a :
2×1 = 2 est le dernier chiffre de a, puis en multipliant par 2 succesivement
2×2 = 4
2×4 = 8
2×8 = 6 retenue 1
2×6 +1 = 3 retenue 1
2×3 + 1 = 7
2×7 = 4 retenue 1
2×4 + 1 = 9
2×9 = 8 retenue 1
2×8 + 1 = 7 retenue 1
2×7 + 1 = 5 retenue 1
2×5 + 1 = 1 retenue 1
2×1 + 1 = 3
2×3 = 6
2×6 = 2 retenue 1
2×2 + 1 = 5
2×5 = 0 retenue 1
2×0 + 1 = 1
et on reboucle cycliquement à partir de ce point.
On obtient ainsi la solution 052631578947368421, que l'on peut faire tourner d'un cran si le 0 initial est rejeté.

Mais cette méthode ne garantit pas que l'on obtienne la plus petite solution !
En l'appliquant au multiplicateur 5, on obtient 020408163265306122448979591836734693877551 (ou après rotation d'un cran 102040816326530612244897959183673469387755), plus petit nombre qui tourne d'un cran en le multipliant par 5. Euh... c'est 142857 !

Il faudrait répéter la méthode pour chaque valeur de b pour déterminer la plus petite solution.
Avec b = 7, on obtient bien le 142857 attendu, par contre toute autre valeur de b donne un nombre à 42 chiffres.
La méthode fonctionne toutefois pour les autres valeurs du multiplicateur m. Elle permet ainsi d'obtenir la plus petite solution pour m = 6 :
1016949152542372881355932203389830508474576271186440677966 (après rotation d'un cran)
Et ce sans avoir besoin de traiter des nombres de 58 chiffres en tant que tels : les chiffres sont obtenus un à un, le plus grand nombre traité est 9×6 + 5 = 59.

m = 2 : 105263157894736842 m = 3 : 1034482758620689655172413793 m = 4 : 102564 m = 5 : 142857 (et non pas 102040816326530612244897959183673469387755) m = 6 : 1016949152542372881355932203389830508474576271186440677966 m = 7 : 1014492753623188405797 m = 8 : 1012658227848 m = 9 : 10112359550561797752808988764044943820224719

Revenons au cas général et à l'équation (10m - 1)a = (10ⁿ - m)b, 1≤b≤9, 10^n-1≤a<10ⁿ
il faut alors considérer les diviseurs d de 10m - 1
m = 2 : 19 est premier, déja traité
m = 3 : 29 est premier et se traite de même
m = 4 : 39 = 3×13, et donc 10ⁿ - 4 multiple de 13 ou de 39
m = 5 : 49 = 7² et 10ⁿ - 5 multiple de 7 ou de 49
m = 6 : 59 est premier
m = 7 : 69 = 3×23, donc 10ⁿ - 7 multiple de 23 ou de 69
m = 8 : 79 est premier
m = 9 : 89 est premier

On cherche alors l'ordre de 10 modulo d, c'est à dire le plus petit k tel que 10^k ≡ 1 mod d
Le théorème d'Euler-Fermat affirme juste 10^φ(d) ≡ 1 mod d pour tout nombre d premier avec 10.
Bien sûr l'ordre de 10 modulo d est défini seulement pour tout nombre premier avec 10, il n'a aucun sens si PGCD(d, 10) ≠ 1
Le script suivant calcule φ(d), indicateur d'Euler, et l'ordre de 10 modulo d.
De façon générale k est un diviseur de φ(d), et si d est premier φ(d) = d - 1
Si d est un "nombre premier long", l'ordre de 10 est d - 1 lui même.

Calcul de l'ordre de 10 modulo d :

d =

On notera que pour m = 5, on peut décider que 10ⁿ - 5 multiple de 7, et l'ordre est 6, mais que si on prend 10ⁿ - 5 multiple de 49, alors l'ordre est 42 ! Ce qui explique l'anomalie obtenue pour m = 5

On a ainsi la longueur du nombre derviche cherché :
En posant 10m - 1 = f.d, d étant le diviseur de 10m - 1 choisi
10ⁿ ≡ m mod d, soit 10ⁿ⁺¹ ≡ 10m ≡ f.d + 1 ≡ 1 mod d et donc n = k - 1.
On obtient alors f.a = b×(10^k-1 - m)/d, k étant l'ordre de 10 modulo d.
Dans le cas où 10m - 1 est composé (m = 4, 5, 7) il faut tester les différents cas.
Par exemple m = 4, p = 39. En fait il y a deux cas à traiter :
3a = b×(10⁵ - 4)/13 = 7692 b, puisque φ(13) = ordre = 6
et le cas a = b×(10⁵ - 4)/39 = 2564 b puisque φ(13) = ordre = 6 aussi.
Bien sûr puisque 7692 = 3×2564, le premier cas donne les solutions du second pour b = 3, 6, 9 et seul le second suffit pour les avoir toutes :
025641, 051282, 076923, 102564, 128205, 153846, 179487, 205128, 230769

Par contre pour le cas m = 5, il faut bien entendu retenir uniquement l'ordre le plus petit !
a = b×(10⁴¹ - 5)/49 (ordre mod 49 = 42) n'offre que peu d'intérêt par rapport à 7a = b×(10⁵ - 5)/7 (ordre de 7 = 6)
Le dernier cas composé qui nous intéresse (m = 7) donne des résultats semblables à m = 4.

On notera aussi que la périodicité de 10ⁱ mod d donne des solutions plus grandes par simple répétition,
par exemple 102564102564, répétition de 102564, tourne aussi d'un cran en le multipliant par 4.

Rotation à gauche

En considérant le chiffre de gauche a et le reste du nombre b, x = 10ⁿa + b, 10^n-1 ≤ b < 10ⁿ et 1 ≤ a ≤ 9
alors m.x = m.10ⁿa + m.b = 10b + a soit  (m.10ⁿ - 1)a = (10 - m)b 

m = 2, alors (2.10ⁿ - 1)a = 8b
8 = 2³ est premier avec 2.10ⁿ - 1 impair, a est donc multiple de 8, soit a = 8.
Alors b = 2.10ⁿ - 1 ≥ 10ⁿ, donc c'est impossible.

m = 3, (3.10ⁿ - 1)a = 7b et donc soit a = 7, soit 7 divise 3.10ⁿ - 1
a = 7 donne b = 3.10ⁿ - 1 > 10ⁿ
Reste 3.10ⁿ ≡ 1 mod 7. En multipliant par 5, inverse de 3 modulo 7 : 10ⁿ ≡ 5 mod 7
Soit n = 5 et b = a(3.10⁵ - 1)/7 = 42857 × a
Comme 10⁴ ≤ b < 10⁵, a = 1 ou 2 qui donnent  142857 et 285714 

m = 4, (4.10ⁿ - 1)a = 6b, donc a pair = 2a' = 2,4,6,8
(4.10ⁿ - 1)a' = 3b, soit b = (4.10ⁿ - 1)a'/3 > 10ⁿ, impossible

m = 5, (5.10ⁿ - 1)a = 5b.
a = 5 donne b > 10ⁿ, et sinon 5.10ⁿ - 1 est premier avec 5.

m > 5, (m.10ⁿ - 1)a = (10-m)b, avec 10-m < 5 < m
alors b = (m.10ⁿ - 1)a/(10-m) ≥ (m.10ⁿ - 1)/(10-m) > 10ⁿ

Il y a donc une seule possibilité de rotation à gauche d'un chiffre :

le multiplicateur est 3, la plus petite solution est 142857

Et bien sûr des solutions plus grandes, par répétition ou en partant de 285714 :
285714, 142857142857, 285714285714 ...