PR 4 # 32
 

What is the rightmost digit of 7[sup]7[sup]7[/sup][/sup] ?

[QUOTE=Wacky]What is the rightmost digit of 7[sup]7[sup]7[/sup][/sup] ?[/QUOTE]
[spoiler]1

Proof:

7^2 = 49 == -1 mod 10
Therefore, 7^6 = (7^2)^3 == (-1)^3 == -1 mod 10

Therefore 7^7 == -3 == 4 mod 10.

Therefore 7^(7^7) == 7^4 == (7^2)^2 == (-1)^2 == 1 mod 10

[/spoiler]

[spoiler] 3. To get answer, all you have to do is calculate mod 10. [/spoiler]

I was going to be the first to answer this, the 300 sec posting time limit let Xilman answer first.

Whoa there!

Order(7,10) = 4

Therefor 7^(7^7) = 7^(Mod(7^7,4)) (mod 10).

Paul,

"No cigar". Try again.

[QUOTE=Wacky]What is the rightmost digit of 7[sup]7[sup]7[/sup][/sup] ?[/QUOTE]

[spoiler]7[/spoiler]

[spoiler]So, we have 7*7*7*7 (49 times) . Since a*b (mod 10) = (a mod 10)*(b mod 10), we can reduce the multipliers as we go through. This is a sequence, but we must find it first. We can know for sure it's smaller than 11! :)
Exponent = 2 mod 4 7*7 = 9 (mod 10)
Exponent = 3 mod 4 9*7 = 3 (mod 10).
Exponent = 0 mod 4 3 * 7 = 1 (mod 10)
Exponent = 1 mod 4 1 * 7 = 7 (mod 10).
We have returned to our original point. Therefore every exponent that is -2 mod 4 equals 9 mod 10, and so on. Since 49 == 1 (mod 4), the result is congruent to 7 (mod 10)[/spoiler]

[spoiler]3?[/spoiler]

I have ten possibilities:
0, 1, 2, 3, 4, 5, 6, 7, 8, and 9

Please justify why you choose a particular one / (exclude some of them)

[quote=Wacky]Please justify why you choose a particular one / (exclude some of them)[/quote] [spoiler]$ echo '7^7^7' | bc | tail --bytes=2
3[/spoiler]

:whistle:

Yes, the answer is 3.

7^7=823543=4*k+3, so
7^(7^7)=7^823543=7^(4*k+3)=343*2401^k==3*1==3 mod 10.

extra credit?
 

since 7^4 = 2401 and so ==1 mod 100, the penultimate digit must be 4.

[QUOTE=fetofs][spoiler]7[/spoiler]

[spoiler]So, we have 7*7*7*7 (49 times) . Since a*b (mod 10) = (a mod 10)*(b mod 10), we can reduce the multipliers as we go through. This is a sequence, but we must find it first. We can know for sure it's smaller than 11! :)
Exponent = 2 mod 4 7*7 = 9 (mod 10)
Exponent = 3 mod 4 9*7 = 3 (mod 10).
Exponent = 0 mod 4 3 * 7 = 1 (mod 10)
Exponent = 1 mod 4 1 * 7 = 7 (mod 10).
We have returned to our original point. Therefore every exponent that is -2 mod 4 equals 9 mod 10, and so on. Since 49 == 1 (mod 4), the result is congruent to 7 (mod 10)[/spoiler][/QUOTE]

Duh!

[spoiler]7^7 is not 49!
7^7 mod 4 = 3^3 mod 4 = 27 mod 4 = 3

Therefore the result is congruent to 3 (mod 10) according to my table. At least I didn't have to do any particularly large calculations. That was a major overlook :)[/spoiler]

PR4#32
 

:smile:
Well a full day has passed and Wacky has not okayed any of the answers so I take it that they are all wrong so far.
Even a school boy knows that the multiples of 7 are cyclic viz:9,3,1,7 and no others.of the ten digits.
Since 3 , 1 , 7 have all been given the only one left that can be correct is 9.
Simple deduction!
Mally. :coffee:

Do we really need a confirmation?
I solved this problem the same way as Xyzzy ...

$ echo '7^7^7' | bc -lq | tail -n1
69420286961175158040296628237893293350284931035707361287013234[U]3[/U]

:)

Mally,

I fear that you are reading something into my non-response that should not be inferred.

As others have pointed out, the last digit is "3".
Obviously, I discount the methodology of those who used a computer to calculate the digit as opposed to those who used the cyclic nature of the expansion to deduce the answer without actually expanding the entire expression.

Richard

[quote=Wacky]Obviously, I discount the methodology of those who used a computer to calculate the digit as opposed to those who used the cyclic nature of the expansion to deduce the answer without actually expanding the entire expression.[/quote]I'd like to understand how everyone found the last digit without a computer. I only answered it that way in desperation.

:innocent:

There is a simple pattern.

7
7*7=49
7*7*7=343
7*7*7*7=2401
7*7*7*7*7=16807
7*7*7*7*7=117649
7*7*7*7*7*7=823543
7*7*7*7*7*7*7=4764801

Notice the pattern of ending digits. Its 7,9,3,1,7,9,3,1 which repeats as long as you choose to continue multiplying by 7. Once you know the group order, its easy to extract the exact result using mod.

There is a similar type of pattern associated with Mersenne numbers. Anyone want to take a whack at explaining what it is and why its useless for finding mersenne primes?

Fusion

simple pattern
 

[QUOTE=Fusion_power]There is a simple pattern.

7
7*7=49
7*7*7=343
7*7*7*7=2401
7*7*7*7*7=16807
7*7*7*7*7=117649
7*7*7*7*7*7=823543
7*7*7*7*7*7*7=4764801

Notice the pattern of ending digits. Its 7,9,3,1,7,9,3,1 which repeats as long as you choose to continue multiplying by 7. Once you know the group order, its easy to extract the exact result using mod.

There is a similar type of pattern associated with Mersenne numbers. Anyone want to take a whack at explaining what it is and why its useless for finding mersenne primes?

Fusion[/QUOTE]
:smile:
There is a simpler way based on your method.
Just multiply the last digits and theres no need to work the whole number out.

For instance 7x7 = 49
last digit 9x7 = #3
3x7 = #1
1x7 =# 7
7x7 =# 7

So we are back to 7x7 for the last digit and the cycle is 9,3,1,7. repeating itself.

Mally :coffee:

[QUOTE=Xyzzy]I'd like to understand how everyone found the last digit without a computer. I only answered it that way in desperation.

:innocent:[/QUOTE]

Highlighting the spoilers would help. If you didn't want to, Axn gave a good clue in his post.

[QUOTE=mfgoode]:smile:
There is a simpler way based on your method.
Just multiply the last digits and theres no need to work the whole number out.

For instance 7x7 = 49
last digit 9x7 = #3
3x7 = #1
1x7 =# 7
7x7 =# 7

So we are back to 7x7 for the last digit and the cycle is 9,3,1,7. repeating itself.

Mally :coffee:[/QUOTE]


Its often easy to see a better solution after the fact!

if you calculate this table:
[QUOTE=fusion]
There is a simple pattern.

7
7*7=49
7*7*7=343
7*7*7*7=2401
7*7*7*7*7=16807
7*7*7*7*7*7=117649
7*7*7*7*7*7*7=823543

[/QUOTE]

you can read off everything you need to find the solution. And as you say, you can then see that calculating all the digits was unnecessary. But you do need to see what the [B]penultimate[/B] digit is (or else observe that is even - actually it is always 0 or 4); but how would you know this without calculating it?

Richard

[QUOTE=Richard Cameron]Its often easy to see a better solution after the fact!
you can read off everything you need to find the solution. And as you say, you can then see that calculating all the digits was unnecessary. But you do need to see what the [B]penultimate[/B] digit is (or else observe that is even - actually it is always 0 or 4); but how would you know this without calculating it?

Richard[/QUOTE]

Actually, I don't think anyone prior to Fusion calculated the digits. The penultimate digit observation is interesting though, how did you calculate it? Without calculating the digits with modular arithmetic, I would say that

[spoiler]
7*7 = 49 (2 mod 4)
49*7 = 43 (3 mod 4)
43*7 = 01 (0 mod 4)
1*7 = 7 (1 mod 4)

As 7^7 = 3 mod 4
7^7^7 = 43 mod 100

We could go on forever, but it takes more and more work as we go...

7*7=49
49*7=343
343*7=401
401*7=807
807*7=649
649*7=543
543*7=801
801*7=607
607*7=249
249*7=743
743*7=201
201*7=407
407*7=849
849*7=943
943*7=601
601*7=207
207*7=449
449*7=143
143*7=1
1*7=7

As 7^7 = 3 (mod 20),
7^7^7 is congruent to 343 (mod 1000).
If we had the order prior to the calculation we would have known that
7^7^7 (mod 1000) = 7^(7^7 mod 20) (mod 1000)

[/spoiler]

PR4#32
 

[QUOTE=Richard Cameron]Its often easy to see a better solution after the fact! [/QUOTE]
:huh:
Evidently you have not read my post No. 13 where I clearly mention the cycle of digits repeating much before Fusion Power used brute force when it was not necessary. It appears to me that FP merely amplified my rule after reading it
Hey Richard please give credit when it is deserved

[QUOTE=you can read off everything you need to find the solution. And as you say, you can then see that calculating all the digits was unnecessary. But you do need to see what the [B]penultimate[/B] digit is (or else observe that is even - actually it is always 0 or 4); but how would you know this without calculating it?

Richard[/QUOTE]

[ "you can read off everything you need to find the solution"] AMBIGUOUS!

["but how would you know this without calculating it?]

Simple just multiply the last two digits and add the 'carry over digit' :flex:

However I must commend you for your astute observation on the penultimate digit for which my many thanks.

From Fusion Power's ready table I observe that the digits 0 and 4 do not always alternate but its always one of them

Mally :coffee:

Mally,

I posted the table in direct response to Xyzzy's query. I was not answering Wacky's original question. That had been adequately answered already.

What happened to "Its better to give than to receive"?

Fusion

[QUOTE=mfgoode]:huh:
Evidently you have not read my post No. 13 where I clearly mention the cycle of digits repeating much before Fusion Power used brute force when it was not necessary. It appears to me that FP merely amplified my rule after reading it
Hey Richard please give credit when it is deserved
[/QUOTE]

sorry: I did read it and I did appreciate it. But in post 13 you did not give the correct answer!
[QUOTE=me, mainly]
[ "you can read off everything you need to find the solution"] AMBIGUOUS!
[/QUOTE]
the details of the method of solution had been given before so I didn't go through it again: in order to identify the last digit of the original number you need the exponent mod 4 so you need the last two digits of the exponent. And you pointed this out too, thank you.

[QUOTE=Mally]From Fusion Power's ready table I observe that the digits 0 and 4 do not always alternate but its always one of them
[/QUOTE]

I used Fusion Power's table because it was convenient and available. And from there you can see that the pattern for two digits is 07,49,43,01, so the penultimate digit goes 0,0,4,4.

If you extend that table, you will see that the third last digit has a period of 20, the fourth last 100, and -I was sensing a pattern by this time- the fifth last 500.

I don't know how exceptional 7 is in this respect, I think some digits have maximal periods.


Richard

PR4#32
 

[QUOTE=Fusion_power]Mally,

I posted the table in direct response to Xyzzy's query. I was not answering Wacky's original question. That had been adequately answered already.

What happened to "Its better to give than to receive"?

Fusion[/QUOTE]
:smile:
Fusion: Yes I certainly believe that phrase and practice it too
Bu here it is slightly out of context though.
So here lets say "Forgive us our trespasses as we forgive them that trespass against us"
Regards,
Mally:coffee:

Pattern
 

K[QUOTE=Richard Cameron]sorry: I did read it and I did appreciate it. But in post 13 you did not give the correct answer!

the details of the method of solution had been given before so I didn't go through it again: in order to identify the last digit of the original number you need the exponent mod 4 so you need the last two digits of the exponent. And you pointed this out too, thank you.



I used Fusion Power's table because it was convenient and available. And from there you can see that the pattern for two digits is 07,49,43,01, so the penultimate digit goes 0,0,4,4.

If you extend that table, you will see that the third last digit has a period of 20, the fourth last 100, and -I was sensing a pattern by this time- the fifth last 500.

I don't know how exceptional 7 is in this respect, I think some digits have maximal periods.


Richard[/QUOTE]
:smile: Excellent observation Richard.
The reciprical of 7 is 142857 repeating indefinitely.
You may try 1/13 ,1/17, 1/19.
See if you can crack out a pattern for the bigger primes

Mally:coffee:

[QUOTE=Richard Cameron]

If you extend that table, you will see that the third last digit has a period of 20, the fourth last 100, and -I was sensing a pattern by this time- the fifth last 500.

I don't know how exceptional 7 is in this respect, I think some digits have maximal periods.
[/QUOTE]

Do you feel sad by knowing that the sixth last has a period of 5000?

[QUOTE=fetofs]Do you feel sad by knowing that the sixth last has a period of 5000?[/QUOTE]

yes, devastated. My great mathematical theory is shown to be flawed.
Oh well, back to proving the Riemann Hypothesis for me.

Richard

PR4#32
 

[QUOTE=Richard Cameron]!
#~
the details of the method of solution had been given before so I didn't go through it again: in order to identify the last digit of the original number you need the exponent mod 4 so you need the last two digits of the exponent. And you pointed this out too, thank you.

Richard[/QUOTE]

Sorry Richard but I cant understand your terminology.
Kindly be so kind as to explain this to me?

mally :coffee:

[QUOTE=mfgoode]Sorry Richard but I cant understand your terminology.
Kindly be so kind as to explain this to me?

mally :coffee:[/QUOTE]

by the original number I meant 7^7^7; by the exponent i meant 7^7. I hope the rest makes sense.



I've thought about this a little more and if you look back at R Gerbicz's elegently concise solution and modify it a little, an even shorter solution becomes apparent:

[QUOTE=R Gerbicz]
Yes, the answer is 3.

7^7=823543=4*k+3, so
7^(7^7)=7^823543=7^(4*k+3)=343*2401^k==3*1==3 mod 10.[/QUOTE]

If you start from
7^7 = 7^3 * 7^4 = 343 * 2401
Its obvious without actually multiplying this out that the last two digits of 7^7 are 43 and so 7^(7^7) will be 7^(4k+3) == 343 mod 10.


Richard

[QUOTE=Richard Cameron]


I've thought about this a little more and if you look back at R Gerbicz's elegently concise solution and modify it a little, an even shorter solution becomes apparent:



Richard[/QUOTE]

There is even a shorter solution. I will give a hint: 7 = -1 mod 4.

Try 7^(7^(7^(7^(7^(7^7))))) mod 10 ..........

[QUOTE=R.D. Silverman]There is even a shorter solution. I will give a hint: 7 = -1 mod 4.

Try 7^(7^(7^(7^(7^(7^7))))) mod 10 ..........[/QUOTE]

[spoiler]Since we want the solution x mod 10, we have to work both mod 2 and mod 5.

The first case (mod 2) is simple because we have:

x = 7^(7^(7^(7^(7^(7^7))))) = 1^(...) = 1 (mod 2)

The second case (mod 5) can be worked as follows:

From Fermat's Little theorem we have:

x = 7^(7^(7^(7^(7^(7^7))))) = 2^a (mod 5)

where a = 7^(7^(7^(7^(7^7)))) (mod 4)

so a = 3^(7^(7^(7^(7^7)))) (mod 4)

a = 3^odd = 3 (mod 4)

So x = 2^3 = 8 = 3 (mod 5)

Since x = 1 (mod 2) and x = 3 (mod 5), we must have [b]x = 3 (mod 10)[/b]

Notice that it does not matter the number of 7s.[/spoiler]

[QUOTE=alpertron][spoiler]Since we want the solution x mod 10, we have to work both mod 2 and mod 5.

The first case (mod 2) is simple because we have:

x = 7^(7^(7^(7^(7^(7^7))))) = 1^(...) = 1 (mod 2)

The second case (mod 5) can be worked as follows:

From Fermat's Little theorem we have:

x = 7^(7^(7^(7^(7^(7^7))))) = 2^a (mod 5)

where a = 7^(7^(7^(7^(7^7)))) (mod 4)

so a = 3^(7^(7^(7^(7^7)))) (mod 4)

a = 3^odd = 3 (mod 4)

So x = 2^3 = 8 = 3 (mod 5)

Since x = 1 (mod 2) and x = 3 (mod 5), we must have [b]x = 3 (mod 10)[/b]

Notice that it does not matter the number of 7s.[/spoiler][/QUOTE]


While you got the right answer, you ignored the hint. There is a
MUCH easier way to do this.

[QUOTE=R.D. Silverman]While you got the right answer, you ignored the hint. There is a
MUCH easier way to do this.[/QUOTE]
Well, the derivation above was easy.

It is more interesting to find the last 7 digits of 7^(7^(7^(7^(7^(7^7))))) which is not too difficult.

[QUOTE=alpertron]It is more interesting to find the last 7 digits of 7^(7^(7^(7^(7^(7^7))))) which is not too difficult.[/QUOTE]

[spoiler]Let x = 7^(7^(7^(7^(7^(7^7)))))
Let a = 7^(7^(7^(7^(7^7))))
Let b = 7^(7^(7^(7^7)))
Let c = 7^(7^(7^7))
Let d = 7^(7^7)
Let e = 7^7

x = 7^a = 7^(a mod phi(10000000)) (mod 10000000)
x = 7^a = 7^(a mod 4000000) (mod 10000000)

a = 7^b = 7^(b mod phi(4000000)) (mod 4000000)
a = 7^b = 7^(b mod 1600000) (mod 4000000)

b = 7^c = 7^(c mod phi(1600000)) (mod 1600000)
b = 7^c = 7^(c mod 640000) (mod 1600000)

c = 7^d = 7^(d mod phi(640000)) (mod 640000)
c = 7^d = 7^(d mod 256000) (mod 640000)

d = 7^e = 7^(e mod phi(256000)) (mod 256000)
d = 7^e = 7^(e mod 102400) (mod 256000)

Working backwards:

e = 7^7 = 4343 (mod 102400)
d = 7^4343 = 244343 (mod 256000)
c = 7^244343 = 372343 (mod 640000)
b = 7^372343 = 372343 (mod 1600000)
a = 7^372343 = 1172343 (mod 4000000)
x = 7^1172343 = 5172343 (mod 10000000)

So the last 7 digits of the power is 5172343.[/spoiler]