[HN Gopher] Powers of 2 with all even digits
___________________________________________________________________
Powers of 2 with all even digits
Author : Hbruz0
Score : 210 points
Date : 2025-03-20 11:55 UTC (11 hours ago)
(HTM) web link (oeis.org)
(TXT) w3m dump (oeis.org)
| WithinReason wrote:
| _No additional terms up to 2^(10^10). - Michael S. Branicky, Apr
| 16 2023_
|
| How did he do this?
| 38 wrote:
| yeah that's weird - its kind of a pointless comment without an
| included algorithm or something
| madcaptenor wrote:
| There's probably a smart way to rule out a lot of cases so
| you only have to check a relatively small number of
| candidates. It would be good to know what it is.
| taneq wrote:
| I guess the margin was too small to contain it.
| vhcr wrote:
| 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.
| toxik wrote:
| 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.
| showerst wrote:
| Just by sheer numbers, the comment you're replying to
| must be one of the provably wrong-est comments in history
| of hacker news =).
| shiandow wrote:
| You only need to check the actual powers of two.
|
| 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)
| theamk wrote:
| 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.
| lifthrasiir wrote:
| 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.
| andrewla wrote:
| > 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 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.
| lifthrasiir wrote:
| Oh, yeah, I should have said 2^k mod _100_ has no odd
| digits.
| madcaptenor wrote:
| 10^10 * 36105/39062500 = 9242880, so you're already down to
| under 10^7 cases to check, which is starting to seem more
| tractable.
| dmurray wrote:
| 10^7 cases, but almost every case has billions of digits.
|
| 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?
| andrewla wrote:
| I see my error here -- you can in fact eliminate half even
| for 2^k mod 10, because both 6 and 8 force a carry; so
| ending in a 2 or a 6 means that the next higher digit must
| be odd.
| Retr0id wrote:
| 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.
| sebzim4500 wrote:
| That's not possible, at minimum 2,4,8,64,2048 would all
| be the the cycle for `k >= 4`.
| Retr0id wrote:
| I don't follow
| sebzim4500 wrote:
| Looking back I don't know what I was thinking ignore me.
| LeftHandPath wrote:
| Hah, I had Michael Branicky as a professor (for his AI course)
| at the time (Jan - May 2023). Didn't expect to see his name
| here. He's a brilliant guy.
| AnotherGoodName wrote:
| 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.
| thaumasiotes wrote:
| > 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.
| theamk wrote:
| 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.
| sltkr wrote:
| 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 =
| 5x10^19 elemental operations. At one operation per nanosecond
| that takes 1584 years of CPU time. Not at all easy to brute
| force!
| theamk wrote:
| 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.
| theamk wrote:
| 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.
| gavinsyancey wrote:
| 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.
| sltkr wrote:
| 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
| gridspy wrote:
| 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.
| fdej wrote:
| Just check for the existence of at least one odd digit mod 10^B
| for some well chosen B.
|
| 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.
| andrewla wrote:
| 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.
| guy234 wrote:
| why should it be straightforward to establish that?
| Sharlin wrote:
| Proofs of non-existence aren't usually straightforward.
| andrewla wrote:
| I mean, clearly it isn't in this case. But given that the
| digits of 2^n are cyclical at each decimal position, it does
| feel like this should fall out of some sort of chinese
| remainder theorem manipulation.
| Sharlin wrote:
| True. It might also just be that the question hasn't
| attracted the attention of number theorists, and finding a
| proof wouldn't be unreasonably difficult to an expert in
| the field.
| LegionMammal978 wrote:
| Nope, it's not that easy in this case. E.g., Erdos
| conjectured in 1979 that every power of 2 greater than
| 256 has a digit '2' in its ternary expansion [0]. This
| makes sense heuristically, but no methods since then have
| come close to proving it.
|
| 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.)
|
| [0] https://arxiv.org/abs/math/0512006
| Sharlin wrote:
| Thanks!
| codeflo wrote:
| 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.
| LegionMammal978 wrote:
| In this case, it doesn't even help to downsize the problem.
| Erdos once asked the same question, but with powers of 2,
| base 3, and the set {0,1}. (If you want to, you can disguise
| that version as something more natural-looking like "Which
| powers of 2 can be expressed as the sum of distinct powers of
| 3?") But we're still nowhere close to solving it.
| intalentive wrote:
| You can generalize it if you want. Given powers of p in base
| b, what is the largest n=p^i such that each digit is
| divisible by k. Here we have: if p=2, b=10, k=2, then n=2048
| and i=11. Why? Maybe there is a deeper reason that applies to
| all values of p, b, k.
| sweezyjeezy wrote:
| 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.
| kens wrote:
| 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.
| netsharc wrote:
| 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).
| monktastic1 wrote:
| 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.
| mtoner23 wrote:
| why comment about your misunderstanding of the title?
| hrldcpr wrote:
| The base 2 list is even shorter.
| lanna wrote:
| How many powers of 2 have just a single even digit? 2, 4, 8, 16,
| 32, 512...
| madcaptenor wrote:
| 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.
| esnard wrote:
| Just tested up to 2 * 1000000, and it indeed looks like
| that's all of them.
| recursive wrote:
| Asterisk means exponent here?
| esnard wrote:
| Yes. I didn't escape the asterisks before posting, and HN
| replaced ** with \\* without me noticing.
| sltkr wrote:
| This is equivalent to asking: how many powers of 2 are there
| such that all digits except the leading digit are 5 or greater?
|
| The powers of 2 with a single even digit are just those double
| those numbers (i.e., the next higher power of 2).
| IsTom wrote:
| It might be finite, but it also has a "fast growing sequence"
| kind of smell too.
| vessenes wrote:
| 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..
| francoi8 wrote:
| 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).
| chasing wrote:
| Yeah, but how many powers of 2 have all odd digits?
| detaro wrote:
| 0
| joshuaissac wrote:
| > 0
|
| 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.
| ddalcino wrote:
| I think you forgot one.
| SamBam wrote:
| Nice double-meaning.
| Someone wrote:
| 2^0 = 1
|
| If we allow cheating, there are infinitely many.
| 2^(^2log(3.57)) equals 3.57, for example.
| 317070 wrote:
| 2^0 and 2^{-1}. other positive integers will end on an even
| number, other negative integers will end with the numbers 25.
| bitwize wrote:
| 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.
| madcaptenor wrote:
| 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.
| waffletower wrote:
| 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.
| parsimo2010 wrote:
| 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.
| ethanwillis wrote:
| 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 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.
| ethanwillis wrote:
| 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.
| openasocket wrote:
| 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
| bluewin wrote:
| 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.
| pinkmuffinere wrote:
| > I worked on this once after an argument with my boyfriend.
|
| Wow I love this relationship dynamic! you sound like very cool
| people
| Nifty3929 wrote:
| Followed by "... We made a system to generate digits for
| powers of two" ('we' not 'I')
|
| That's awesome!
| swyx wrote:
| is this kind of argument normal for you two?
|
| what.. what other arguments have you had?
|
| i request highlight reel
| zoky wrote:
| > _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 number >= 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 number 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.
| froh wrote:
| I wonder if the double dabble binary to decimal algorithm could
| be modified to check this relatively efficiently?
|
| 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
| Aardwolf wrote:
| In base 2 there are 0 of those since all are of the form 1000...
| nneonneo wrote:
| 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.
| FartyMcFarter wrote:
| 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.
| shrx wrote:
| Is your algorithm published somewhere?
| jmount wrote:
| Simple permutations of digits: https://rworks.dev/posts/digital-
| difficulties/
___________________________________________________________________
(page generated 2025-03-20 23:00 UTC)