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

81–90 of 123 posts

Re: Powers of 2 with all even digits

#81

Post by theamk »

sltkr wrote: post #69
theamk wrote: post #59

Earlier quoted context omitted.

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.

Re: Powers of 2 with all even digits

#83

Post by theamk »

theamk wrote: post #81
sltkr wrote: post #69

Earlier quoted context omitted.

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 na…

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.

Re: Powers of 2 with all even digits

#84

Post by Retr0id »

sebzim4500 wrote: post #77
Retr0id wrote: post #64

Earlier quoted context omitted.

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

Re: Powers of 2 with all even digits

#85

Post by thaumasiotes »

AnotherGoodName wrote: post #58
WithinReason wrote: post #3

No additional terms up to 2^(10^10). - Michael S. Branicky, Apr 16 2023 How did he do this?

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…

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

Re: Powers of 2 with all even digits

#86

Post by [deleted] »

theamk wrote: post #61
toxik wrote: post #48

Earlier quoted context omitted.

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.

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.

[deleted]

Re: Powers of 2 with all even digits

#87

Post by gridspy »

sltkr wrote: post #78
WithinReason wrote: post #3

No additional terms up to 2^(10^10). - Michael S. Branicky, Apr 16 2023 How did he do this?

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 a…

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.

Re: Powers of 2 with all even digits

#88

Post by pinkmuffinere »

bluewin wrote: post #79

I worked on this once after an argument with my boyfriend. The original argument was "the ones digit has permanent pattern in 2^n {2,4,8,6,2...}. We made a system to generate digits for powers of two, although eventually we just made one that can take arbitrary bases, and found that you can decompose digit frequency and find a variety of NMR like resonances that vary based on where you terminate data collection. It w…

> I worked on this once after an argument with my boyfriend.

Wow I love this relationship dynamic! you sound like very cool people

Re: Powers of 2 with all even digits

#89

Post by gavinsyancey »

sltkr wrote: post #69
theamk wrote: post #59

Earlier quoted context omitted.

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!

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.

Re: Powers of 2 with all even digits

#90

Post by francoi8 »

IsTom wrote: post #45

It might be finite, but it also has a "fast growing sequence" kind of smell too.

I wonder if we can get a sense of how fast it would grow if we hypothesize it is an infinite sequence.

And if it is a finite sequence, one could define f(p, n) as the sequence of successive exponents of 2 such that the ratio of even digits over its total number of digits is greater than p. This could be an interesting way of describing a set of fast growing functions from exponential growth (p=0) to arbitrarily fast growth as p grows closer to 1 (or P where P is the smallest number such that f(P, n) is a finite sequence).

Post reply on HN