Hacker News Reader

Comment by WithinReason | Hacker News Reader

No additional terms up to 2^(10^10). - Michael S. Branicky, Apr 16 2023

How did he do this?

As noted in 3) in the Shepherd's comment, 2^k has no odd digits when 2^k mod 10^n for all integer n have no odd digits as well. So many k would be filtered by checking whether 2^k mod 100 has an odd digit, then another portion of the remainder will get filtered with 2^k mod 1000, 2^k mod 10000 and so on. (EDITED: Thanks to andrewla!) All of them would be periodic, so first few steps can be made into a lookup table to filter almost every k.

> whether 2^k mod 10 is odd

2^k mod 10 is never odd; it's the cycle (2, 4, 8, 6).

Related here is the length of the cycles mod 2^k, https://oeis.org/A005054. Interestingly, the number of all-even-digit elements in those cycles does not appear to be in the oeis, I get 4, 10, 25, 60, 150 as the first five terms.

This does appear to get more efficient as k gets higher; for k=11 I get a cycle length of 39,062,500 with an even subset of 36,105, meaning only .09% of the cycle is all-even.

This is all brute force; there's probably a more elegant way of computing this.

Oh, yeah, I should have said 2^k mod 100 has no odd digits.

10^10 * 36105/39062500 = 9242880, so you're already down to under 10^7 cases to check, which is starting to seem more tractable.

10^7 cases, but almost every case has billions of digits.

Even that doesn't seem so bad though, it's on the order of 10^16 total digits to check in the worst case, and far fewer in practice.

Maybe someone here can run a program overnight and increase the bound by another few orders of magnitude, or disprove the hypothesis?

You only need to check enough digits to find an odd one. An odd digit appears in the low order (< 46 up to a high level) digits for the first quadrillion cases so you only need to compute 2^n mod 10^d where d is big enough to be safe. I used d=60 in my computations to take this to 10^15 candidates (with no additional terms found).

I see my error here -- you can in fact eliminate half even for 2^k mod 10, because both 6 and 8 force a carry; so ending in a 2 or a 6 means that the next higher digit must be odd.

So I suppose if you ever find a cycle where the full cycle has no all-even members, you can prove that there are no more all-even numbers to find.

That's not possible, at minimum 2,4,8,64,2048 would all be the the cycle for `k >= 4`.

I don't follow

Looking back I don't know what I was thinking ignore me.

You're on the right track!

The length of the cycles mod 10^k is simply Euler's phi function of 5^k: 5^(k-1) * 4 (or a factor of phi(5^k); AFAIK it is always exactly phi(5^k), although I don't have a proof of this handy).

The length of the even subset grows roughly as 2.5^k * 1.6. To see why, consider that the length of the cycle grows by a factor of 5 when incrementing k. Each all-even-digit power mod 10^k leads to 5 numbers mod 10^{k+1} which all share the same last k digits - i.e. their last k digits are even. We can model the k+1'th digit as being random, in which case we expect half of all those new numbers to consist entirely of even digits (one new digit, which is either odd or even, and k digits from the previous round that are all even). Thus, when incrementing k, the number of all-even-digit powers in the cycle will grow by approximately a factor of 2.5.

To prove that there is no value of k between 12 and 10^10 such that 2^k has all even digits, you only have to prove that there is an odd digit among the lowest X decimal digits for all 12 ≤ k ≤ 10^10.

The value of X necessary to prove this grows rather slowly compared to k. For example, the smallest power of 2 that doesn't have an odd digit in its last 16 digits is 2^12106. The smallest power of 2 that doesn't have an odd digit in its last 32 digits is 2^3789535319. So it makes sense to try increasingly large values of X until you are able to rule out all values of 2^k for k up to 10^10.

Here's a C++ program you can run to replicate this proof. It takes around 20 minutes to run, and can probably be optimized further, but it shows the principle: https://pastebin.com/DVK2JKdq

This optimization is important because you can then discard most of the number in question, bounding the integer size required for computation.

For instance you could store the number in question in a 128 bit integer, shift left (double), check for odd digits (a series of modulo & divide operations) and then truncate using a modulo and subtract. You can repeat this process as long as you like. If you find an all evens number than you can do a more expensive indepth check.

There likely is a trick but the above is also technically feasible as-is.

You have to do this for 10^10 (ten billion) powers. Each operation needs to check ~4.3billion decimal digits at worst (half that on average). It's highly parallelizable since each power is an easy to compute binary digit and you can do a binary->decimal conversion without relying on previous results which is a log(n) operation, ie one operation per decimal digit.

All up 10^10 powers * ((10^4.3)/2) decimal digits to calculate and check for each of those powers. Around 200 trillion operations all up in human terms. It's still hard enough you'd want a lot of compute. Getting each operation down to a nanosecond still means you're waiting 2.3days for a result. But it's also fair to say it's feasible.

> and you can do a binary->decimal conversion without relying on previous results which is a log(n) operation, ie one operation per decimal digit

Aren't those operations divisions? One division would usually be considered more than one operation.

Hah, I had Michael Branicky as a professor (for his AI course) at the time (Jan - May 2023). Didn't expect to see his name here. He's a brilliant guy.

Just check for the existence of at least one odd digit mod 10^B for some well chosen B.

Here is a C program that does the verification up to 2^(10^10) in 30 seconds: https://gist.github.com/fredrik-johansson/8924e10e5d74e39109...

Edit: made it multithreaded, goes up to 2^(10^12) in nine minutes on 8 cores.

This is plausible with brute-force, perhaps with some basic optimization.

You only need to test 10^10 values, and that is just less than 2^34 cases. Not hard to brute force at all, and trivial to parallelize too.

You forget that the number of decimal digits grows linearly with the exponent. To generate the first n numbers of the form 2^n numbers you need O(n^2) time.

For example, 2^(10^10) is 10^10 bits and about 3 billion decimals digits.

So for n up to 10^10, you need to do about (10^10)/2 = 5×10^19 elemental operations. At one operation per nanosecond that takes 1584 years of CPU time. Not at all easy to brute force!

No, I did not forget.

First of all, 1584 years of CPU time is not that bad.. if your university has a lab of 200 computers, each with 64 cores, that's already 45 days. If there is SETI-like system which lets researchers run their code on idle PCs, the calculation like this might get finished in a few months. Don't underestimate amount of idle compute sitting around in large organizations.

Second, while you can use naive algorithm (generate number, use something like GMP to convert to decimal, find odd digit), there are some pretty trivial optimizations. The OEOIS comments mention most numbers have odd values in last few digits, so in most cases, all you need to do is to calculate (2^n mod 100000000) and check that there is an odd digit there. Only if if there is not (which should be pretty rare) then you pull out that GMP and start do full check.

But wait, there is more! 2^(10^10) is a single binary 1 followed 9999999999 binary zeros, so it seems stupid to waste gigabytes of memory bandwidth storing all that zeros, and you don't need a result either. Implementing your own custom division algorithm specialized for those numbers will let you have tight loop with almost no memory accesses - something that modern CPUs do very fast. I would not be surprised if you can even get GPU to do it for you.

There could be more opportunities for improvement.. For example, I suspect the internal state of that division algorithm might end up being periodic, in which case you'd be able to quickly come up with an answer without having through go to every digit. But even if that's not possible, the optimization will make this problem pretty tractable.

found your other comment: https://news.ycombinator.com/item?id=43426826

very smart! You duplicate the number while only keeping last few digits, to get basically O(n) complexity. Much better than my idea.

To prove a number is on the list, you need to calculate all its digits. But to prove it's not on the list, you only need to calculate its digits up to the first odd one. It looks like the number of digits until the first odd grows very slowly; per the comments there up to n=50000 it has a maxiumum of 18.

yeah that's weird - its kind of a pointless comment without an included algorithm or something

There’s probably a smart way to rule out a lot of cases so you only have to check a relatively small number of candidates. It would be good to know what it is.

I guess the margin was too small to contain it.

Here's a really dumb algorithm:

    for i in range(1, 10**10):
        for k in range(1, 5):
            s = str(pow(2, i, 10**(10**k)))
            if '1' in s or '3' in s or '5' in s or '7' in s or '9' in s:
                break
        else:
            print(2**i)

It's really easily to parallelize, I was able to run it up to 10**8 in about 15min, so you would be able to run it up to 10**10 in a few hours with parallelization.

It's not 10^10 ≈ 2^33 though, it's 2^(10^10) = 2^10000000000, or about 9 999 999 967 orders of magnitude more.

Just by sheer numbers, the comment you're replying to must be one of the provably wrong-est comments in history of hacker news =).

You only need to check the actual powers of two.

Checking about 10^10 of them is just about doable as vhcr correctly showed. (I mean it wasn't optimal, but 'leave this running for 400 hours' is far from impossible)

It is 10^10 cases, checking numbers up to 2^(10^10). The numbers themselves are pretty big (~9 gigabytes each if you want to write full binary representation), but nothing that modern computers can't handle.

Reply on news.ycombinator.com