În [1] părea că am ajuns pe aproape de un anumit rezultat; până a-l și formula complet… căutam totuși, o demonstrație. De fapt, revederea și întregirea lucrurilor (implicând și ceva adânciri teoretice asupra grafurilor orientate) ne va putea duce "direct", la rezultatul pe care îl intuisem; iar formularea "completă" pe care o așteptam… este de fapt complicată și chiar nu-i de obținut "manual".

Revederi și… frământări

Atm este "automatul modulo $M$" (mai jos, $M$ = 15); stările acestuia sunt desemnate prin resturile împărțirii la $M$ a numerelor naturale, iar trecerea (directă) din starea curentă în alta se face alipind formei binare a numărului curent, un bit — reprezentat aici prin culoarea arcului: "blue" pentru 1 și o nuanță de "yellow" pentru bitul 0:

Notă. Între timp am aflat că avem de fapt un "generalized De Bruijn graph": G_B(N, d) = (V, E) unde V = 0:(N-1) și (x, y) ∈ E iff y = dx + α pentru un α < d. În cazul nostru (de "automat mod $M$"), avem N = $M$ și d = 2 (fiindcă "alipirea bitului" revine la dublarea valorii reprezentate, urmată de adunare cu $0$ sau $1$). Odată… ne-am referit și noi la "șiruri binare de Bruijn" (v. "Reprezentarea binară minimală a lui $Z_{2^n}$", Recreații matematice nr. 2 / 2023).

Problema pusă consta în a caracteriza forma binară a multiplilor de $M$ (= 15), ceea ce revine la a găsi expresia regulată asociată automatului Atm în care (fiindcă restul multiplilor față de $M$ este zero) fixăm "$0$" ca stare inițială și ca stare finală.

Pentru orice multiplu de $M$, forma binară se obține plecând din nodul "0" și alipind succesiv biții întâlniți pe arcele unui ciclu; iar plecând din "0" pe un drum care duce la o stare $t\ne 0$, obținem forma binară a unui număr cu restul $t$ față de $M$.
De exemplu (pentru $M$=15), drumul $11-8-2$ transformă forma binară a unui număr $x$ cu restul 11 față de $M$, în aceea a unuia cu restul 2 (alipind succesiv câte un bit 1):
$x\,\mathrm{mod}\,15=11 \rightarrow 2x+1\,(\mathrm{mod}\,15)=22 +1\,(\mathrm{mod}\,15)=8$, iar $2*8+1\,(\mathrm{mod}\,15)=2$.

De observat că avem șase cicluri simple de câte 4 noduri: trei formate fiecare cu arce "blue" (=1): $0-1-3-7-0$, $2-5-11-8-2$ și $10-6-13-12-10$; și trei formate cu arce 0: $1-2-4-8-1$, $12-9-3-6-12$ și $13-11-7-14-13$.
Ciclurile cu mai mult de 4 noduri îmbină aceste 6 cicluri simple și folosesc eventual și "ciclurile banale" (4, 9, 4), (14, 14) și (5, 10, 5).
(abia mai târziu, am înțeles că aspectul esențial este cum "îmbină"…)

Reuniunea celor șase cicluri simple (de câte 4 vârfuri) acoperă toate vârfurile (și conține 24 arce); adăugând și cele 6 arce din "ciclurile banale", obținem (v. algoritmul lui Hierholzer) un ciclu eulerian (Atm este conex (chiar "tare-conex"), iar gradele de intrare sunt respectiv egale cu cele de ieșire — deci într-adevăr, Atm este un graf eulerian):

> eulerian_cycle(Atm)
$epath  # arcele consecutive ale ciclului eulerian
+ 30/30 edges from de906ef (vertex names):
 [1] 0 ->0  0 ->1  1 ->2  2 ->4  4 ->8  8 ->1  1 ->3  3 ->6  6 ->12 12->10
[11] 10->6  6 ->13 13->12 12->9  9 ->4  4 ->9  9 ->3  3 ->7  7 ->14 14->14
[21] 14->13 13->11 11->8  8 ->2  2 ->5  5 ->10 10->5  5 ->11 11->7  7 ->0 
$vpath  # vârfurile ciclului eulerian
+ 31/15 vertices, named, from de906ef:
 [1] 0  0  1  2  4  8  1  3  6  12 10 6  13 12 9  4  9  3  7  14 14 13 11 8  2 
[26] 5  10 5  11 7  0 

(abia mai târziu, am observat că din acest ciclu eulerian putem constitui un arbore de acoperire și apoi — în loc de ciclurile noastre "de bază"— un set just de cicluri fundamentale…)

Rezultă (…până acuși) că pentru orice multiplu de $M$, forma binară a sa este constituită, prin concatenare și eventual repetare, din unele (eventual, numai una) dintre formele binare asociate celor 9 cicluri evidențiate mai sus — întărind la prima vedere, rezultatul din [1] (unde angajam find_cycles(), găsind 14 cicluri simple "de bază" (dar fără nodul 14), la care adăugam un ciclu "ne-simplu" dar care trecea și prin nodul 14).

Dar… ajunge "concatenare"? Pentru legarea unor cicluri, ultimul nod din ciclul curent trebuie să fie primul din următorul ciclu; cu alte cuvinte… ar fi de avut în vedere și unele dintre permutările circulare ale vârfurilor fiecărui ciclu ?
Nu neapărat… N-am avea nevoie de "permutări circulare", fiindcă nu nodurile ne interesează, ci formele binare ale ciclurilor — iar în fiecare dintre cele 9 cicluri, arcele sunt marcate cu câte o aceeași culoare (deci formele binare asociate respectiv celor 9 cicluri au toți biții de câte o aceeași valoare, încât nu mai are importanță ordinea vârfurilor).

Doar că, avem de concatenat (sau imbricat) cicluri în multe locuri intermediare…
Arcul "de plecare" este $0-1$, deci trebuie să plecăm de la ciclul $0-1-3-7-0$ (care include deasemenea, arcul final $7-0)$.
Ajunși în starea "1", putem continua fie cu arcul $1-2$, fie cu arcul $1-3$; folosind operatorul regulat '|' ("alege una dintre posibilități"), putem exprima porțiunea inițială a ciclului din "0" pe care vrem să-l constituim, prin "0$-$1($-$2 | $-$3)".
Este de întrevăzut că vom avea de plasat multe paranteze și mulți operatori "|" și "*" ("repetă de zero sau mai multe ori"); de exemplu, în locul "$-2$" putem insera (și repeta) ciclul 1-2-4-8-1; analog în locul "$-3$" — încât porțiunea inițială curentă capătă expresia "0$-$1(($-$2$-$4$-$8$-$1)* | $-$3$-$7$-$0*)" (încheiem, în starea "0"). Bineînțeles că la fel avem de procedat mai departe (și… mai departe), înserând în locurile curente "$-2$", "$-3$" etc., cicluri care pleacă din aceste locuri.

În final (dacă ar fi să ducem astfel lucrurile, până la starea finală "0"), obținem expresia regulată a formei binare a multiplilor de $M$ (=15), culegând biții de pe arcele ciclului format; de exemplu, porțiunii inițiale constituite mai sus îi corespunde expresia binară regulată "(1((0000)*|(1110*)))*" (de observat în treacăt că din ea, putem deriva de exemplu, forma binară "1(0000)*111", de valoare $2^{\boldsymbol{4k+3}}+7$ — care se vede ușor că este multiplu de 15 (pentru k≥0 repetiții ale grupului de 4 biți '0')).

Frământând cele de mai sus, constatăm mai întâi, că ne-a scăpat faptul că pe lângă cele 9 cicluri, avem de considerat și două cicluri de câte trei noduri: $2-4-8-2$ și $10-6-12-10$ (care au fiecare, câte un arc de altă culoare decât celelalte două, încât pentru ele vor trebui considerate și permutări circulare).
De exemplu, expresia regulată ințială evocată mai sus ar deveni (incluzând ciclul $2-4-8-2$, repetat de zero sau mai multe ori) "10(001)*000111".
Deci (ținând seama că pentru un ciclu de 3 noduri, cu arce și 1 și 0, avem de considerat 3 permutări circulare) am avea 9+6=15 cicluri "de bază" — dar altele ("mai logic" alese), decât cele extrase automat prin find_cycles() în [1].

Dar… trebuie să mai constatăm, cam răsturnând ceea ce credeam "la prima vedere" mai sus, că nu este adevărat, că oricare ciclu din Atm "se poate exprima" prin ciclurile de bază ale noastre; "culegeam" mai sus, biții câte unui ciclu, dar nu consecutiv, ci intercalând în anumite locuri biți de pe arce ale unor alte cicluri.
De exemplu, ciclul $0-1-3-6-13-11-7-0$ nu se poate exprima prin cicluri "de bază": este adevărat că implică ciclul $0-1-3-7-0$, dar numai "pe porțiuni", intercalând nu vreun alt ciclu, ci doar câte un arc de pe alte două cicluri "de bază".
Sintagma "se poate exprima" poate avea doar acest sens (nicidecum, "concatenare", sau "imbricare"): se reunesc porțiuni ale unora dintre ciclurile "de bază"…

În concluzie să zicem, mai sus am cam amestecat lucrurile… Plecând din $0$ și culegând biții de pe arce consecutive, ajungem într-adevăr, la expresia regulată a formei binare a unui multiplu de $M$ — dar procedeul derulat mai sus ține de parcurgerea în lățime a grafului și nicidecum, de "ciclurile de bază"!