Prove that there does not exist any positive integer N which is a power of 2 such that the digits of N (in the base ten representation) can be permuted to form a different power of 2. It is known that neither N nor any of the permutations of the digits of N can contain any leading zero.
When a number is doubled, its digital root doubles mod 9, and this is applicable to powers of 2:
1 1
2 2
4 4
8 8
16 7
32 5
64 1
128 2
256 4
512 8
1024 7
One can see how the digital root is related to the idea of "casting out 9's".
The thing to note here is that for powers of 2, the digital root has a cycle length of 6: as you go from one power of 2 to the next, you advance 1/6 of the way in the cycle.
If two powers of 2 contain the same number of digits, the larger could be 2, 4 or 8 times the smaller; that is, it can be only 3 powers of 2 higher, which is insufficient to advance to the repetition of the same digital root, which requires advancing six powers of 2. So the two can't have the same digits, otherwise they'd have the same digital root.
BTW, without the restriction against leading zeros, its probably also true, though I don't see a proof. The following program lists the non-zero digits used for powers of 2 up to 2000, in ascending order, each power on a separate record (line) of the file:
5 kill "pow2dig.txt"
10 open "pow2dig.txt" for output as #2
20 P=8
30 for Pwr=4 to 2000
40 P=P*2
50 S=str(P)
51 for I=1 to len(S)
52 if mid(S,I,1)="0" then mid(S,I,1)=" "
53 next
54 S=cutspc(S)
60 repeat
70 Done=1
80 for I=1 to len(S)-1
90 if mid(S,I,1)>mid(S,I+1,1) then
100 :H=mid(S,I,1):mid(S,I,1)=mid(S,I+1,1):mid(S,I+1,1)=H
110 :Done=0
120 next
130 until Done
140 print #2,S;" ";Pwr
150 next
such that, for example, the resulting file shows
122579 21
to represent 2^21 = 2097152
This file was sorted so that any powers of 2 using the same non-zero digits would be on successive records of the file, and no such matches were found in the portion of the records preceding the space before the power itself.
|
|
Posted by Charlie
on 2009-11-18 15:15:20 |
solution (spoiler)
