Powers of 2 with all even digits

Original Article ↗ Hacker News Discussion ↗

How the 2^(10¹⁰) bound was checked

  • Initial puzzle: OEIS note claims “no additional terms up to 2^(10¹⁰)” with no algorithm given, prompting questions about feasibility.
  • Naive idea: literally compute 2^k in decimal for all k ≤ 10¹⁰ and scan digits. This is quickly recognized as prohibitively slow (O(n²) digit work, ~10¹⁹ operations).
  • Key observation: to prove 2^k is not all-even, it suffices to find a single odd digit, and this almost always occurs in the lowest few digits.

Filtering via modular arithmetic and cycles

  • Use residues modulo 10^B: for each exponent k, compute 2^k mod 10^B and check only those B low digits for an odd digit.
  • For most k, an odd digit appears in < ~40 low digits; someone pushed this to k up to 10¹⁵ using B=60.
  • Powers of 2 modulo 10^k are periodic, with cycle length given by φ(5^k) = 4·5^(k−1).
    • Only a small fraction of the cycle positions give all-even digits; at k=11, about 0.09% of the cycle.
  • This periodicity allows:
    • Precomputing cycles mod 10^k.
    • Sieve-style “lifting”: each all-even residue mod 10^k yields 5 candidates mod 10^(k+1); heuristically about half survive (2.5× growth per digit).
  • Efficient C code using such a modulus filter verifies no new terms up to 2^(10¹⁰) in ~30 seconds, and up to 2^(10¹²) in minutes on 8 cores. Another implementation reaches exponents < 10¹⁵ with high-order sieves.

Heuristics, (lack of) proof, and related problems

  • Many commenters believe 2048 is the last term, but no proof is known.
  • Digits of sequences like 2^n are viewed as “random-looking”; proving exact digit properties is notoriously hard.
  • Erdős-type conjectures about digits of powers in other bases are cited as analogously difficult and still unresolved.
  • One attempted proof sketch (using bounds on digits of 2^(k−1) and cycle arguments) is shown to break on a subtle step.

Base dependence and variations

  • In bases that are powers of 2 (e.g., base 8, 16), the analogous “all even digits” power-of-2 sequences are trivially infinite.
  • Discussion branches into:
    • Powers of 2 with exactly one even digit (apparently finite, with small known examples).
    • Generalizations to other bases, digit sets, and density-based sequences (e.g., requiring a high fraction of even digits).