PR 4 # 32 - Page 2

fetofs · 2006-07-15, 14:42

Quote:

Originally Posted by fetofs

7

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)

Duh!

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 :)

mfgoode · 2006-07-16, 16:35

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.

victor · 2006-07-16, 16:57

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

$ echo '7^7^7' | bc -lq | tail -n1
694202869611751580402966282378932933502849310357073612870132343

:)

Wacky · 2006-07-16, 17:19

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

Xyzzy · 2006-07-16, 20:47

Quote:

Originally Posted by 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.

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

Fusion_power · 2006-07-16, 23:48

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

mfgoode · 2006-07-18, 11:06

Quote:

Originally Posted by 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

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

fetofs · 2006-07-18, 17:42

Quote:

Originally Posted by Xyzzy

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

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

Richard Cameron · 2006-07-18, 21:17

Quote:

Originally Posted by mfgoode

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

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

if you calculate this table:

Quote:

Originally Posted by 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

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 penultimate 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

fetofs · 2006-07-18, 21:54

Quote:

Originally Posted by 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 penultimate 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

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

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)

mfgoode · 2006-07-19, 04:18

Quote:

Originally Posted by Richard Cameron

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

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:

Originally Posted by 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

[ "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'

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

2006-07-16, 16:35	#13
mfgoode Bronze Medalist Jan 2004 Mumbai,India 2²×3³×19 Posts	PR4#32 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.

2006-07-16, 16:57	#14
victor Oct 2005 Fribourg, Switzerlan 2²·3²·7 Posts	Do we really need a confirmation? I solved this problem the same way as Xyzzy ... $ echo '7^7^7' \| bc -lq \| tail -n1 694202869611751580402966282378932933502849310357073612870132343 :)

2006-07-16, 17:19	#15
Wacky Jun 2003 The Texas Hill Country 441₁₆ Posts	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

2006-07-16, 23:48	#17
Fusion_power Aug 2003 Snicker, AL 3BF₁₆ Posts	There is a simple pattern. 7 77=49 777=343 7777=2401 77777=16807 77777=117649 777777=823543 777777*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