I introduced the sequence 2, 3, 4, 82000, … in an earlier post. To recap: the n-th term is the smallest number > 1 whose representation in all bases up to n uses only the digits 0 and 1.
Nobody has found the next term. I wrote a C++ program to search for it. The code is on GitHub and uses the GNU Multiple Precision Arithmetic Library, since the candidates quickly grow to millions of digits.
The algorithm
The core idea: take a guess and check whether it satisfies all bases from the target base down to 3. (Base-2 is always satisfied by definition.)
As soon as a base fails — i.e., the number’s representation in that base contains a digit other than 0 or 1 — we don’t check further bases. Instead, we jump directly to the next number that would satisfy that base. This skip is roughly proportional to the size of the number, which keeps the search tractable even for huge candidates.
Example: verifying 82000
Starting from 10 (the first candidate past 4), the algorithm visits only 16 numbers before finding 82000:
| Decimal | Base-5 | Base-4 | Base-3 |
|---|---|---|---|
| 10 | 20 | 22 | 101 |
| 25 | 100 | 121 | 221 |
| 64 | 224 | 1000 | 2101 |
| 125 | 1000 | 1331 | 11122 |
| 256 | 2011 | 10000 | 100111 |
| 625 | 10000 | 21301 | 212011 |
| 1024 | 13044 | 100000 | 1101221 |
| 3125 | 100000 | 300311 | 11021202 |
| 4096 | 112341 | 1000000 | 12121201 |
| 15625 | 1000000 | 3310021 | 210102201 |
| 16384 | 1011014 | 10000000 | 211110211 |
| 16400 | 1011100 | 10000100 | 211111102 |
| 19683 | 1112213 | 10303203 | 1000000000 |
| 78125 | 10000000 | 103010231 | 10222011112 |
| 81920 | 10110140 | 110000000 | 11011101002 |
| 82000 | 10111000 | 110001100 | 11011111001 |
Bold entries are the failing base that causes the jump. The algorithm checks the largest base first, aborting as soon as one fails.
Current status
As of September 7, 2015, the code has been running for a week on my desktop with 20 threads and has reached candidates with almost 14 million digits — compared to 82000’s 5 digits. Still no hit.
The next post covers the performance analysis and threading details.