[andrewla]

> 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.

[andrewla]

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.

[nneonneo]

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.

[lifthrasiir]

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

[Retr0id]

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.

[sebzim4500]

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

[Retr0id]

I don't follow

[sebzim4500]

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

[madcaptenor]

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

[dmurray]

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?

[ted_dunning]

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).