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.
Solution 1:
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.
Solution 2:
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 $\%$.
Solution 3:
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$.
Solution 4:
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\}$.