Informatik zum Jahresanfang – noch mehr Teiler - Spoiler

[Rolf B]

Hallo Gunnar,

Ich bin vielleicht der letzte, der’s verstanden hat; aber ich glaube, jetzt hab auch ich es.

Nein, bist Du nicht, ich glaube, ich war's. Aber dafür versuche ich jetzt mal, es aufzuschreiben, am Beispiel der 7.

Man braucht für einen solchen Automaten einen Startzustand sowie einen Zustand R0 bis Rn für jeden möglichen Divisionsrest. Die Werte der Übergangsfunktion des Startzustandes sind identisch mit denen des Endzustandes. Er existiert nur, damit das leere Wort nicht als "teilbar durch N" akzeptiert wird. Endzustand ist logischerweise R0.

Man muss nun herausfinden, wie sich k und 10k mod 7 verhalten:

Wenn $$k \equiv n \pmod 7$$, dann ist $$10k = 7k+3k \equiv 0 + 3n \pmod 7$$. Mit $$p = (3n \bmod 7)$$ erhält man also den Status Rp, der bei Antreffen der Ziffer 0 auf den Rn folgen muss. Die übrigen ergeben sich fortlaufend automatisch: Zum Beispiel ist p=5 für n=4, damit hat der Zustand R4 die Übergänge

0,7 -> R5
1,8 -> R6
2,9 -> R0
  3 -> R1
  4 -> R2
  5 -> R3
  6 -> R4

Oder - aus FLACI kopiert, diese Deltafunktion:

 δ  0   1   2   3   4   5   6   7   8   9
R0	R0	R1	R2	R3	R4	R5	R6	R0	R1	R2
R1	R3	R4	R5	R6	R0	R1	R2	R3	R4	R5
R2	R6	R0	R1	R2	R3	R4	R5	R6	R0	R1
R3	R2	R3	R4	R5	R6	R0	R1	R2	R3	R4
R4	R5	R6	R0	R1	R2	R3	R4	R5	R6	R0
R5	R1	R2	R3	R4	R5	R6	R0	R1	R2	R3
R6	R4	R5	R6	R0	R1	R2	R3	R4	R5	R6

Ob das bei zweistelligen Teilern genauso funktioniert? Wenn $$k \equiv n \pmod{37}$$, was ist dann mit 10k?

$$10k = 37k - 27k \equiv 0 - 27n \pmod{37}$$, d.h. für $$p=(-27n) \bmod 37$$ erhält man zum Status n den Folgestatus p bei Antreffen der Ziffer 0. Dabei ist der Rest so zu bestimmen, dass er nicht negativ ist, d.h. es muss beispielsweise $$-27 : 37 = -1$$ mit Rest 10 gelten.

Auf den Zustand R1 müsste bei Antreffen der Ziffer 0 also der Zustand $$-27\cdot 1 \bmod{37}= 10$$ folgen, demzufolge bei Antreffen der 4 der Zustand R14. Und auf R14 der Zustand $$-27\cdot 14 \bmod{37}=29$$ für Ziffer 0, demzufolge R0 für Ziffer 8. Kurzer Blick auf den Taschenrechner: $$148=4\cdot 37$$ - scheint zu passen.

Ich bin total perplex, das hatte ich für unmöglich gehalten.

Rolf