Transformationen

Zunächst formulieren wir das Zahlenpaar (x; y) um in (x; x+n); n ist also die Differenz zwischen y und x und ist positiv.

Wenn wir

T₁: (x,y) → (x+1, 2*(x+n))

n mal anwenden erhalten wir

(x+n ; 2^n*x + 2^n*n)

Wenn wir

T₂: (x,y) → (2*x, x+n+1)

(n-b) mal anwenden, erhalten wir

(2^(n-b)*x + 2^(n-b)*n ; 2^n*x + 2^n*n + n - b)

b ist eine Zahl unserer Wahl kleiner als n, (n-b) ist also positiv.

Nun wenden wir einmal T₁ an:

(2^(n-b)*x + 2^(n-b)*n + 1  ;  2^(n+1)*x + 2^(n+1)*n + 2n - 2b)

Schließlich wenden wir (b-1) mal T₂ an:

(2^(n+1)*x + 2^(n+1)*n + 2^(b+1)  ;  2^(n+1)*x + 2^(n+1)*n + 2n - b + 1)

Die Differenz dieser beiden Zahlen ist der Absolutwert von

| 2^(b+1) + b - (2n + 1) |

Wir erinnern uns, dass die Differenz der beiden ursprünglichen Zahlen n ist. Die Frage ist nun, ob es eine Zahl b gibt, sodass die neue Differenz kleiner als n ist, egal, wie groß die Zahl n ist:

| 2^(b+1) + b - (2n + 1) |  <  n

Dies ist immer der Fall, mit Ausnahme von n=1. Wie wir den oben beschriebenen Algorithmus mehrfach anwenden, wird die Differenz der beiden Zahlen immer kleiner, bis sie schließlich 1 oder 2 wird.

Wenn die Differenz 2 ist, führt eine weiterer Durchlauf mit b=1 zu zwei gleichen Zahlen.

Wenn die Differenz 1 ist, führen folgende Schritte zu einem Zahlenpaar mit der Differenz 2:

(x        ;  x+1) ... ein  Zahlenpaar mit der Differenz 1
(x+1   ; 2x+2)  
(x+2   ; 4x+4)
(2x+4 ; 4x+5)
(4x+8 ; 4x+6) ... ein  Zahlenpaar mit der Differenz 2