Powers of 2 with all even digits(oeis.org) |
Powers of 2 with all even digits(oeis.org) |
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.
This would avoid using a lot of memory, and it would also be faster.
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 < k (there aren't many) and then rely on the cycles to test all of the larger powers.
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.
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.
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.
Wow I love this relationship dynamic! you sound like very cool people
That's awesome!
what.. what other arguments have you had?
i request highlight reel
How did he do this?
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 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.
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 would overlap a subset of the infinite lists for 2^2^k=4^k
all prime bases, p, p^k would admit infinite lists that cover all the infinite lists for some composite base, c, c^k.
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).
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.
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.
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.
I'd conjecture the number of powers of 2 with exactly m even digits is finite for all m.
The powers of 2 with a single even digit are just those double those numbers (i.e., the next higher power of 2).
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
If we allow cheating, there are infinitely many. 2^(^2log(3.57)) equals 3.57, for example.
2^0 is a power of two and has all odd digits.
Edit: If we include negative powers, there is also 2^-1, which is all odd except for the leading zero before the decimal point.
As in, could you somehow solve it without knocking the other two down in a major way?
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
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).
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 an even subset of 36,105, meaning only .09% of the cycle is all-even.
This is all brute force; there's probably a more elegant way of computing this.
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
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.
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.
Aren't those operations divisions? One division would usually be considered more than one operation.
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.
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.
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!
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)
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.
Of course, such a problem could yield deep insight into number theory blah blah blah, but it's unlikely.
Nothing about this question feels natural. I've noticed that random facts often don't have simple proofs.
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.
do you mean the largest prime number where all digits are prime numbers?
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.
very smart! You duplicate the number while only keeping last few digits, to get basically O(n) complexity. Much better than my idea.
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'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?
As mentioned in another comment, the code is at: https://github.com/tdunning/EvenDigits
Digits of numbers are a wild beast, and they're tough to pin down for a specific sequence. At best, we get statistical results like "almost all sequences of this form have this property", without actually being able to prove it for any one of them. (Except sometimes for artificially-constructed examples and counterexamples, or special classes like Pisot numbers.)
Checking about 10^10 of them is just about doable as vhcr correctly showed. (I mean it wasn't optimal, but 'leave this running for 400 hours' is far from impossible)
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.
Even that doesn't seem so bad though, it's on the order of 10^16 total digits to check in the worst case, and far fewer in practice.
Maybe someone here can run a program overnight and increase the bound by another few orders of magnitude, or disprove the hypothesis?