Anstatt mit Baumsuche vorwärts so wie bei Schachengines kannst du auch Rückwärts rechnen so wie bei Schhachdatenbanken.

Beim Rückwärts rechnen muss du aber auch trickreich sein, um große Distanzen zu finden, da die zahlen recht schnell groß werden und zb ein 2dim Array sehr schnell den Speicher sprengt.

Hinterher könnte man dann eine Kombination aus vorwärtssuche und Datenbankwissen veranstalten, auch so wie bei Schachprogrammen.

Als nächstes kommt der Beweis.

Den Beweis habe ich allerings nicht selber gefunden.

Er stammt  von von Tyler Seacrest  aus dem Jahre  2001 aus rec.puzzles
Einen original Link habe dorthin habe ich leider nicht.

Die Beweisidee ist, dass das paar (a,b) in mehreren Schritten vereinfacht wird, indem nach jedem Schritt die Differenz der beiden Werte echt kleiner wird und am Schluß 0 beträgt.

Ein einzelner "Schritt" umfasst dafür allerdings   (auch für kleine (a,b))   sehr viele Transformationen. Mitten in einem Schritt kann die Differenz durchaus einmal gigantisch werden. Am ende eines Schrittes jedoch ist sie stets nachweislich kleiner als zu Beginn des Schrittes

Der Beweis ist konstruktiv, aber er konstruiert  bei weitem nicht die kürzeste Zugfolge.

Gegeben sei (x,x+n) wobei n>= 0 und x ist eine nat.zahl
(Im Fall (x+n,x) verläuft das Verfahren anaog man muss nur T1 und T2 vertauschen)

T1: (x,x+n) → (x+1, 2*(x+n))

n mal anwenden erhalten wir

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

Wenn wir für ein bliebiges b mit  1 <= b < n

T2: (x,x+n) → (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)

Nun wenden wir einmal T1 an und erhalten

(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 T2 an:

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

Der Betrag der Differenz der beiden Zahlen beträgt nun:

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

Wenn man sich den Ausdruck genau ansieht stellt man fest, dass es für n > 1 stets ein b gibt mit 1<=b < n so dass der Ausdruck einen Wert von <n ergibt.

Auf diese Weise können wir durch mehrfache Anwendung des o.g Alogrithmus die Differenz verkleinern bis sie schließlich nur noch 0 1 oder 2 beträgt.

Beträgt die Differenz 1 so führt folgender Durchlauf zu einer Diffenz von 2:

(x , x+1)
(x+1, 2x+2)
(x+2, 4x+4)
(2x+4, 4x+5)
(4x+8, 4x+6)

Beträgt die Differenz 2 so führt ein erneuter Durchlauf mit b = 1 zu zwei gleichen Werten.