Limited persistence (part 3)

By the way:

I talked about how, instead of checking in base 10 every number up to, say, 1040, you can check only numbers with no 0 or 1 digits, that do not have both a 5 and an even digit, with digits in increasing order, and that’s a vastly smaller number to check.

Similarly for other bases, but think about base 3. The only digits you have are 0, 1, and 2, so the only numbers that do not have 0 or 1 digits are all 2s: 23, 223, 2223, 22223, …

There are 343,585,013,821,340,887,357,640,753,177,080,848,468,071,681,334 numbers that have 100 digits in base 3. Out of those only one needs to be checked (if you’ve already checked the 99 other numbers consisting of fewer 2s). Which is one heck of a speedup.

In base 4, any number with more than one digit equal to 2 has maximum persistence 2, so there are only two numbers per decade worth checking (234, 334, 2334, 3334, 23334, 33334, …)

So if we want to check numbers up to 100 digits, there are 100 base 3 numbers and 200 base 4 numbers. For base 5, there are 176,850 numbers. 181,900 in base 6, benefiting from the factors of 6, but 96,560,645 in base 7! Still a lot less than 7100, but things are slowing down pretty hard.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s