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

61–70 of 123 posts

Re: Powers of 2 with all even digits

#61

Post by theamk »

toxik wrote: post #48
vhcr wrote: post #42

Earlier quoted context omitted.

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.

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.

Re: Powers of 2 with all even digits

#63

Post by esnard »

madcaptenor wrote: post #47
lanna wrote: post #30

How many powers of 2 have just a single even digit? 2, 4, 8, 16, 32, 512...

Looks like that's all of them. The typical number of even digits of n grows like a constant times n, so you need some very large deviations from t I'd conjecture the number of powers of 2 with exactly m even digits is finite for all m.

Just tested up to 2 * 1000000, and it indeed looks like that's all of them.

Re: Powers of 2 with all even digits

#64

Post by Retr0id »

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…

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.

Re: Powers of 2 with all even digits

#65

Post by bitwize »

Not all even digits, but I'm still mindblown that 33554432 is a power of 2 (2^25). It makes a nice little song on one of those singing calculators from the 80s that play a little tune with a different note for each digit.

Re: Powers of 2 with all even digits

#66

Post by waffletower »

Definitely not finite in radix-16 (hexadecimal): [2 4 8 10 20 40 80 100 200 400 800 1000 2000 4000 8000 10000 20000 40000 80000 100000 200000 400000 800000 1000000 ...]

or radix-8 (octal): [2 4 10 20 40 100 200 400 1000 2000 4000 10000 20000 40000 100000 ...]

Interesting puzzle due to radix representation and sequence interactions.

Re: Powers of 2 with all even digits

#67

Post by madcaptenor »

bitwize wrote: post #65

Not all even digits, but I'm still mindblown that 33554432 is a power of 2 (2^25). It makes a nice little song on one of those singing calculators from the 80s that play a little tune with a different note for each digit.

A puzzle you might appreciate: 2^29 is a nine-digit number. All nine digits are different. Which of the ten digits is missing? Figure it out without computing 2^29 explicitly.

Re: Powers of 2 with all even digits

#68

Post by parsimo2010 »

waffletower wrote: post #66

Definitely not finite in radix-16 (hexadecimal): [2 4 8 10 20 40 80 100 200 400 800 1000 2000 4000 8000 10000 20000 40000 80000 100000 200000 400000 800000 1000000 ...] or radix-8 (octal): [2 4 10 20 40 100 200 400 1000 2000 4000 10000 20000 40000 100000 ...] Interesting puzzle due to radix representation and sequence interactions.

I'm not a number theorist, but I note that 16 is 2^4 and 8 is 2^3 (both powers of 2). Maybe there is a provable statement about whether these lists are finite in bases that are not 2^k, and maybe there is a bound on the length of the list by the value of log_2(base).

I'm not going to write it out, there is certainly a proof that the list is infinite in base 2^k (for integer k >= 2). I'm more wondering about how hard it is to prove that the list is finite in a different base.

Re: Powers of 2 with all even digits

#69

Post by sltkr »

theamk wrote: post #59
WithinReason wrote: post #3

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

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!

Re: Powers of 2 with all even digits

#70

Post by kens »

sweezyjeezy wrote: post #40
andrewla wrote: post #7

This is remarkable! I always find it fascinating that simple to express properties lack a proof. This is a very simple thing to evaluate and seems like it should be straightforward to establish that 2048 is the highest such power.

Base‑10 is just our chosen way of writing numbers, it doesn’t need to have any deep relationship with the arithmetic properties of sequences like the powers of 2. For most series (Fibonacci numbers, factorials etc), the digits for large members will be essentially random, their digits don't obey any pattern - it's just two unconnected things. It seems extremely likely that 2048 is the highest, but there might not be…

Yes, I find math problems that depend on base 10 to be unsatisfying because they rely on arbitrary cultural factors of how we represent numbers. "Real" mathematics should be universal, rather than just solving a puzzle.

Of course, such a problem could yield deep insight into number theory blah blah blah, but it's unlikely.

Post reply on HN