Prove analytically that for any nonnegative integer k there exists a power of 3, terminating with 0..001, i.e. a sequence of k zeroes followed by digit 1,
e.g. k=0==> 3^0=1, 3^4 =81;
k=1==> 3^20=3486784401,
k=2==> 3^100= 515377520732011331036461129765621272702107522001.
Bonus question: Show that replacing the number 3 by any odd number, not terminating by 5, leaves your proof valid.

All you need is a power that ends in 1 and you can add in a zero before the one by raising to the power of 10.

Say 3^n is of the form 10x+1 (ie it ends in 1)
then (3^n)^10 = 3^(10n) = (10x)^10 + 10*(10x)^9 + 45*(10x)^8 +...+ 45*(10x)^2 + 10*(10x) + 1
Which clearly is of the form 100y+1
This gives a sequence of the form 3^(4*10^a) as ending with a zeros before the terminal 1.

Note: these are not the smallest numbers because if the last non-zero digit is even we can just multiply the exponent by 5 which will halve this digit.
This sequence of smallest exponents goes 4,20,100,500,5000,50000,...


To show this works for any odd (except multiples of 5) it is enough to show there is a power that ends in 1.
If it ends in 3 then the power is 4: (10x+3)^4 = 1000x^4 +1200x^3 +5400x^2 + 1080x + 81
If it ends in 1 (except for 1 itself) then the power is 1.
If it ends in 7 the power is 4.
If it ends in 9 the power is 2.

Posted by Jer on 2010-03-08 16:12:52