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

101–110 of 123 posts

Re: Powers of 2 with all even digits

#101

Post by FartyMcFarter »

nneonneo wrote: post #96

Fun fact: 2^133477987019 is the smallest power of two that ends with 40 even digits. In fact, it ends with 46 even digits - which is surprising, given that it is significantly smaller than 2^(2^46). The last 50 digits of this number are ...32070644226208822284248862288402404246620406284288. This number has over 40 billion digits, though, so it seems kind of unlikely that we will ever find another number where all the…

I think you can calculate "2^X mod (10^N)" where N is the number of digits using a modular exponentiation algorithm.

This would avoid using a lot of memory, and it would also be faster.

Re: Powers of 2 with all even digits

#102

Post by zoky »

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…

> The original argument was "the ones digit has permanent pattern in 2^n {2,4,8,6,2...}.

Isn’t that obviously the case (for n >= 1 anyway)? If each successive power of two is just the previous number times two, then it would always have to follow that pattern.

Any integer >= 10 can be expressed as the sum of a multiple of 10 plus a single digit number, for example 32 = 30 + 2. So 32 * 2 can be written as 2 * (30 + 2). And since any integer ending in zero multiplied by any integer must also end in zero, you only need to look at the single digit part of the number to see that a pattern must immediately emerge for powers of two, or of any number for that matter.

Re: Powers of 2 with all even digits

#103

Post by shrx »

nneonneo wrote: post #96

Fun fact: 2^133477987019 is the smallest power of two that ends with 40 even digits. In fact, it ends with 46 even digits - which is surprising, given that it is significantly smaller than 2^(2^46). The last 50 digits of this number are ...32070644226208822284248862288402404246620406284288. This number has over 40 billion digits, though, so it seems kind of unlikely that we will ever find another number where all the…

Is your algorithm published somewhere?

Re: Powers of 2 with all even digits

#104

Post by nneonneo »

shrx wrote: post #103
nneonneo wrote: post #96

Fun fact: 2^133477987019 is the smallest power of two that ends with 40 even digits. In fact, it ends with 46 even digits - which is surprising, given that it is significantly smaller than 2^(2^46). The last 50 digits of this number are ...32070644226208822284248862288402404246620406284288. This number has over 40 billion digits, though, so it seems kind of unlikely that we will ever find another number where all the…

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 all x >= k. So, after the k'th term, the rest will repeat with a particular cycle period. We'll manually test all of the 2^x for x The algorithm itself is a kind of sieving + lifting procedure: it inductively identifies all of the candidate exponents mod 5^(k-1)*4 which yield numbers with k trailing even digits (i.e. all even digits mod 10^k). Each such exponent will yield 5 possible exponents mod 10^(k+1) via a lifting procedure, which we can test; on average, half of these will have a top digit that is even and is therefore a candidate for the next power of 10 (10^(k+1)). Therefore, on average, we grow our candidate list by a factor of 2.5 per added digit - thus, for each 10^k, we test O(2.5^k) candidates (approximately 1.6*2.5^k, experimentally). This isn't too bad - at mod 10^19, we test only 55097940 candidates, representing every exponent below 5^18*4 = 15258789062500.

My rather hasty prototype is actually implemented in Python - not a language you want to do tons of arithmetic in - but it's still fast enough to chew through all those candidates in ~20 minutes on a single core. Obviously, there's ample room to make this faster; I figure a good, parallelized native (C/C++/Rust etc.) implementation could easily be 100x faster.

Re: Powers of 2 with all even digits

#105

Post by nneonneo »

FartyMcFarter wrote: post #101
nneonneo wrote: post #96

Fun fact: 2^133477987019 is the smallest power of two that ends with 40 even digits. In fact, it ends with 46 even digits - which is surprising, given that it is significantly smaller than 2^(2^46). The last 50 digits of this number are ...32070644226208822284248862288402404246620406284288. This number has over 40 billion digits, though, so it seems kind of unlikely that we will ever find another number where all the…

I think you can calculate "2^X mod (10^N)" where N is the number of digits using a modular exponentiation algorithm. This would avoid using a lot of memory, and it would also be faster.

I am already doing that (thanks to `pow(x, y, z)` in Python). The numbers I'm working with would have trillions of digits were it not for this trick - way more than 1GB. 1GB is what I use to store all of the candidates, in an inefficient JSON format.

Re: Powers of 2 with all even digits

#106

Post by Mae_soph »

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 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). If l > 10,that means that we can divide by b to get 2^(k-1)/b = c*10^d + 1 where c and d are nonzero integers. But this is a contradiction.

Now we only need to show up to 2^(5^10 * 4) to allow l > 10, which has already been done by other comments.

Re: Powers of 2 with all even digits

#108

Post by IIAOPSW »

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…

I might have a proof too but it is too large for the margin of this text box.

Re: Powers of 2 with all even digits

#109

Post by nneonneo »

andrewla wrote: post #13
lifthrasiir wrote: post #6

Earlier quoted context omitted.

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…

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

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.

Re: Powers of 2 with all even digits

#110

Post by RheingoldRiver »

ethanwillis wrote: post #76
ethanwillis wrote: post #74

Earlier quoted context omitted.

when dealing with only even and odd they are not finite in base 2^k. if we marked sequences of integers with 3 options. even, odd, other. then these lists are not finite in bases of 3^k. for four options. even, odd, other, another. then these lists are not finite in bases of 4^k. there is an intersection in the infinite lists where the base is equivalent to the power of an earlier base. so infinite lists for 2^k woul…

there is another similar problem about the largest number where all digits are prime numbers. which afaik has only been proven in base 10. similarly there the largest number with all prime digits actually differs if you ask the question in different bases. and there is also a pattern that exists to predict what the number will be in a given base.

> the largest number where all digits are prime numbers

do you mean the largest prime number where all digits are prime numbers?

Post reply on HN