17. AUFGABE DER WOCHE

Diese Woche hätte Herr Zwiwesa aufgrund des folgenden interessanten Phänomens fast seinen Lieblingssatz vergessen:

Seien b und s natürliche Zahlen mit b ≥ 2 und s ≥ 1 und bezeichne für natürliche a und b mit a ≥ b den bei der Disivion von a durch b mit Rest anfallenden Rest mit a(mod b). Sei O_{+} (bzw. O_{−}) die Abbildung, die eine s-stellige Zahl (z_{s}...z_{1})_{b} zur Basis b auf die s-stellige Zahl (z_{i_{m}}...z_{i_{1}})_{b} zur Basis b abbildet, wobei (z_{i_{m}}, ..., z_{i_{1}}) das bezüglich der Größe der z_{i} absteigend (bzw. aufsteigend) geordnete s-Tupel (z_{s}, ..., z_{1}) ist.

Nun betrachte man für ein n ≤ b^{s} − 1 das folgende Verfahren zur Konstruktion einer Folge (c_{i})_{i∈ℕ}:

• Wähle c_{0} := n.
• Setze c_{i+1} := O_{+}(c_{i})(mod O_{−}(c_{i})).

Sie Frage ist nun: Gibt es für jedes natürliche n ≤ b^{s} − 1 eine Stelle i ∈ ℕ in der obigen Folge, sodass c_{i} = (0...0)_{b}? Falls ja, gilt für die kleinste solche Stelle i_{0}, daß i_{0} ≤ b?

Beispiel: Sei b = 10, s = 4 und n = 1234. Dann gilt

c_{0} = (1234)_{10}.
c_{1} = (4321)_{10}(mod (1234)_{10}) = (0619)_{10},
c_{2} = (9610)_{10}(mod (0169)_{10}) = (0146)_{10},
c_{3} = (6410)_{10}(mod (0146)_{10}) = (0132)_{10},
c_{4} = (3210)_{10}(mod (0123)_{10}) = (0012)_{10} und
c_{5} = (2100)_{10}(mod (0012)_{10}) = (0000)_{10}.

und 5 ≤ 10.

http://www.math.uni-bielefeld.de/∼florian/adw/.