Palindrome – auch Spiegelzahlen genannt

1. Aufgabe

Eine natürliche Zahl, die identisch ist mit ihrer Kehrzahl wie z.B. 131, wird Palindrom genannt. In dieser Aufgabe entwickeln wir eine nicht deterministische Methode zur Berechnung beliebig großer Palindrome

Die in C++ eingebauten elementaren Datentypen (wie int oder long) stellen keine echte Hilfe dar, wenn wir potentiell unendlich große Palindrome berechnen wollen. Zu diesem Zweck entwerfen wir im Folgenden zunächst zwei Klassen Digit und Number, mit deren Hilfe sich sehr große Zahlen darstellen lassen. Im Anschluss daran gehen wir auf die Klasse Palindrom ein, um Palindrome zu berechnen.

Für die Erzeugung von Palindromen gibt es einen sehr einfachen Algorithmus, der leider nicht immer funktioniert: Man addiere eine beliebige Zahl mit ihrer Kehrzahl und untersuche das Ergebnis daraufhin, ob man eine Spiegelzahl erhalten hat. Wenn nicht, setze man das Spiel fort, bis das Ergebnis ein Palindrom ist, zum Beispiel:

165 + 561 ⇒ 726 + 627 ⇒ 1353 + 3531 = 4884

Da dieser Algorithmus nicht immer funktioniert, muss man darauf achten, dass man nicht in eine Endlosschleife gerät! Zur Lösung der Aufgabe sind eine Reihe von Klassen zu entwickeln, deren Arbeitsweise im Folgenden näher beschrieben wird.

1.1. Klasse Digit

Objekte der Klasse Digit beschreiben eine einzelne Ziffer von 0 bis 9. Die Klasse Digit ist äußerst einfach in Ihrer Realisierung, wir spezifizieren sie deshalb nur an Hand einiger Beispiele:

Beispiel:

Digit d;
cout << d << endl;
Digit d1 (5);
cout << d1 << endl;
Digit d2 (15);
cout << d2 << endl;

Ausgabe:

0
5
0

Beispiel:

Digit d1(1);
Digit d2(2);
cout << (d1 == d2) << endl;
cout << (d1 != d2) << endl;

Ausgabe:

0
1

Beispiel:

Digit d(5);
int n = d; // type conversion operation
cout << n << endl;

Ausgabe:

5

1.2. Klasse Number

Objekte der Klasse Number beschreiben eine beliebig große Zahl, deren Ziffern durch Digit-Objekte festgelegt sind. Die in Tabelle 1 beschriebenen Elemente der Klasse Number sind zur Vorbereitung der Berechnung von Palindromen zu implementieren:

Beispiel:

Number n("123456789");
cout << "Number: " << n << endl;
cout << "Digits: " << n.Count() << endl;

Ausgabe:

Number: 123456789
Digits: 9

Die öffentliche Schnittstelle der Klasse Number ist in Tabelle 1 spezifiziert. Die Methoden der Klasse sind mit dem Ziel konzipiert, Palindrome berechnen zu können:

Methode

Schnittstelle und Beschreibung

Standardkonstruktor

Number ();

Erzeugt ein Number-Objekt mit dem Wert 0.

Benutzerdefinierter Konstruktor

Number (char* s);

Erzeugt ein Number-Objekt mit Hilfe der Beschreibung einer Zahl in Form einer Zeichenkette. Der besseren Lesbarkeit halber sind Punkte in der Zeichenkette zulässig, wie etwa "123.456". Mit Ausnahme von Punkten dürfen in der Zeichenkette keine anderen Zeichen enthalten sein.

Count

int Count();

Liefert die Anzahl der Ziffern (Digit-Objekte) in einem Number-Objekt zurück.

IsSymmetric

bool IsSymmetric ();

Liefert true zurück, wenn das aktuelle Number-Objekt eine Spiegelzahl ist, andernfalls false.

Reverse

Number Reverse ();

Erstellt zum aktuellen Number-Objekt das inverse Number-Objekt, auch als Kehrzahl bezeichnet. Das aktuelle Number-Objekt bleibt unverändert.

Add

Number Add (const Number& num);

Addiert zwei beliebig lange Number-Objekte. Das Ergebnis wird als Rückgabewert von Add zurückgegeben.

PrependDigit

void PrependDigit (const Digit& digit);

Stellt die Ziffer digit der aktuellen natürlichen Zahl voran:

Beispiel:

Number n("1");
cout << n << endl;
Digit d(2);
n.PrependDigit (d);
cout << n << endl;

Ausgabe:

1
21

Hinweis: Die PrependDigit-Methode ist als Unterstützung für die Add-Methode konzipiert!

Tabelle 1. Öffentliche Schnittstelle der Klasse Number.


Bei der Additionsmethode Add legen Sie Ihre Kenntnisse aus der Schulmathematik zu Grunde: Die zu addierenden Zahlen sind „gedanklich“ betrachtet untereinander zu schreiben. Die Zahlen werden nun von hinten beginnend aufaddiert, wobei ein Übertrag entstehen kann. Dieser ist dann im nächsten Schritt zu berücksichtigen, wie in Abbildung 1 am Beispiel der beiden Zahlen 1282 und 976 dargestellt wird:

Schriftliche Addition aus der Schulmathematik.

Abbildung 1. Schriftliche Addition aus der Schulmathematik.


Es folgen einige Beispiele, um die Arbeitsweise der Klasse Number näher illustrieren:

Beispiel:

Number n ("1234321");
cout << n.IsSymmetric() << endl;

Ausgabe:

1

Beispiel:

Number n ("12345");
Number m = n.Reverse();
cout << n << endl;
cout << m << endl;

Ausgabe:

12345
54321

Beispiel:

Number n1 ("1282");
cout << n1 << endl;
Number n2 ("976");
cout << '+' << n2 << endl;
Number n3 = n1.Add (n2);
cout << n3 << endl;

Ausgabe:

1282
+976
2258

Anmerkung

Überlegen Sie sich, in welcher Reihenfolge Sie die Ziffern einer natürlichen Zahl in einem Number-Objekt abspeichern. Bei geeigneter Ablage kann sich die Implementierung der Add-Methode vereinfachen!


1.3. Klasse Palindrom

Für die Erzeugung von Palindromen gibt es einen Algorithmus, der leider nicht deterministisch ist: Addiert man eine beliebige Zahl wiederholt mit ihrer Kehrzahl (inversen Zahl), kann man ein Palindrom erhalten.

Beispiel:

Zahl: 53978
inverse Zahl: + 87935
addiert: 141913
inverse Zahl: + 319141
addiert: 461054
inverse Zahl: + 450164
addiert: 911218
inverse Zahl: + 812119
addiert: 1723337
inverse Zahl: + 7333271
addiert: 9056608
inverse Zahl: + 8066509
addiert: 17123117
inverse Zahl: + 71132171
addiert: 88255288 7 Schritte

Die einfache Idee des Algorithmus basiert also auf der wiederholten Addition einer beliebigen Zahl mit ihrer inversen Zahl. Da in einigen (wenigen) Situationen der Algorithmus in eine Endlosschleife geraten kann, müssen Sie die Anzahl der wiederholten Additionen begrenzen. Weitere Details entnehmen Sie Tabelle 2:

Methode

Schnittstelle und Beschreibung

SetStart

void SetStart (const Number& num);

Mit SetStart wird die Ausgangszahl zur Berechnung eines Palindroms eingestellt.

GetStart

Number GetStart ();

Liefert die Ausgangszahl zurück, die bei der Berechnung eines Palindroms verwendet wird.

SetSteps

void SetSteps (int steps);

Dient zum Einstellen der maximalen Anzahl Iterationsschritte steps, die für den Versuch, ein Palindrom zu berechnen, verwendet wird.

GetSteps

int GetSteps ();

Liefert die maximale Anzahl der Iterationsschritte zurück, die bei der Berechnung eines Palindroms herangezogen werden.

CalcPalindrom

PalindromResult CalcPalindrom ();

Die Methode versucht, zu einem vorgegebenen Ausgangswert ein Palindrom zu berechnen. Wird ein Palindrom ermittelt, bricht der Algorithmus ab. Andernfalls erfolgt die Terminierung nach einer festgelegten Anzahl Iterationsschritte.

Tabelle 2. Öffentliche Schnittstelle der Klasse Palindrom.


Die Methode CalcPalindrom liefert ein Objekt vom Typ PalindromResult zurück. In diesem Objekt sind drei Werte abgelegt: Der Ausgangswert, das berechnete Palindrom und die Anzahl der Iterationsschritte, siehe auch Tabelle 3. Konnte kein Palindrom berechnet werden, wird dies durch den Wert -1 für die Anzahl der Iterationsschritte zum Ausdruck gebracht.

Methode

Element

GetResult

Number m_result;

Liefert das berechnete Palindrom zurück.

GetStart

Number m_start;

Liefert die Ausgangszahl zurück, die bei der Berechnung des Palindroms verwendet wird.

GetSteps

int m_steps;

Liefert die Anzahl der Iterationsschritte zurück, die bei der Berechnung des Palindroms herangezogen wurden.

Tabelle 3. Elemente der Klasse PalindromResult.


Testen Sie Ihre Implementierung an Hand der folgenden drei Codefragmente. Achten Sie darauf, neben dem Ausgangswert auch die passende Anzahl der Iterationsschritte zu verwenden:

Beispiel:

Palindrom p;
p.SetStart (Number ("89"));
p.SetSteps (90);
PalindromResult r = p.CalcPalindrom ();
cout << r << endl;

Ausgabe:

Palindrom: 8813200023188
[Start: 89, 25 steps]

Beispiel:

Palindrom p;
p.SetStart (Number ("53978"));
p.SetSteps (10);
PalindromResult r = p.CalcPalindrom ();
cout << r << endl;

Ausgabe:

Palindrom: 88255288
[Start: 53978, 8 steps]

1.4. Viertes Eulersches Problem

Ein nach dem Mathematiker Leonhard Euler benanntes Problem lautet: „Finde das größte Palindrom, das ein Produkt aus zwei dreistelligen Zahlen ist!“. Zum besseren Verständnis: Das größte 4-stellige Palindrom als Produkt zweier 2-stelliger Zahlen ist 9009 = 91 * 99.

Ein Hinweis: Für die Multiplikation dreistelliger Zahlen dürfen Sie Variablen des Typs int verwenden. Sie müssen die Klasse Number also nicht um eine Multiplikationsmethode ergänzen.

Schreiben Sie eine C++-Funktion, die mit Hilfe der Klasse Number das vierte Eulersche Problem löst.

2. Lösung

Quellcode: Siehe auch https://github.com/peterloos/Cpp_BigPalindrom.

Wir kommen direkt auf Lösungsvorschläge für die Klassen Digit, Number, PalindromResult und Palindrom zu sprechen:

01: class Digit
02: {
03: private:
04:     int m_digit;
05: 
06: public:
07:     // c'tors
08:     Digit ();
09:     Digit (int digit);
10: 
11:     // getter / setter
12:     void SetDigit (int digit);
13:     int GetDigit() const;
14: 
15:     // operators
16:     friend bool operator== (const Digit&, const Digit&);
17:     friend bool operator!= (const Digit&, const Digit&);
18: 
19:     // conversion operator
20:     operator int();
21:     
22:     // output
23:     friend ostream& operator<< (ostream&, const Digit&);
24: };

Beispiel 1. Klasse Digit: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "Digit.h"
05: 
06: // c'tors
07: Digit::Digit ()
08: {
09:     m_digit = 0;
10: }
11: 
12: Digit::Digit (int digit)
13: {
14:     m_digit = (digit >= 0 && digit <= 9) ? digit : 0;
15: }
16: 
17: // getter / setter
18: void Digit::SetDigit (int digit)
19: {
20:     m_digit = (digit >= 0 && digit <= 9) ? digit : 0;
21: }
22: 
23: int Digit::GetDigit() const
24: {
25:     return m_digit;
26: }
27: 
28: // operators
29: bool operator== (const Digit& d1, const Digit& d2)
30: {
31:     return d1.m_digit == d2.m_digit;
32: }
33: 
34: bool operator!= (const Digit& d1, const Digit& d2)
35: {
36:     return d1.m_digit != d2.m_digit;
37: }
38: 
39: // conversion operator
40: Digit::operator int()
41: {
42: 	return m_digit;
43: }
44: 
45: // output
46: ostream& operator<< (ostream& os, const Digit& digit)
47: {
48:     os << digit.m_digit;
49:     return os;
50: }

Beispiel 2. Klasse Digit: Implementierung.


01: class Number
02: {
03: private:
04:     Digit* m_digits;         // array of 'Digit' objects
05:     int    m_count;          // number of 'Digit' objects
06: 
07: public:
08:     // c'tors / d'tor
09:     Number ();               // default c'tor
10:     Number (char*);          // conversion c'tor
11:     Number (const Number&);  // copy c'tor
12:     ~Number ();              // d'tor
13: 
14: private:
15:     Number (int count);      // private user-defined c'tor
16: 
17: public:
18:     // getter
19:     int Count() const;
20: 
21:     // public interface
22:     bool IsSymmetric () const;
23:     Number Reverse () const;
24:     void PrependDigit (const Digit&);
25:     Number Add (const Number&) const;
26: 
27:     // assignment operator
28:     Number& operator= (const Number&);
29: 
30:     // index operator (read-only)
31:     int operator[] (int i) const;
32: 
33:     // operators
34:     friend bool operator== (const Number&, const Number&);
35:     friend bool operator!= (const Number&, const Number&);
36:     friend Number operator+ (const Number&, const Number&);
37: 
38:     // output
39:     friend ostream& operator<< (ostream&, const Number&);
40: };

Beispiel 3. Klasse Number: Schnittstelle.


001: #include <iostream>
002: using namespace std;
003: 
004: #include "Digit.h"
005: #include "Number.h"
006: 
007: // c'tors / d'tor
008: Number::Number ()
009: {
010:     m_digits = new Digit [1];
011:     m_count = 1;
012: }
013: 
014: // user-defined c'tor
015: Number::Number(char* s)
016: {
017:     // count number of digits 
018:     m_count = 0;
019:     int i = 0;
020:     while (s[i] != '\0')
021:     {
022:         if (s[i] >= '0' && s[i] <= '9')
023:             m_count ++;
024: 
025:         i ++;
026:     }
027: 
028:     // allocate array of digit objects
029:     m_digits = new Digit[m_count];
030: 
031:     // copy digits into array in reverse order
032:     for (int j = i -1, k = 0; j >= 0; j --)
033:     {
034:         if (s[j] >= '0' && s[j] <= '9')
035:         {
036:             m_digits[k].SetDigit (s[j] - '0');
037:             k++;
038:         }
039:     }
040: }
041: 
042: Number::Number (int count)
043: {
044:     // allocate array of digit objects
045:     m_count = count;
046:     m_digits = new Digit [m_count];
047: }
048: 
049: Number::Number (const Number& number)
050: {
051:     // allocate array of digit objects
052:     m_digits = new Digit [number.m_count];
053: 
054:     // copy digit objects
055:     for (int i = 0; i < number.m_count; i ++)
056:         m_digits[i] = number.m_digits[i];
057:     m_count = number.m_count;
058: }
059: 
060: Number::~Number ()
061: {
062:     delete[] m_digits;
063: }
064: 
065: // getter
066: int Number::Count() const
067: {
068:     return m_count;
069: }
070: 
071: // public interface
072: bool Number::IsSymmetric () const
073: {
074:     for (int i = 0; i < m_count / 2; i ++)
075:         if (m_digits[i] != m_digits[m_count - 1 - i])
076:             return false;
077: 
078:     return true;
079: }
080: 
081: Number Number::Reverse () const
082: {
083:     Number tmp (*this);
084:     for (int i = 0; i < m_count / 2; i ++)
085:     {
086:         Digit d = tmp.m_digits[i];
087:         tmp.m_digits[i] = tmp.m_digits[m_count - 1 - i];
088:         tmp.m_digits[m_count - 1 - i] = d;
089:     }
090:     return tmp;
091: }
092: 
093: void Number::PrependDigit (const Digit& d)
094: {
095:     // allocate new array of digit objects
096:     Digit* tmp = new Digit [m_count + 1];
097: 
098:     // copy old digits
099:     for (int i = 0; i < m_count; i ++)
100:         tmp[i] = m_digits[i];
101: 
102:     // add new digit
103:     tmp[m_count] = d;
104: 
105:     // switch to new array
106:     delete[] m_digits;
107:     m_digits = tmp;
108:     m_count ++;
109: }
110: 
111: Number Number::Add (const Number& number) const
112: {
113:     int count = (m_count < number.m_count) ? number.m_count : m_count;
114:     Number result (count);
115: 
116:     int carry = 0;
117:     for (int pos = 0; pos < count; pos ++)
118:     {
119:         int sum1 = (pos < m_count) ? m_digits[pos].GetDigit() : 0;
120:         int sum2 = (pos < number.m_count) ? number.m_digits[pos].GetDigit() : 0;
121:         int sum = sum1 + sum2 + carry;
122: 
123:         if (sum >= 10)
124:         {
125:             sum -= 10;
126:             carry = 1;
127:         }
128:         else
129:         {
130:             carry = 0;
131:         }
132: 
133:         Digit d (sum);
134:         result.m_digits[pos] = d;
135:     }
136: 
137:     if (carry == 1)
138:     {
139:         Digit d (1);
140:         result.PrependDigit (d);
141:     } 
142: 
143:     return result;
144: }
145: 
146: Number operator+ (const Number& number1, const Number& number2)
147: {
148:     return number1.Add (number2);
149: }
150: 
151: // assignment operator
152: Number& Number::operator= (const Number& number)
153: {
154:     if (this != &number)
155:     {
156:         // release left side
157:         delete[] m_digits;
158: 
159:         // allocate array of digit objects
160:         m_digits = new Digit [number.m_count];
161:         for (int i = 0; i < number.m_count; i ++)
162:             m_digits[i] = number.m_digits[i];
163:         m_count = number.m_count;
164:     }
165: 
166:     return *this;
167: }
168: 
169: // index operator (read-only)
170: int Number::operator[] (int i) const
171: {
172:     return (i >= 0 && i < m_count) ? m_digits[i].GetDigit() : 0;
173: }
174: 
175: // comparison operators
176: bool operator== (const Number& number1, const Number& number2)
177: {
178:     if (number1.m_count != number2.m_count)
179:         return false;
180: 
181:     for (int i = 0; i < number1.m_count; i ++)
182:         if (number1.m_digits[i] != number2.m_digits[i])
183:             return false;
184: 
185:     return true;
186: }
187: 
188: bool operator!= (const Number& number1, const Number& number2)
189: {
190:     return ! (number1 == number2);
191: }
192: 
193: // output
194: ostream& operator<< (ostream& os, const Number& number)
195: {
196:     for (int i = number.m_count - 1; i >= 0; i --)
197:         os << number.m_digits[i];
198: 
199:     return os;
200: }

Beispiel 4. Klasse Number: Implementierung.


01: #include <iostream>
02: using namespace std;
03: 
04: class PalindromResult
05: {
06: private:
07:     Number m_result;
08:     Number m_start;
09:     int m_steps;
10: 
11: public:
12:     // c'tors
13:     PalindromResult ();
14:     PalindromResult (const Number& result, const Number& start, int);
15: 
16:     // getter
17:     Number GetResult () const { return m_result; }
18:     Number GetStart () const { return m_start; }
19:     int GetSteps () const { return m_steps; }
20: 
21:     // output
22:     friend ostream& operator<< (ostream&, const PalindromResult&);
23: };

Beispiel 5. Klasse PalindromResult: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "Digit.h"
05: #include "Number.h"
06: #include "PalindromResult.h"
07: 
08: PalindromResult::PalindromResult () : m_result(), m_start()
09: {
10:     m_steps = -1;
11: }
12: 
13: PalindromResult::PalindromResult (const Number& result, const Number& start, int steps)
14: {
15:     m_result = result;
16:     m_start = start;
17:     m_steps = steps;
18: }
19: 
20: ostream& operator<< (ostream& os, const PalindromResult& result)
21: {
22:     if (result.m_steps >= 0)
23:         os << "Palindrom: " << result.m_result << endl
24:            << "[Start: " << result.m_start
25:            << ", " << result.m_steps << " steps]";
26:     else
27:         os << "No Palindrom found!" << endl;
28: 
29:     return os;
30: }

Beispiel 6. Klasse PalindromResult: Implementierung.


01: class Palindrom
02: {
03: private:
04:     Number m_start;
05:     int m_steps;
06: 
07: public:
08:     // c'tors / d'tor
09:     Palindrom ();
10:     Palindrom (int);
11: 
12:     // getter / setter
13:     void SetStart (const Number&);
14:     Number GetStart () const;
15:     void SetSteps (int);
16:     int GetSteps () const;
17: 
18:     // public interface
19:     PalindromResult CalcPalindrom ();
20:     PalindromResult CalcPalindrom (const Number&);
21: 
22:     // verbose interface
23:     void CalcPalindromVerbose (ostream&, const Number&, int);
24: };

Beispiel 7. Klasse Palindrom: Schnittstelle.


01: #include <iostream>
02: using namespace std;
03: 
04: #include "Digit.h"
05: #include "Number.h"
06: #include "PalindromResult.h"
07: #include "Palindrom.h"
08: 
09: // c'tors
10: Palindrom::Palindrom () : m_steps(0), m_start("1")
11: {
12: }
13: 
14: Palindrom::Palindrom (int steps) : m_steps(steps), m_start("1")
15: {
16: }
17: 
18: // getter / setter
19: void Palindrom::SetStart (const Number& start)
20: {
21:     m_start = start;
22: }
23: 
24: Number Palindrom::GetStart () const
25: {
26:     return m_start;
27: }
28: 
29: void Palindrom::SetSteps (int steps)
30: {
31:     m_steps = steps;
32: }
33: 
34: int Palindrom::GetSteps () const
35: {
36:     return m_steps;
37: }
38: 
39: // public interface
40: PalindromResult Palindrom::CalcPalindrom ()
41: {
42:     return CalcPalindrom(m_start);
43: }
44: 
45: PalindromResult Palindrom::CalcPalindrom (const Number& number)
46: {
47:     m_start = number;
48:     Number n = m_start;
49:     for (int i = 0; i < m_steps; i ++)
50:     {
51:         if (n.IsSymmetric ())
52:             return PalindromResult (n, m_start, i+1);
53: 
54:         Number m = n.Reverse ();
55:         n = n.Add (m);
56:     }
57: 
58:     return PalindromResult();
59: }
60: 
61: void Palindrom::CalcPalindromVerbose (ostream& os, const Number& number, int steps)
62: {
63:     m_start = number;
64:     Number n = m_start;
65:     PalindromResult result;
66:     os << "Start: " << n << endl;
67:     for (int i = 0; i < steps; i ++)
68:     {
69:         if (n.IsSymmetric ())
70:         {
71:             result = PalindromResult (n, m_start, i);
72:             break;
73:         }
74: 
75:         Number m = n.Reverse ();
76:         n = n.Add (m);
77:         os << "Next:  " << n << endl;
78:     }
79: 
80:     os << endl << result << endl;
81: }

Beispiel 8. Klasse Palindrom: Implementierung.


Zum besseren Testen der Implementierung finden Sie in der Klasse Palindrom noch eine zusätzliche Methode CalcPalindromVerbose vor. Sie schreibt bei der versuchsweisen Berechnung eines Palindroms alle Zwischenberechnungen in ein ostream-Objekt. Am nachfolgenden Beispiel mit dem Startwert 107000020928910 können Sie dies eindrucksvoll beobachten:

Palindrom p;
Number start ("107.000.020.928.910");
p.CalcPalindromVerbose (cout, start, 200);

Ausgabe:

Start: 107000020928910
Next:  126829040929611
Next:  243758081858232
Next:  476616262715574
Next:  952133525332248
Next:  1794367050663507
Next:  8848027558298478
Next:  17596956115506966
Next:  84557507281476537
Next:  158124925552052085
Next:  738375181081473936
Next:  1377749361263047773
Next:  5155152982902525504
Next:  9210405075795041019
Next:  18311811051500081148
Next:  102429811566511892529
Next:  1027727927231630816730
Next:  1403908288558928093931
Next:  2797816587117756186972
Next:  5594633164235612374944
Next:  10089365329560225739899
Next:  109983117536152582137900
Next:  119714402787788293527801
Next:  228439795675575497945712
Next:  445989590251152095880534
Next:  881078180502304191870078
Next:  1751156371905509273740266
Next:  8371630100960601010251837
Next:  15753150202021291020613575
Next:  73284752221233311225749326
Next:  135679504432566523451497563
Next:  501473658758231757857474094
Next:  991948417515364615713848199
Next:  1983796735031828131428697398
Next:  10921764976350109436805671289
Next:  109139415839840214804752384190
Next:  200622673248252263743267316091
Next:  391236435595614516585643542093
Next:  781481782181229933181178174286
Next:  1463953653362569855362465358473
Next:  5212489295998159507996028952114
Next:  9325087502995219026991958794239
Next:  18650066094991428152984016599478
Next:  106149627143916610572933082605159
Next:  1057655907483191627192274809546760
Next:  1734114992206108889106121905114261
Next:  3358230083422128777122144899228632
Next:  5726460067834346555334388699557165
Next:  11344020036668682111768776300203440
Next:  15774220404455393240455439302247751
Next:  31548440797910797479810879704495502
Next:  52107881595712694959512859408980015
Next:  103116862091534290909134618927850140
Next:  144175591907966200001569809196461441
Next:  288340283816931300004239518392032882
Next:  576570577632863700007379136774076764
Next:  1044241055264837400014747373549152439
Next:  10386760509002311500062131999050576840
Next:  15254265608915437500573452089557345141
Next:  29408641206940875001146904070213590392
Next:  58718172413981839111204709030428270884
Next:  107525454817072579322398527961855452669
Next:  1073780012986798472546373798680309978370
Next:  1812579043855772208999122775572410852071
Next:  3515159186611544428997145551155820604252
Next:  6039219472123099846995390002322640119405
Next:  11088329934355100782991879905535389248711
Next:  22872628287906098602920580060879381636722
Next:  45636246685712107105841269121857664264544
Next:  90182493361524303320691439243616328528198
Next:  179365075723158596740293769586132667956307
Next:  883024841954844564132341465437460238520278
Next:  1755050674019579128275572930885919386940666
Next:  8415547513215459521031301150645024147446237
Next:  15741994927420920032062602410190147304901385
Next:  74052935301530021452688625413092620254816136
Next:  137214780504159052905377250825096130608741183
Next:  518362586535849580958150760076047535696153914
Next:  937714283071590251025202619161996071381417729
Next:  1865428466242289412941405139314091241763835468
Next:  10510812137664193552256446631463913668412081149
Next:  104628833624296129965920911857003060341533882650
Next:  160917168767356430724039941426924752767872709051
Next:  311824447534613860348189871853959406535734428112
Next:  523648885070218819706368853697027722971478856225
Next:  1046307759249446540502727717304946535042067702550
Next:  1598385361654803034539904989355402984471644738951
Next:  3196759823399695080079799088709706069033280577902
Next:  5294510646709301159158609068410512038966570154815
Next:  10479021403407603309307218136930023078043030309740
Next:  15269324437494635313270399407320353748473442407141
Next:  29439748874979370615640898714551707397946884803392
Next:  58770597739958741331182688519203314795894769596884
Next:  107640194489818482661474277147316629581888549104669
Next:  1074042140378004409275216049621482914400873040151370
Next:  1805552544158048602116485455747211958409603452556071
Next:  3512105087227097193243961001593324026818117905111152
Next:  6023220184345283397477912003286747944725345710123305
Next:  11056430359780557894954735005484495878550780520346511
Next:  22620732868486145754403185059230445754059575823811522
Next:  45132565726081191508806480117360891508228062647514144
Next:  89274140352163472028612851225821772027346125404037298
Next:  178547180804327844056325703441643454054782250708184596
Next:  874028987856615294510671847749167104503505658789930467
Next:  1638068975713120599912433795497343119996022317579750945
Next:  7128648732845327599025871741470685319946235493378359306
Next:  13168187466790654098161732482942470529903470975756827523
Next:  45741053224698085090669157411366186718949080742235013654
Next:  91372106449406180072437323722841383328007170384470028408
Next:  171854113897713350154775638545573756755015330878930155727
Next:  899405153775746860712433014091410334206068648677241613898
Next:  1797721296552593721314866028281820668423137296254593118896
Next:  8785835251079521034563526310110027352554411248811514396867
Next:  16472769402267942179116063510220163606208712508513039782745
Next:  71201562433848463959376699612421699667405837484733536510206
Next:  131403125967596937809853399224843399334801773969566963020423
Next:  455423495633566314918287392573266392693710513665336484324554
Next:  910846980267132629935683686235641686476529927330673078649108
Next:  1712793850643166359861358372382174372863069853562435168297127
Next:  8930722465985819949465041107095007111394759390175895752269298
Next:  17860345041971530889039972224100914122800408889361791394539696
Next:  87553894361687929769440794366001056350793507692879705448846567
Next:  164118778812485759439980499731011122700498004485858321798682145
Next:  705405675936344343840874506952121260694587939443442540676493606
Next:  1311800351981588688780660003014242520300065987786886180252998113
Next:  4430792872798475566676260033266666623300726866655738071783079244
Next:  8860496744506851133362530066533333246601353633311487044566049588
Next:  17719903398914692266726061132956666603201706266623073099042990276
Next:  84929827497951724932986771363623332526317769032852715088373982047
Next:  158958764886003450756083542726146665162635537956795431067846874995
Next:  758437413646138048415819078987713306789880918613849731756314734846
Next:  1406874827303275996732638167975316624579751837128690563402629469703
Next:  4486524089346926964950019747729582760377370199505686286439914255744
Next:  8962048288693753830009930485460255619654849300100382582879718512588
Next:  17814206468476606660019969970029421140300689699100766156848546915286
Next:  86066171053341773360219668570333533632308686690107426824335007157157
Next:  161241341106684635830329337250657167165616273381313764538670024323225
Next:  683564761183520103143512709867218928921669007304352301025271167465386
Next:  1367129522356040206396916410833348758734437914519693602050652334930772
Next:  4137523854916542270366070608177727337167818060716629622457184594148403
Next:  7185938809734084539632241216365344674445536121423260344913379177405717
Next:  14360986529467278970255482432720789438881172242845629699717758265801534
Next:  57871842815239078662910306659839672937583895671300837686994250834707875
Next:  115742586620489047336710624319678246865277791331602764374087502659525750
Next:  173268542826269520803916757517450815508154704757620398115071529344773261
Next:  335645986751440032696943514924902621026209420515239706141034157590635632
Next:  572182082502870174304876029949805241152418849930589402371078315280182165
Next:  1133463165016740347509861069898619492294927799851267805842156520560463440
Next:  1577103815273252832597482659875914415244096789452956863272632626174106751
Next:  3153118531535615556284075209752818840388292579015804815655156351357124502
Next:  5207336063072131121468160319505747670876475158041509642210321702715238015
Next:  10315661235143361243937211728021494451643950217172128283421634406321575040
Next:  14373173595586973682219338899227429067093362299883402217637968559538226341
Next:  28735457191173947353439777798453768143185834599766793446275937119075363682
Next:  57371814282347904617879544597997626277372570089544586881650874238250817464
Next:  103843619565595710236748089196005153654635250069089184753291848566492634839
Next:  1042279914231443902594230070156057690110986750761070032385309444132408983140
Next:  1456177956545892938426530771826634580221954257271770357337402885456608705541
Next:  2911256023091774985764061543554159171442808623553540713585795870913206422082
Next:  5713502046282560961617231997107427253884528138106992318261690642816412943274
Next:  10436994192465021923245364993125745508768055385124983645423381295642814996449
Next:  104906936017124240255700003935284100595548610137264929999656293352071964959850
Next:  163866405187377632912699933398015117441143611619804230007208335773782604569251
Next:  316831811474755166715399965806931233782288323130697570003427572547564109237612
Next:  533564712940500442439700041602962557664575655270306139996945234105038227376225
Next:  1056238435771001874989399973206035114240042410539512280004879478110087444841560
Next:  1707722883571120624773400795365385256640466525845536079944774259111862793168061
Next:  3316336856252240149547900501720870513280933051681172049988548519323616675445132
Next:  5631782622415479308006799904432732016671756202461443100086007929746143261781265
Next:  11253654245831958605013599917874374043243522304833787200062015969491285524652630
Next:  14879296804051455556039600196608214365777756352181659199593066655405139770287841
Next:  29757504597201911222079199392226339731555512693462328300286132210820180639585682
Next:  58416098205304712445247399774552779353111026486824557699483154422730460180161474
Next:  105832206311708434890385899450095647815122161884550105498857408844470810469222959
Next:  1065055170329782883695144793951151135976343680631140160497440507279277924071461460
Next:  1706696874627512610745592734561562496839780475942651754471856471162157154786967061
Next:  3314393749145025222492174479133124992580659862885303408844811941324314419573933132
Next:  5627787508289159453983358967176160875270220715879516728589524883549519839047867265
Next:  11255474917678318907867618825452320660440441441660133446288058777099039667105744530
Next:  14800225094371417985652707089885427274854845848262458899169735648080427339053199741
Next:  29599360187743826070306503289770853559709691695534917797240461307051844688105400582
Next:  58099810376388641140622907569542797119329382491070725595471021614114679466211800174
Next:  105200621642886282282234925029095504138757774882250450192041944218229367833513699259
Next:  1058196936981650205094684065320149556427235532713656041112571376500512056079639701760
Next:  1729276306688152355151415817431556119599590859960215451348176241405532617976036620261
Next:  3349542613485314710192842535863101240299171819919332002695361382921065136842073349532
Next:  5708976315971630311485674171825103579498353539839753016380713865831239272685235808965
Next:  11407061641834359632871357342661207158887707078789506031662428631672369634480372607040
Next:  15477688950278055960485039769274267757674777857674676248286803949496064978294988677451
Next:  30955377899566002029979970637558535405350655605350452495583597007903020065500977354902
Next:  51900755800122004060950050176117960810701311210700906081157205005895040132100854710805
Next:  102702501600245108120800100451236021711402522521402713052324310011801080154201710411720
Next:  129816518702696188228910113874486338915527747725519833684478311019822881696207815618921

Palindrom: 129816518702696188228910113874486338915527747725519833684478311019822881696207815618921
[Start: 107000020928910, 192 steps]