# How many powers of 2 are easy to double? [duplicate]

Possible Duplicate:
Is 2048 the highest power of 2 with all even digits (base ten)?

Numbers written in base $10$ are easiest to double when their digits lie in the range $0, \ldots, 4$, so that no carries are performed. For instance, ...

• $1$ is easy to double, yielding $2$;
• $2$ is also easy to double, yielding $4$;
• $4$ is also also easy to double, yielding $8$;
• but $8$ is not easy to double, since $8+8 = 16$ involves a carry.

The only numbers $2^n$ which are easy to double that I'm aware of are the three listed above, along with $2^5 = 32$ and $2^{10} = 1024$. My suspicion is that $2^{10}$ is the last such power of $2$, and that's my question:

My question is: Is $2^{10} = 1024$ the last example of a power of $2$ which is easy to double? If it isn't the last example, how many more are there? Is there a(n infinite) family of examples which is easy to produce?

There's an theorem of Kummer which can be used to solve a "base $p$ analogue" of this question for $p$ a prime:

Theorem (Kummer): In $p$-adic arithmetic, the number of times a carry is performed when adding the numbers $n$ and $m$ (in base $p$) is equal to the number of times $p$ divides the binomial coefficient $\binom{n+m}{m}$.

I haven't found any analogue that holds in base $10$. An essential obstacle is that $\binom{5}{3} = 10$ shows that $2 + 3$ has carries when written both in base $2$ and base $5$, but not in base $10$. Because of this sort of phenomenon, I suspect that this isn't the right way to approach my problem, but it helps form a complete question and I thought someone might find it cute.

-

## marked as duplicate by Eric, Cameron Buie, Micah, Rahul, DidDec 8 '12 at 8:42

32 is easy to double. I ran a maple program up to $2^{1000}$ and only found 1,2,4,32,1024. – coffeemath Dec 8 '12 at 0:48
Ha, good point, I edited the question to include $32$ too. – Eric Dec 8 '12 at 0:56
There is an equivalent question on this site. The double of your numbers have all even digits... math.stackexchange.com/questions/116026/… – coffeemath Dec 8 '12 at 1:13
Oh, wonderful! I clicked around for related questions but somehow didn't find that one. This could probably be closed; anything said here will be directly relevant to that question. – Eric Dec 8 '12 at 1:19
I note with mild amusement that this has been marked as a duplicate question. :) – David H Aug 16 '13 at 23:01

Here's another potential approach to the problem: the powers of $2$ eventually fall into a cycle $\bmod\,10^k$ for each $k$, and this cycle isn't 'full' in the sense that it only has $4\cdot 5^{k-1}$ elements (see http://www.exploringbinary.com/cycle-length-of-powers-of-two-mod-powers-of-ten/ ); we only need all of these elements to include a digit $\geq 5$ for some $k$ to guarantee that there will always be a carry for any powers of $2$ larger than that cycle, and then the rest could easily be checked by hand. If we pretend that these elements are all independent, then the odds that any given one is 'high-digit-free' are $\frac{1}{2^k}$, which seems like good odds; unfortunately, there are so many numbers that have to avoid the 'high-digit-free' zone that it's impossible to reasonably bound the non-collision probability away from $1$ (if we only had $2^k$ elements then we would have probability roughly $\left(1-2^{-k}\right)^{2^k}\approx e^{-1}$ of avoiding a collision; with as many elements as we have, the probability that all of our cycle elements are good is roughly $e^{-2.5^k}$), so in fact it's probable that every cycle of powers of $2\bmod\,10^k$ contains some 'bad' (carry-free) set of trailing digits, even if no actual powers of $2$ do. Still, this would be easy enough to check for all $k$ up to some relatively modest bound, say $k=16$ or so.

-

Too long for a comment.

The question you are asking is basically the following: how many powers of two only conatin the digits 0,1,2,3 and 4. Or similarly, which power of two has all the digits even $2^{n+1}$ has this property if $2^n$ is easy to double.

It is very easy to prove that there are infinitely many powers of two which don't have this property. Actually, using the irrationality of $\log_2(10)$, it is easy to prove that given any $n$-digit number, there are infinitely many powers of two which start with that number. And you can also get a lower bound on the number of powers up to $N$ of two which can start with a certain combination, but I highly doubt that this can lead you anywhere. The best result you can hope for with this approach is is that between $1$ and $N$ at least $p\%$ are not easy to double, where you can probably get high percentages but never 100 $\%$.

-
I believe you can use equidistribution of $\{n \log_{10} 2\}$ to actually get 100% in the sense of natural density, but as you point out this is not the same as establishing finitely many counterexamples. Heuristically one expects finitely many easy-to-double powers, assuming that (a positive proportion of) digits are distributed randomly. – Erick Wong Dec 8 '12 at 0:51

In typical experimental tradition, let's write code to check this out.

(defun difficult-to-double-p (n)
(loop :for (x y) := (multiple-value-list (floor n 10))
:then (multiple-value-list (floor x 10))
:thereis (> y 4)
:until (zerop x)))

(defun test (max-pow)
(loop :for x := 1 :then (* 2 x)
:for i :from 0 :to max-pow
:unless (difficult-to-double-p x)
:do (format t "~D " i)))


This will print out the powers of 2 that satisfy your condition. I tried it up to $n=500,000$ and only came up with $\{0, 1, 2, 5, 10\}$. Is it a coincidence that those powers of 2, except for $n=0$, are factors of 10?

Here is the output for the curious.

> (test 500000)
0 1 2 5 10

Evaluation took:
174.270 seconds of real time
174.940405 seconds of total run time (173.307653 user, 1.632752 system)
[ Run times consist of 5.225 seconds GC time, and 169.716 seconds non-GC time. ]
100.38% CPU
371,799,804,896 processor cycles
46,761,694,928 bytes consed

NIL


EDIT: Instead of doubling, let's try $k$-tupling. Here's a good ol' table for $2 \le n \le 100$:

2: 0 1 2 5 10
3: 0 1 5
4: 0 1 5
5: 0
6: 0
7: 0 3 4
8: 0
9: 0
10: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100
11: 0 1 2 3
12: 0 1 2
13: 0 1
14: 0 1
15: 0
16: 0
17: 0
18: 0 2 6
19: 0 4
20: 0 1 2 5 10
21: 0 1 2
22: 0 1
23: 0 1
24: 0 1
25: 0
26: 0
27: 0
28: 0
29: 0
30: 0 1 5
31: 0 1
32: 0 1 2
33: 0 1
34: 0 1
35: 0
36: 0
37: 0
38: 0 2
39: 0 4
40: 0 1 5
41: 0 1
42: 0 1
43: 0 1
44: 0 1
45: 0
46: 0
47: 0
48: 0 2
49: 0 2
50: 0


EDIT 2: Next, let's try changing the base $b$, where the digits must be between $0$ and $\tfrac{b}{2}-1$ if $b$ is even, $\lfloor b/2\rfloor$ if odd. Here's a table of $b$ for $2 \le n\le 100$.

3: 0 2 8
4: 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70 72 74 76 78 80 82 84 86 88 90 92 94 96 98 100
5: 0 1 5 8
6: 0 1 3 9
7: 0 1 3 4 6 9
8: 0 1 3 4 6 7 9 10 12 13 15 16 18 19 21 22 24 25 27 28 30 31 33 34 36 37 39 40 42 43 45 46 48 49 51 52 54 55 57 58 60 61 63 64 66 67 69 70 72 73 75 76 78 79 81 82 84 85 87 88 90 91 93 94 96 97 99 100
9: 0 1 2 8 13 14
10: 0 1 2 5 10
11: 0 1 2 4 8 14 30
12: 0 1 2 4 6 12
13: 0 1 2 4 5 9 24
14: 0 1 2 4 5 8 10 25
15: 0 1 2 4 5 6 8 9 12 13 16 24
16: 0 1 2 4 5 6 8 9 10 12 13 14 16 17 18 20 21 22 24 25 26 28 29 30 32 33 34 36 37 38 40 41 42 44 45 46 48 49 50 52 53 54 56 57 58 60 61 62 64 65 66 68 69 70 72 73 74 76 77 78 80 81 82 84 85 86 88 89 90 92 93 94 96 97 98 100
17: 0 1 2 3 11 18
18: 0 1 2 3 7 13
19: 0 1 2 3 6 14 18 19 34
20: 0 1 2 3 6 7 11
21: 0 1 2 3 6 7 9 12 18 45
22: 0 1 2 3 5 9 11 12 19
23: 0 1 2 3 5 8
24: 0 1 2 3 5 7 25
25: 0 1 2 3 5 7 8 14 21
26: 0 1 2 3 5 6 13
27: 0 1 2 3 5 6 8 13
28: 0 1 2 3 5 6 8 12
29: 0 1 2 3 5 6 7 10
30: 0 1 2 3 5 6 7 10 11 13 15 22
31: 0 1 2 3 5 6 7 8 10 11 12 15 16 17 20 21 25 36
32: 0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 20 21 22 23 25 26 27 28 30 31 32 33 35 36 37 38 40 41 42 43 45 46 47 48 50 51 52 53 55 56 57 58 60 61 62 63 65 66 67 68 70 71 72 73 75 76 77 78 80 81 82 83 85 86 87 88 90 91 92 93 95 96 97 98 100
33: 0 1 2 3 4 14 23 42
34: 0 1 2 3 4 9 17 49
35: 0 1 2 3 4 8 12 14 40
36: 0 1 2 3 4 8 9
37: 0 1 2 3 4 7 11
38: 0 1 2 3 4 7 9 14 21 38
39: 0 1 2 3 4 7 9 13 16 33
40: 0 1 2 3 4 7 8 11 20 27
41: 0 1 2 3 4 7 8 9 15
42: 0 1 2 3 4 7 8 9 14 19 20 28
43: 0 1 2 3 4 6 12 20
44: 0 1 2 3 4 6 12 13 14 22
45: 0 1 2 3 4 6 9 12 13 14 15 24 25 26 36 45
46: 0 1 2 3 4 6 9 10 15
47: 0 1 2 3 4 6 8 19 21 39
48: 0 1 2 3 4 6 8 10 14 20
49: 0 1 2 3 4 6 8 9 13
50: 0 1 2 3 4 6 8 9 10 15 17 23


And here's a pictorial representation. Dot means easy, space means not.

  4: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5: ..   .  .
6: .. .     .
7: .. .. .  .
8: .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
9: ...     .    ..
10: ...  .    .
11: ... .   .     .               .
12: ... . .     .
13: ... ..   .              .
14: ... ..  . .              .
15: ... ... ..  ..  .       .
16: ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .
17: ....       .      .
18: ....   .     .
19: ....  .       .   ..              .
20: ....  ..   .
21: ....  .. .  .     .                          .
22: .... .   . ..      .
23: .... .  .
24: .... . .                 .
25: .... . ..     .      .
26: .... ..      .
27: .... .. .    .
28: .... .. .   .
29: .... ...  .
30: .... ...  .. . .      .
31: .... .... ...  ...  ..   .          .
32: .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .
33: .....         .        .                  .
34: .....    .       .                               .
35: .....   .   . .                         .
36: .....   ..
37: .....  .   .
38: .....  . .    .      .                .
39: .....  . .   .  .                .
40: .....  ..  .        .      .
41: .....  ...     .
42: .....  ...    .    ..       .
43: ..... .     .       .
44: ..... .     ...       .
45: ..... .  .  ....        ...         .        .
46: ..... .  ..    .
47: ..... . .          . .                 .
48: ..... . . .   .     .
49: ..... . ..   .
50: ..... . ...    . .     .
51: ..... . ...   . .       .
52: ..... ..      ...         .
53: ..... ..  . .       .    .
54: ..... .. .           .
55: ..... .. .  .
56: ..... .. .. .  .
57: ..... ...     .      .    .
58: ..... ...    .
59: ..... ... . .  .  . .       .                 .
60: ..... ... . .  ..     .
61: ..... ....  ..    .   .
62: ..... ....  ... . ..       ..    .
63: ..... ..... ....  ....  ...   ..    .       .
64: ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... ..... .....
65: ......           .          .            .
66: ......     .         .
67: ......    .    . .
68: ......    ..              .  .                            .
69: ......   .    .
70: ......   . .  . .            .
71: ......   ..     .. .   .        .    .
72: ......   ...   . .    ..
73: ......   ...  .    .
74: ......  .                  .
75: ......  .  . .      .
76: ......  . .     .      .         .
77: ......  . .  .  ..    .
78: ......  . .. . .    .                  .
79: ......  ..       .  ..              .
80: ......  ..   .  ..
81: ......  .. . ..
82: ......  ...      .      .
83: ......  ...   .  ..     .
84: ......  ....  . .     .         .  .
85: ......  .... .  ...  .  . .  .      .
86: ...... .     . .  .        .   .
87: ...... .     ..      ..      .
88: ...... .   . ...       .
89: ...... .   . .... .       .
90: ...... .  .  .....        ....         ..
91: ...... .  . .
92: ...... .  ..             .
93: ...... .  ...    .  .                                 .
94: ...... . .      .        .
95: ...... . .  .     .  .                  .
96: ...... . . .     .     .
97: ...... . . ..       .                     .
98: ...... . ..    .
99: ...... . .. .
100: ...... . ...      .   .        .


EDIT 3: Define base $b$ to be easy if there are an infinite number of easy doublings.

CONJECTURE 1: The only easy bases are $2^j$ for $j\ge 2$.

A friend noticed...

CONJECTURE 2: The only hard-to-double numbers in base $2^j$ are numbers whose power is $\{ij-1\mid i\ge 1\}$.

And from the picture, notice when the leftmost column gets thicker. It happens after each power of two.

CONJECTURE 3: $2^n$ in base $2^k$ is easy to double for all $k > n$.

-

If you do it in binary, all of them are very easy to double: Just append another $0$. For example, $\{1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, \ldots\}$.

-
Of course there is technically a "carry" in these base 2 examples. In fact here there are no digits possible which are less than half the base of 2. – coffeemath Dec 8 '12 at 2:58
@coffeemath True, but they do not make it any more difficult. – ctype.h Dec 8 '12 at 3:21
My phrase "of course" was meant to indicate that what followed was not meant as criticism, only the obvious remark that though not difficult, it isn't the same procedure of doubling each digit which the OP mentioned. – coffeemath Dec 8 '12 at 14:30