← nimbers

La roue lcm

Enroulez autour d'un même centre les rubans 010101…, 001001…, 00010001… : l'anneau k porte un 1 sur chaque multiple de k. Pour que tous les rubans se referment ensemble, la roue doit compter lcm(2, 3, …, m) secteurs, un nombre derrière lequel se cache la fonction de Tchebychev.

Anneau 2 à l'extérieur, anneau m au centre, secteur 0 en haut. Touchez un secteur pour le lire. Les anneaux redondants sont en teinte lavée ; les traits dorés marquent les rayons qui portent le même code que le rayon lu.
Vue déroulée autour du rayon lu : chaque ligne est un ruban, la colonne dorée est le rayon. Après L − 1, la numérotation revient à 0 : la roue se referme.

Une circonférence en eψ(m)

Notons L(m) = lcm(1, 2, …, m) le nombre de secteurs. Pour m = 2, 3, 4, … on obtient 2, 6, 12, 60, 60, 420, 840, 2 520, 2 520, 27 720 (suite A003418). Son logarithme est la fonction de Tchebychev :

ln L(m) = ψ(m) = Σn ≤ m Λ(n)

Ajouter l'anneau m multiplie donc la roue par eΛ(m) : par p si m = pa, par 1 sinon. Dans ce second cas l'anneau est redondant. Si m = ab avec a, b > 1 premiers entre eux, alors m ∣ n ⟺ (a ∣ n et b ∣ n) : l'anneau 6 n'est que le ET logique des anneaux 2 et 3. Enfin, le théorème des nombres premiers, sous la forme ψ(m) ~ m, dit que la roue grossit comme em(1 + o(1)) : L(20) = 232 792 560, et ln L(20) ≈ 19,27.

Ce qu'un rayon raconte

Le rayon n traverse tous les anneaux et porte un 1 sur l'anneau k exactement quand k divise n. Comme chaque k ≤ m divise L, on a k ∣ n ⟺ k ∣ pgcd(n, L) : le code ne dépend que de g = pgcd(n, L). Il le détermine aussi, car chaque puissance de premier pj ≤ m a son anneau. Le code de g revient donc sur φ(L/g) rayons, et la roue se partage en autant de classes que L a de diviseurs. Compter les rayons classe par classe redonne l'identité de Gauss :

Σd ∣ L φ(d) = L

Les rayons muets

Un rayon qui ne porte que des 0 vérifie pgcd(n, L) = 1 ; il y en a φ(L). Ils forment la roue des cribles de nombres premiers (wheel factorization) : un premier p > m est premier avec tous les entiers de 2 à m, il tombe donc toujours sur un rayon muet. La réciproque est fausse : sur la roue de 60, le rayon 49 est muet alors que 49 = 7².

Combien de codes différents

Le nombre de codes distincts, d(L(m)), est la suite A056793 : 1, 2, 4, 6, 12, 12, 24, 32, 48, 48, 96, … Chaque premier p ≤ m y contribue par son nombre d'anneaux plus un, et une formule de Singh (2022) le réécrit étage par étage :

d(L(m)) = Πp ≤ m (⌊logp m⌋ + 1) = Πk ≥ 1 (1 + 1/k)π(m1/k)

Elle se lit en miroir de ψ(m) = Σk ≥ 1 θ(m1/k). La circonférence pèse chaque premier par ln p ; le nombre de codes se contente de le compter, avec un poids ln(1 + 1/k) à l'étage k. L'anneau pk multiplie ainsi les secteurs par p, mais les codes seulement par (k + 1)/k. Au total, log2 d(L(m)) ~ π(m) : environ un bit par nombre premier, face à em(1 + o(1)) secteurs.

Un tamis plutôt qu'une boussole

Comme roue à encoder, elle n'est pas absolue. Puisque k ∣ n ⟺ k ∣ L − n, la roue est symétrique par rapport à l'axe du rayon plein, et chaque code a au moins son reflet. Un code n'est unique que si φ(L/g) = 1, c'est-à-dire L/g ∈ {1, 2} : seuls les deux rayons de l'axe, 0 et L/2, sont reconnaissables à coup sûr. La roue ne dit pas où l'on est, elle dit de quoi l'on est fait.

Pour une version absolue, l'anneau de chaque puissance de premier q devrait indiquer n mod q en entier, et pas seulement « divisible ou non ». Le théorème chinois des restes recolle alors une position unique modulo L. C'est le principe du nonius des codeurs absolus : deux pistes de N et N − 1 périodes par tour donnent la position modulo N − 1 et modulo N.

Le phare

Posez une lampe au centre de la roue et rendez les traits opaques : la lumière ne sort que par les rayons muets, ceux qu'aucun anneau ne marque. La roue alignée est le meilleur phare possible, avec φ(L) faisceaux (suite A217863). Ils pointent vers tous les nombres premiers supérieurs à m, mais aussi vers quelques intrus, comme 49 sur la roue de 60 : le phare montre des candidats, pas des certitudes.

Le phare de la roue lcm Une lampe au centre éclaire à travers les secteurs où aucun anneau ne porte de trait.

Tourner un anneau d'un cran

Anneaux de l'extérieur vers le centre, dans l'ordre des boutons. Touchez un anneau sur la roue ou utilisez les boutons pour le faire tourner.

Faites tourner les anneaux : la lumière se déplace, et certains réglages l'éteignent complètement. Une roue d'où ne sort aucun faisceau, c'est un système couvrant, une famille de congruences n ≡ ai (mod mi) que tout entier vérifie au moins une fois. Erdős les a inventés en 1950. L'exemple classique, avec les modules 2, 3, 4, 6 et 12, garde les anneaux 2 et 3 en place et tourne l'anneau 4 d'un cran, l'anneau 6 de cinq crans et l'anneau 12 de sept crans.

En testant tous les réglages, le nombre minimal de faisceaux vaut 1, 2, 2, 8, 4, 24, 24, 48, 36, 360 pour m = 2 à 11, puis tombe à 0 dès m = 12. Un anneau premier ne fait que multiplier la lumière restante par 1 − 1/p, quel que soit son réglage : tout se joue sur les puissances de premiers et les anneaux composés.

Une lanterne noire à modules distincts n'est jamais exacte, avec chaque entier couvert une seule fois. Si c'était le cas, on aurait Σ zai/(1 − zmi) = 1/(1 − z). En approchant z d'une racine primitive M-ième de l'unité, où M est le plus grand module, un seul terme exploserait (Mirsky–Newman, Davenport–Rado).

Reste la question d'Erdős et Selfridge, ouverte à ce jour : peut-on éteindre le phare avec des anneaux de périodes impaires, toutes distinctes ? Leurs ombres devraient d'abord suffire, Σ 1/mi ≥ 1, ce qui force leur ppcm N à vérifier σ(N) ≥ 2N. Ce serait un nombre impair abondant (ou parfait, s'il en existe), donc au moins 945, et une preuve vérifiée en Lean a repoussé ce seuil au-delà de 10 000 en 2026. Hough et Nielsen ont montré que tout système couvrant à modules distincts contient un module divisible par 2 ou par 3, et Balister, Bollobás, Morris, Sahasrabudhe et Tiba ont exclu le cas des modules sans facteur carré.

Références