Enigma 1494 - Powerful logic
Chappy
New Scientist magazine, 17 May 2008.
By Bob Walker.
Joe found this problem in one of his old
maths books and gave it to Penny to solve.
But as there was no solution in the book,
Joe programmed his computer to find the
answer and check Penny's. All Penny had to
do was find the last three digits of:
3^123456
What are they?
Ciao,
Chappy.
Ted Schuerzinger
Let's see how long it takes for the last three digits to repeat
themselves:
001 003
002 009
003 027
004 081
005 243 <--- last digit repeats with period 4
006 729
007 187
008 561
009 683
010 049
011 147
012 441
013 323
014 969
015 907
016 721
017 163
018 489
019 467
020 401
021 203 <--- last two digits repeat with period 20
022 609
023 827
024 481
025 443
026 329
027 987
028 961
029 883
030 649
031 947
032 841
033 523
[...]
041 403
061 603
081 803
101 003 <--- last three digits repeat with period 100
How convenient. :-)
So, we're going to need the last three digits to 3^56. Taking the three
from 41 and multiplying them by the three from 15, we get 521. (We get
the same 521 if we square the number from 028).
I cheated a bit in that I used the Windows calculator to do the
calculating by three, so that I wouldn't make any dumb mistakes trying
to calculate the answers in my head.
--
Ted S.
fedya at hughes dot net
Now blogging at http://justacineast.blogspot.com
dgates
I didn't realize how quickly the last THREE digits would repeat
themselves, but I saw that the third digit from the end followed an
identifiable pattern for how it changed with period 20.
For example...
16 is 721
36 is 121
56 is 521
So I could guess that...
76 is 921
And then I could guess that 156, 256 and so on would also end in 521.
Mensanator
I cheated a lot and simply used Python.
>>> a = 3**123456
>>> b = str(a)
>>> print b[-3:]
521
Old is right. these problems need to be updated to use 12 to 15
digit exponents. Otherwise, they don't qualify as enigmas.
Richard Heathfield
We are asked for 3^123456 modulo 1000. I use % to indicate modulo.
I can't recall whether a^b % c is equivalent to (a%c)^(b%c)%c, which will
slow me down a bit, but I am at least certain that a^b%c is equivalent to
(a%c)^b%c, so I can use that. (No doubt there is a much, much quicker way,
but never mind that for now.)
Because x^y * x^z = x^(y+z), m^n = m^(n/2) * m^(n/2) = (m^(n/2))^2, so:
3^123456 = (3^61728)^2 = ((3^30864)^2)^2 = (((3^15432)^2)^2)^2 =
((((3^7716)^2)^2)^2)^2 = (((((3^3858)^2)^2)^2)^2)^2 =
((((((3^1929)^2)^2)^2)^2)^2)^2 = ((((((3*((3^964)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(((3^482)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3^241)^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((3^120)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((3^60)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((((3^30)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3^15)^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*((3^7)^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
We calculate 3^7 directly: 3^3 is 27, 27^2 is 729, and 3*729 is 2187.
((((((3*((((3*(((((3*((3^7)^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*(2187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
From now on, all = signs are assumed to mean "equals (modulo 1000)":
((((((3*((((3*(((((3*(2187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*(187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
187^2 is 34969, which is 969 (mod 1000).
((((((3*((((3*(((((3*(187^2))^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((3*969)^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((((2907)^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((((907^2)^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((822649^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(((649^2)^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((421201^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*((201^2)^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(40401^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*(401^2))^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((((3*160801)^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(((482403^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(((403^2)^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((162409^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*((409^2)^2))^2)^2)^2)^2)^2)^2
= ((((((3*(167281^2))^2)^2)^2)^2)^2)^2
= ((((((3*(281^2))^2)^2)^2)^2)^2)^2
= ((((((3*78961)^2)^2)^2)^2)^2)^2
= (((((236883^2)^2)^2)^2)^2)^2
= (((((883^2)^2)^2)^2)^2)^2
= ((((779689^2)^2)^2)^2)^2
= ((((689^2)^2)^2)^2)^2
= (((474721^2)^2)^2)^2
= (((721^2)^2)^2)^2
= ((519841^2)^2)^2
= ((841^2)^2)^2
= (707281^2)^2
= (281^2)^2
= 78961^2
= 961^2
= 923521
= 521.
Since (a%c)^(b%c)%c gives the same result, I am somewhat reassured that
this would have been a valid short-cut, but of course one good example
doesn't make a general proof.
So - what's the quick way?
--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
Gareth Taylor
Chappy <petergreg...@hotmail.com> wrote:
> Joe found this problem in one of his old maths books and gave it to
> Penny to solve. But as there was no solution in the book, Joe
> programmed his computer to find the answer and check Penny's. All
> Penny had to do was find the last three digits of:
>
> 3^123456
My first thought was to use Euler-Fermat, which reduces the problem to
finding 3^256, since phi(1000) = 400. And 3^256 can be found by
repeated squaring. But here's a much simpler way.
3^123456 = 9^61728 = (10-1)^61728
Expanding, we can ignore all the powers of 10 greater than 2, leaving:
(61728-choose-2) * 10^2 - 61728*10 + 1
We could reach for a calculator to find 61728-choose-2, but as we're
going to reduce mod 1000 at the end, and we have that 10^2 already, it's
enough to worry about its final digits. Similarly for the 61728*10.
So we get: 8*7/2 * 100 - 280 + 1 = 2521.
So the answer is 521.
Gareth
Simon Tatham
> I cheated a lot and simply used Python.
>
> >>> a = 3**123456
> >>> b = str(a)
> >>> print b[-3:]
> 521
>
> Old is right. these problems need to be updated to use 12 to 15
> digit exponents.
Even that piece of Python is inefficient. The quick way is
>>> pow(3, 123456, 1000)
521
which works internally by doing a proper modular exponentiation,
reducing mod 1000 at every stage. Much more efficient than bothering
to calculate all those upper digits that weren't going to be needed
anyway.
That function is a viable way to do modular exponentiation with both
the exponent and modulus in the region of kilobits, still in seconds
(since that's what it mostly gets used for - RSA and Diffie-Hellman
and so on).
12-15 digit modexps? _Still_ peanuts.
> Otherwise, they don't qualify as enigmas.
Only if you permit answers without working to count as solutions. A
simple way to enforce that solvers find a way that doesn't involve
Python is to consider the question to have an implicit "Prove" at
the start. Then, any answer that begins "I fed it into a computer"
attracts an immediate "fine, so now mathematically prove your
computer is right".
Of course, you could still use Python to check that your by-hand
proof did yield the right answer, or to print out reams of numbers
which you can examine to find the patterns for which you then seek
mathematical justification. But really, if it's that easy to get the
answer with a computer, then just getting the answer isn't going to
impress anyone.
--
Simon Tatham "What a caterpillar calls the end of the
<ana...@pobox.com> world, a human calls a butterfly."
Gareth Taylor
Gareth Taylor <gta...@chiark.greenend.org.uk> wrote:
> We could reach for a calculator to find 61728-choose-2, but as we're
> going to reduce mod 1000 at the end, and we have that 10^2 already,
> it's enough to worry about its final digits.
>
> So we get: 8*7/2 * 100 - 280 + 1 = 2521.
I should have written a bit more here. Because we're dividing by 2 in
the first term, we should worry about the next digit up as well. After
all, 28*27 = 756, but 18*17 = 306. The division by 2 would bring that
difference down to a digit we actually care about.
But, in this case we do have an even tens digit in 61728, so it is
enough to consider only the final digits.
Gareth
Simon Tatham
> I can't recall whether a^b % c is equivalent to (a%c)^(b%c)%c, which
> will slow me down a bit, but I am at least certain that a^b%c is
> equivalent to (a%c)^b%c, so I can use that.
As Gareth mentioned in passing in his answer, the theorem you're
looking for is the Euler-Fermat theorem (or Fermat-Euler theorem),
which states that if a and c are coprime then a^phi(a) is congruent
to 1 mod c, where phi is
http://en.wikipedia.org/wiki/Euler's_totient_function
Hence, if you're trying to raise a to some arbitrary power b mod c,
you can't get away with reducing b itself mod c, but you can reduce
b mod phi(c).
For coprime a,b, phi(ab)=phi(a)phi(b); and for any prime power,
phi(p^a) = (p-1)p^(a-1). Hence, phi(1000) = phi(2^3)*phi(5^3) =
1*2^2*4*5^2 = 400 (as Gareth also mentioned). So if your eventual
result will be reduced mod 1000, you can reduce b mod 400. (And you
are of course correct in saying you can also reduce a mod 1000.)
--
Simon Tatham "Imagine what the world would be like if
<ana...@pobox.com> there were no hypothetical situations..."
Matthew T. Russotto
Chappy <petergreg...@hotmail.com> wrote:
521. But I suppose the idea is to come up with an elegant way of
figuring it out without computing 3^123456. I just used 'bc'.
However, were I to do it the "right way", first I'd note that 3^123456
= 9^61728. I do this because there's often tricks with 9s. Then I
note that the last digit of powers of 9 alternates between 1 and 9.
That gives me the 1 So then I note 9^61728 = 81^30864. The next to
last digit of powers of 81 appears to follow a pattern 8,6,4,2,0.
That gives me the 2. Then I note that 81^30864 = 3486784401^6172 *
81^4. The third to last digit of the powers of 3486784401 follow the
pattern 4,8,2,6,0, so 3486784401^6172 ends with 801. 801 * 81^4 ends
in 521, and thus so does 3^123456. Messy but tractable even by hand.
Probably there's a better way to do it than that.
--
There's no such thing as a free lunch, but certain accounting practices can
result in a fully-depreciated one.
johnjo
> Richard Heathfield <r...@see.sig.invalid> wrote:
>
> ...> As Gareth mentioned in passing in his answer, the theorem you're
> looking for is the Euler-Fermat theorem (or Fermat-Euler theorem),
> which states that if a and c are coprime then a^phi(a) is congruent
> to 1 mod c, where phi is
> http://en.wikipedia.org/wiki/Euler's_totient_function
> Hence, if you're trying to raise a to some arbitrary power b mod c,
> you can't get away with reducing b itself mod c, but you can reduce
> b mod phi(c).
>
> For coprime a,b, phi(ab)=phi(a)phi(b); and for any prime power,
> phi(p^a) = (p-1)p^(a-1). Hence, phi(1000) = phi(2^3)*phi(5^3) =
> 1*2^2*4*5^2 = 400 (as Gareth also mentioned). So if your eventual
> result will be reduced mod 1000, you can reduce b mod 400. (And you
> are of course correct in saying you can also reduce a mod 1000.)
> --
> Simon Tatham "Imagine what the world would be like if
> <ana...@pobox.com> there were no hypothetical situations..."
I think the rationale for this puzzle was to expose those who like
numbers to the
howler: mod(a^b, n) = mod(a ^ (mod(b,n)), n) -- which it isnt
since no-one followed up with the calculation, let me.
123456 = 256 mod 400
and 256 is 2^8 and this is significant, since to calculate exponents
to a modulus you need to square and multiply in a russian style
but here all we need to do is square 3, 8 times, each mod 1000.
after 81 the "1" is invariant, and if you have at one stage three
digits
(a, b, 1) then the next stage gives (b^2 + 2a, 2b, 1) (with carry as
required)
so the second digit is a power of 2 mod 10 and we can write down 21
for the 8th stage right away
the third digit just needs to be calculated - cant see an easy way and
yes it is 5.
interestingly the first solution noted that 3^100 = 3 mod 1000 so the
answer is also 3^56
this looks easier to do, but 56 = 111000 binary and so we need to
SMSMSSS (S = square, M=multiply by 3) which is 7 operations rather
than 8, so it isnt that much easier.
HTH
JJ