Teaser 2406 Sunday Times 02.11.08

[Thirsty1]

For a school project, Penny was investigating the powers of 3. She wrote some down and explained to Joe that the first power was 3, the second power was 9, the third power was 27, and so on. Soon the numbers were in the millions and Joe asked how close to a whole number of millions one of the high powers could be. Simply by some clever logic and algebra Penny was soon able to answer the question. She also found the lowest power of 3 that actually came that close. What power (eg 248th) was it? The answer given was 50000th, but I can't see the clever logic and algebra required to solve! Please help.

[factor-fiction]

I think the sum of the digits of all powers of 3 after 3� will add up to 9 (or a multiple thereof)-

3� = 27, 3⁴=81, 3⁵ =243, etc

Maybe it uses that result?

I'll do some thinking.

[Thirsty1]

Thanks factor30. I was on the same track & am reasoning that the closest power has to be an odd number xmillion+or-1 where the sum of the digits is a multiple of 9. eg999999 or 8000001 etc. But 3^50000=1.1554...e+23856 and x =1.1554...e+23850 or 1.1554...e+23862 where the numbers are so huge I can't check how close they are!
I need to crack this clever logic & algebra spoken about in the question. I've tried reducing it to logs but didn't seem to help much.

[factor-fiction]

Just logged back on.

I think it's something to do with this:

When n is > 4 and n is even, then 3ⁿ always has n/2 digits.
For example 3⁴ = 81 has 2 digits and 3⁸ = 6561 has 4 digits.
So, for example, 3⁸ = (a₄x 10⁴) + (a₃x 10�) + (a₂x 10�) + (a₁x 10�).
The general nth term is:
3ⁿ=( a subscriptn x 10ⁿ)+ .....+ (a₁ x 10�)

Now consider numbers one less than full millions. They will be of the form
10ⁿ - 1 (different n to above)
Consider when n=4:
10⁴-1 = 9999= 9 x 10⁴+ 9 x 10�+ 9 x 10� + 9 x 10�
Replace each 9 by 3�
Now consider the general term for 10ⁿ - 1 .


Take it from there. I can't type any more up as the symbols are not easy to type up, but you need to find where the two terms are equal

[factor-fiction]

Typo in above due to messing with fiddly symbols. Should read:


When n is > 4 and n is even, then 3ⁿ always has n/2 digits.
For example 3⁴ = 81 has 2 digits and 3⁸ = 6561 has 4 digits.
So, for example, 3⁸ = (a₄x 10�) + (a₃x 10�) + (a₂x 10�) + (a₁)
The general nth term is:
3ⁿ=( a subscriptn x 10^n-1)+ .....+ (a₁ x 1)

Now consider numbers one less than full thousands or millions. They will be of the form
10ⁿ - 1 (different n to above)
Consider when n=4:
10⁴-1 = 9999= 9 x 10�+ 9 x 10�+ 9 x 10� + 9 x 10�
Replace each 9 by 3�
Now consider the general term for 10ⁿ - 1 .

Good luck

[factor-fiction]

I was wrong- number can't be n million -1. It must be n million +1. This is because all cubes have an odd last digit as we know and the penultimate digit is always even. So it can't end 999999. So I think you are looking for one that ends 000001
The only cubes that end in a 1 are multiples of 4- ie 3^4, 3^8, 3^12 etc.

I think it's best just to try to spot a pattern

[factor-fiction]

Think I can see it. Look at every 4th power-, e.g. 4^12, 4^16, 4^20. See what steps they go up in. Then extrapolate from one of them to work out when you will get to one ending in 000001

[factor-fiction]

Managed to get it yet, Thirsty1? Here's what I've got.

Every 4th power ends in a 1 (3^0=1, 3^4= 81, 3^8 =6561, etc)

Every 20th power ends in 01 :
3^0=1
3^20= 3486784401.
3^40 is (3^20)^2.
So you square the number. It will end in ...801.

Then 3^60 is 3^20 x 3^40.
This will end in ...401 x ..801=...201

Try another and you'll see every 20th power goes up in steps of xxx....xxx400.

So, starting from 4^0=1, you need to see how many steps of 400 you need to go up in to get to a million. That's 2500 steps. Each step is power 20. So that means power of 50000.

So 4^50000 is a number ending in 000001

[Thirsty1]

Thanks factor30-Your solution is nice & simple & it also proves that 50000 is the lowest power that comes that close. And by your same reasoning the next powers that give a difference of 1 will also be in steps of 50000.
ie 3^50000, 3^100000, 3^150000, 3^200000 etc.

I proved that 3^50000 did in fact end in 000001 ignoring the millions by using modular arithmetic as follows:-
3 = 3 mod 10^6
3^10 = 3^10 mod 10^6 =59049 mod 10^6
3^20 = (3^10)^2 = 59049^2 mod 10^6 = 784401 mod 10^6
3^100 = (3^20)^5 = 784401^5 mod 10^6 = 522001 mod 10^6
3^500 = (3^100)^5 = 522001^5 mod 10^6 = 610001 mod 10^6
3^2500 = (3^500)^5 = 610001^5 mod 10^6 = 50001 mod 10^6
3^12500 = (3^2500)^5 = 50001^5 mod10^6 = 250001 mod 10^6
3^50000 = (3^12500)^4 = 250001^4 mod 10^6 = 1 mod 10^6

However I was working towards the given answer & not knowing that it would have taken a lot of trial & error to arrive at . Also this doesn't prove that this is the lowest power satisfying a diff. of 1 like your neat solution did. Thanks once again