Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Powers of 2 with all even digits

oeis.org

Post reply on HN
Print view View original

111–120 of 123 posts

Re: Powers of 2 with all even digits

#111

Post by eru »

nneonneo wrote: post #104
shrx wrote: post #103

Earlier quoted context omitted.

Is your algorithm published somewhere?

I literally just invented it, so it's not published yet, although I'll probably throw it up on GitHub at some point. It matches all published results up to an exponent of 3 billion or so, so I'm quite confident it's correct. The short explanation is that 2^x mod 10^k will repeat with a cycle length of 5^(k-1)*4. This is easily obtained from Euler's phi formula on 2^x mod 5^k, plus the fact that 2^x === 0 mod 2^k for…

> My rather hasty prototype is actually implemented in Python - not a language you want to do tons of arithmetic in [...]

It might actually not be too bad? The actual big integer arithmetic is written in some fast language, and Python is just the glue holding everything together.

Re: Powers of 2 with all even digits

#113

Post by LegionMammal978 »

Mae_soph wrote: post #106

I might have a proof that this list is complete (I am very tired though and should be sleeping instead of doing this, so my apologies if I'm wrong): Because we can only get one extra by carrying, each digit of 2^(k - 1) is at most 4 (otherwise the next digit in 2^k will be odd). Assume this list is complete up to 10^n. We find the biggest l such that 2^(5^(l - 1)*4) 2^k > 10^n such that 2^k has all even digits. By cy…

> By cyclicity of powers of 2 mod 10^l (that's why we chose this l), this means that 2^(k - 1) = a*10^l + b, where a is some integer and b is 1,2,4,32 or 1024 (because those are the only options with digits less than 5 mod 10^l).

I'm pretty sure this is the part where the argument breaks down. Just because 2^(k-1) mod 10^l only has small digits doesn't mean that it corresponds to a lesser power of 2 with small digits. E.g., 2^18 ends in 2144, which is not one of 1, 2, 4, 32, or 1024. (And for that matter, 1024 ends in 24.)

The hard part is showing that eventually you must hit a digit greater than 4 if you look at a long-enough suffix.

Re: Powers of 2 with all even digits

#114

Post by Mae_soph »

LegionMammal978 wrote: post #113
Mae_soph wrote: post #106

I might have a proof that this list is complete (I am very tired though and should be sleeping instead of doing this, so my apologies if I'm wrong): Because we can only get one extra by carrying, each digit of 2^(k - 1) is at most 4 (otherwise the next digit in 2^k will be odd). Assume this list is complete up to 10^n. We find the biggest l such that 2^(5^(l - 1)*4) 2^k > 10^n such that 2^k has all even digits. By cy…

> By cyclicity of powers of 2 mod 10^l (that's why we chose this l), this means that 2^(k - 1) = a*10^l + b, where a is some integer and b is 1,2,4,32 or 1024 (because those are the only options with digits less than 5 mod 10^l). I'm pretty sure this is the part where the argument breaks down. Just because 2^(k-1) mod 10^l only has small digits doesn't mean that it corresponds to a lesser power of 2 with small digits…

Yeah, you're right, thank you. This is why you shouldn't do math past midnight, I guess :).

Re: Powers of 2 with all even digits

#115

Post by vanderZwan »

I'd love to see a numberphile episode on this, for two reasons:

1: it's been too long since we've had a Neil Sloane episode, which are always a highlight

2: it sounds like the kind of thing where just a little bit more attention from maths enthusiasts will result in a proof of the sequence being finite (or not) very quickly

Re: Powers of 2 with all even digits

#116

Post by saagarjha »

eru wrote: post #111
nneonneo wrote: post #104

Earlier quoted context omitted.

I literally just invented it, so it's not published yet, although I'll probably throw it up on GitHub at some point. It matches all published results up to an exponent of 3 billion or so, so I'm quite confident it's correct. The short explanation is that 2^x mod 10^k will repeat with a cycle length of 5^(k-1)*4. This is easily obtained from Euler's phi formula on 2^x mod 5^k, plus the fact that 2^x === 0 mod 2^k for…

> My rather hasty prototype is actually implemented in Python - not a language you want to do tons of arithmetic in [...] It might actually not be too bad? The actual big integer arithmetic is written in some fast language, and Python is just the glue holding everything together.

I don't think Python has a particularly optimized bignum implementation.

Re: Powers of 2 with all even digits

#117

Post by nneonneo »

saagarjha wrote: post #116
eru wrote: post #111

Earlier quoted context omitted.

> My rather hasty prototype is actually implemented in Python - not a language you want to do tons of arithmetic in [...] It might actually not be too bad? The actual big integer arithmetic is written in some fast language, and Python is just the glue holding everything together.

I don't think Python has a particularly optimized bignum implementation.

Additionally, it requires allocating memory for every operation. With a mutable bigint type, or fixed-size large integers (e.g. uint256) we could skip a lot of allocation overhead. I have previously prototyped big integer algorithms in Python, and when rewriting to Rust I have gotten massive speedups - there are just so many more opportunities to optimize in Rust/C/C++ than in Python.

Re: Powers of 2 with all even digits

#118

Post by eru »

saagarjha wrote: post #116
eru wrote: post #111

Earlier quoted context omitted.

> My rather hasty prototype is actually implemented in Python - not a language you want to do tons of arithmetic in [...] It might actually not be too bad? The actual big integer arithmetic is written in some fast language, and Python is just the glue holding everything together.

I don't think Python has a particularly optimized bignum implementation.

Well, it's still better than trying to implement bignums in Python itself on top of limited precision integers.

I'm not even sure whether the prototype in question here uses bignums. Perhaps they use numpy in some clever way (which would probably be a better illustration of my thesis). Or perhaps it's fast enough as it is?

Post reply on HN