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 digits are even. The relevant OEIS sequence is here: https://oeis.org/A096549
Context: I wrote a search program that is substantially faster - it takes just a few minutes to get up to 2^(10^13), although my laptop's limited memory is starting to be a problem (my intermediate result file is already nearly 1GB in size). Unfortunately, it seems there are no results up to 2^15258789062500, which is a 4.5-trillion digit number.
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 was really fun and this makes me want to get back into this so I could check the properties of those resonances across bases and stopping points for data collection.
> 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.
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 filter almost every k.
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 an odd digit in its last 32 digits is 2^3789535319. So it makes sense to try increasingly large values of X until you are able to rule out all values of 2^k for k up to 10^10.
Here's a C++ program you can run to replicate this proof. It takes around 20 minutes to run, and can probably be optimized further, but it shows the principle: https://pastebin.com/DVK2JKdq
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 per decimal digit.
All up 10^10 powers * ((10^4.3)/2) decimal digits to calculate and check for each of those powers. Around 200 trillion operations all up in human terms. It's still hard enough you'd want a lot of compute. Getting each operation down to a nanosecond still means you're waiting 2.3days for a result. But it's also fair to say it's feasible.
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.
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 a good reason that could lead to a proof - it's just that larger and larger random numbers have less and less chance of satisfying the condition (with a tiny probability that they do, meaning we can't prove it).
Interestingly, there are results in the other kind of direction. Fields medalist James Maynard had an amazing result that there are infinitely many primes that have no 7s (or any other digit) in their decimal expansion. This actually _exploits_ the fact that there is no strong interaction between digits and primes - to show that they must exist with some density. That kind of approach can't work for finiteness though.
Everything about this seems so arbitrary. You look at the powers of an arbitrary number (here, 2), you pick an arbitrary base (here, 10) in which to express those powers, and ask for a random property of its digits (whether they belong to the set {0,2,4,6,8}).
Nothing about this question feels natural. I've noticed that random facts often don't have simple proofs.
I thought that at first as well. Then I read the notes which made me reframe it as ‘odds your digit sequence won’t include a six ever’ and note that checking up to 2^50000 has only two candidates with the first 15 digits even, and I came down on ‘shrinking so quickly it’s super unlikely’. No proof here due to HNs comment limits of course..
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).
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) < 10^n. Let us consider the 10^(n+1) > 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.
> 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.
This uses much higher order sieves so that it runs about 32000 times faster than the naive algorithm and was able to search to this point on a single core. It is also possible to thread this algorithm relatively easily.
For those curious, one relevant field of mathematics that could be used to prove properties of this sequence would be Sieve theory: https://en.m.wikipedia.org/wiki/Sieve_theory
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
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.
for 2^n only zeroes are shifted in, to all eternity. thus the lowest digits go through a fixed cycle.
as the top but is shifted to the left in each shift+add-threes-where-needed cycle, and leaves "it's" bcd digit after four such cycles, I intuit the next bcd byte will also switch to some cycle, as it's 'input' is boringly deterministic: all zeroes for the lowest digit, leading to 1, 2, 4, 8 (1)6, (1)2, 4, 8, (1)6, (1)2, ... so 0000(1100)* is shifted in to the tens digit.
that gives 0,0,0,0,
0+1, 2+1, 6, (1)2,
4+1, (1)0+1, 2, 4,
8+1, (1)8+1, (1)8, (1)6,
(1)2+1, 6+1, (1)4, 8,
(1)6+1, (1)4+1, (1)0, 0,
0+1, 2+1, ... for the tens digit. which has a period of 20 ... with a shift to hundreds pattern of 0000(00010100011110101110)* and an odd odd even even rhythm on the tens digit.
noice.
some number nerds will for sure figure or know ways to spin this on for the hundreds digit. and determine the periodicity of having all the lowest n digits even. or the loss of that periodicity... because maybe just maybe this spins into some wheel where one of the digits foo to bar always is odd. and then you can stop searching...
but what do I know.
I just Dunning-Kruger an intuition that the "double dabble" bin2bcd _may_ be useful in this :-D
Somehow I missed the title and wondered what the fuck was going on...
2, 4, 8, 64, 2048 are powers of 2 (i.e. 2^n), and they don't contain odd numbers (e.g. 16, 128, 1024 contain 1 so are not in this list, same with 4096 containing 9).
I'm confused by your comment. First, powers of two are 2^n not n^2. But what do you mean you missed the title and wondered what was going on? How could you expect to understand the contents without reading the title? Surely I'm missing something.
nneonneo|11 months ago
Context: I wrote a search program that is substantially faster - it takes just a few minutes to get up to 2^(10^13), although my laptop's limited memory is starting to be a problem (my intermediate result file is already nearly 1GB in size). Unfortunately, it seems there are no results up to 2^15258789062500, which is a 4.5-trillion digit number.
FartyMcFarter|11 months ago
This would avoid using a lot of memory, and it would also be faster.
shrx|11 months ago
bluewin|11 months ago
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 was really fun and this makes me want to get back into this so I could check the properties of those resonances across bases and stopping points for data collection.
zoky|11 months ago
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.
pinkmuffinere|11 months ago
Wow I love this relationship dynamic! you sound like very cool people
swyx|11 months ago
what.. what other arguments have you had?
i request highlight reel
WithinReason|11 months ago
How did he do this?
lifthrasiir|11 months ago
sltkr|11 months ago
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 an odd digit in its last 32 digits is 2^3789535319. So it makes sense to try increasingly large values of X until you are able to rule out all values of 2^k for k up to 10^10.
Here's a C++ program you can run to replicate this proof. It takes around 20 minutes to run, and can probably be optimized further, but it shows the principle: https://pastebin.com/DVK2JKdq
AnotherGoodName|11 months ago
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 per decimal digit.
All up 10^10 powers * ((10^4.3)/2) decimal digits to calculate and check for each of those powers. Around 200 trillion operations all up in human terms. It's still hard enough you'd want a lot of compute. Getting each operation down to a nanosecond still means you're waiting 2.3days for a result. But it's also fair to say it's feasible.
LeftHandPath|11 months ago
fdej|11 months ago
Here is a C program that does the verification up to 2^(10^10) in 30 seconds: https://gist.github.com/fredrik-johansson/8924e10e5d74e39109...
Edit: made it multithreaded, goes up to 2^(10^12) in nine minutes on 8 cores.
theamk|11 months ago
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.
38|11 months ago
waffletower|11 months ago
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.
parsimo2010|11 months ago
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.
hrldcpr|11 months ago
andrewla|11 months ago
sweezyjeezy|11 months ago
Interestingly, there are results in the other kind of direction. Fields medalist James Maynard had an amazing result that there are infinitely many primes that have no 7s (or any other digit) in their decimal expansion. This actually _exploits_ the fact that there is no strong interaction between digits and primes - to show that they must exist with some density. That kind of approach can't work for finiteness though.
codeflo|11 months ago
Nothing about this question feels natural. I've noticed that random facts often don't have simple proofs.
guy234|11 months ago
Sharlin|11 months ago
IsTom|11 months ago
vessenes|11 months ago
francoi8|11 months ago
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).
Mae_soph|11 months ago
Assume this list is complete up to 10^n. We find the biggest l such that 2^(5^(l - 1)*4) < 10^n. Let us consider the 10^(n+1) > 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.
LegionMammal978|11 months ago
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.
IIAOPSW|11 months ago
ted_dunning|11 months ago
https://github.com/tdunning/EvenDigits
This uses much higher order sieves so that it runs about 32000 times faster than the naive algorithm and was able to search to this point on a single core. It is also possible to thread this algorithm relatively easily.
Aardwolf|11 months ago
openasocket|11 months ago
lanna|11 months ago
madcaptenor|11 months ago
I'd conjecture the number of powers of 2 with exactly m even digits is finite for all m.
sltkr|11 months ago
The powers of 2 with a single even digit are just those double those numbers (i.e., the next higher power of 2).
vanderZwan|11 months ago
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
bitwize|11 months ago
madcaptenor|11 months ago
jmount|11 months ago
chasing|11 months ago
Someone|11 months ago
If we allow cheating, there are infinitely many. 2^(^2log(3.57)) equals 3.57, for example.
317070|11 months ago
detaro|11 months ago
kristopolous|11 months ago
As in, could you somehow solve it without knocking the other two down in a major way?
froh|11 months ago
https://en.wikipedia.org/wiki/Double_dabble
for 2^n only zeroes are shifted in, to all eternity. thus the lowest digits go through a fixed cycle.
as the top but is shifted to the left in each shift+add-threes-where-needed cycle, and leaves "it's" bcd digit after four such cycles, I intuit the next bcd byte will also switch to some cycle, as it's 'input' is boringly deterministic: all zeroes for the lowest digit, leading to 1, 2, 4, 8 (1)6, (1)2, 4, 8, (1)6, (1)2, ... so 0000(1100)* is shifted in to the tens digit.
that gives 0,0,0,0, 0+1, 2+1, 6, (1)2, 4+1, (1)0+1, 2, 4, 8+1, (1)8+1, (1)8, (1)6, (1)2+1, 6+1, (1)4, 8, (1)6+1, (1)4+1, (1)0, 0, 0+1, 2+1, ... for the tens digit. which has a period of 20 ... with a shift to hundreds pattern of 0000(00010100011110101110)* and an odd odd even even rhythm on the tens digit.
noice.
some number nerds will for sure figure or know ways to spin this on for the hundreds digit. and determine the periodicity of having all the lowest n digits even. or the loss of that periodicity... because maybe just maybe this spins into some wheel where one of the digits foo to bar always is odd. and then you can stop searching...
but what do I know.
I just Dunning-Kruger an intuition that the "double dabble" bin2bcd _may_ be useful in this :-D
millipede|11 months ago
unknown|11 months ago
[deleted]
darepublic|11 months ago
kazinator|11 months ago
1970-01-01|11 months ago
[deleted]
karamanolev|11 months ago
nickvec|11 months ago
heffer|11 months ago
netsharc|11 months ago
2, 4, 8, 64, 2048 are powers of 2 (i.e. 2^n), and they don't contain odd numbers (e.g. 16, 128, 1024 contain 1 so are not in this list, same with 4096 containing 9).
mtoner23|11 months ago
monktastic1|11 months ago