Mind Boggling Number

[jinydu]

Originally Posted by wblipp

Stirling Series

Thanks. Using the information, I derived an approximate formula for an order of magnitude approximation of n!:

n! ~ 10^(n+0.5LOGn + 0.3991 - 0.4343n), where the LOG is base 10

This means that the closes natural number factorial to the largest known prime is:

(1,125,242)! ~ 10^6320427 ~ 2^20996044

[jinydu]

Of course, even this method has its limit. My calculator overflows at roughly n = 1.02*10^98.

[mfgoode]

Originally Posted by rogue

I can't prove that, but I could show the opposite is true. 9[sup](9⁹ = 9^387420489 while ((9!)!)! = (362880!)!

9^387420489 has fewer than 387420489 digits
362880! itself has well over a million digits. That means that (326880!)! will easily exceed 387420489 digits. I doubt I need to do any math in order for that to be obvious.

Thank one and all for sending in very helpful pointers towards the eventual solution.
Since michael posed his poblem I did not realise the immensity that factorials could represent!
I tend to agree with rogue that ((9!)!)! > 9^9^9 and not vice versa
However the main issue is not to dispute over symbollism as to how best to express the largest number with only 3 digits. Madachy emphasises the word 'only' by italics. This clearly means no functions, no signs.
The main problem is how by a simple desk calculator and elementary number theory the last 10 digits of the number 9^9^9=9^387420489 could be worked out.
The method should not only be theoretically possible but practically also within finite time.
The last 10 digits are 2,627,177,289.
I am at a loss to work this out.
Perhaps as suggested by ET this could be solved by modular arithmetic.
mfgoode.

[Maybeso]

Originally Posted by mfgoode

The main problem is how by a simple desk calculator and elementary number theory the last 10 digits of the number 9^9^9=9^387420489 could be worked out.
The method should not only be theoretically possible but practically also within finite time.
The last 10 digits are 2,627,177,289.
I am at a loss to work this out.
Perhaps as suggested by ET this could be solved by modular arithmetic.

This one had me stumped for a very long time.
I filled pages with equations, and built complex spreadsheet tables.
And rewrote them, and rebuilt them.
Finally I hit on a line of reasoning that made sense, and actually worked:

9 = 10 - 1
9² = (10 - 1)² -> use binomial expansion -> = [1,-2, 1] = 10² - 2*10 + 1 = 81
9⁹ = (10 - 1)⁹ = [1,-9, 36,-84, 126,-126, 84,-36, 9,-1] -> lets check it ...
carry digits -> [1,-9+3, 6-8+1,-4+2-1, 6-2,-6+8, 4-3,-6, 9,-1] = [1,-6,-1,-3, 4, 2, 1,-6, 9,-1]
subtract ---> [10-7,10-2,10-3, 4, 2, 0,10-6, 8,10-1] = 387420489
Let n = 9⁹ = 387420489
Then 9^9[sup]9[/sup] = 9ⁿ = (10 - 1)ⁿ = [_nC_n, ..., -_nC₁₀, _nC₉, ..., -_nC₂, _nC₁, -_nC₀]
And finally, 9ⁿ mod 10¹⁰ = [_nC₉ mod 10¹⁰, _nC₈ mod 10¹⁰, ..., -_nC₂ mod 10¹⁰, 387420489, -1]
Now we can use modular arithmetic to calculate each _nC_i*10ⁱ and add:

0 =          -1
1 =  3874204890
2 = -5478931600
3 =  9038964000
4 = -4541260000
5 =  3422200000
6 = -3908000000
7 =  6520000000
8 = -3300000000
9 =  7000000000
  =  2627177289

[nfortino]

Originally Posted by mfgoode

The last 10 digits are 2,627,177,289.
I am at a loss to work this out.

Maybeso has given a solution that might actually solve your stated problem on a normal desk calculator as was the restriction. The normal method of calculating these is by using successive squaring, and modular arithmetic. The GIMPS Math Page gives an example of how do calculate 2²³ mod 47 in this way. Obviously, you are calculating 9^9[sup]9[/sup]mod 10¹⁰. The problem with this method is that it gives intermediates twenty digits long, which would give an error on a desk calculator. If all you wanted were the last 6 digits, this will work on a desk calculator in 1-3 minutes (assuming it can handle 13 digits). A computer program will do this for you in under a second.

[mfgoode]

Originally Posted by Maybeso

This one had me stumped for a very long time.
I filled pages with equations, and built complex spreadsheet tables.
And rewrote them, and rebuilt them.
Finally I hit on a line of reasoning that made sense, and actually worked:

9 = 10 - 1
9² = (10 - 1)² -> use binomial expansion -> = [1,-2, 1] = 10² - 2*10 + 1 = 81
9⁹ = (10 - 1)⁹ = [1,-9, 36,-84, 126,-126, 84,-36, 9,-1] -> lets check it ...
carry digits -> [1,-9+3, 6-8+1,-4+2-1, 6-2,-6+8, 4-3,-6, 9,-1] = [1,-6,-1,-3, 4, 2, 1,-6, 9,-1]
subtract ---> [10-7,10-2,10-3, 4, 2, 0,10-6, 8,10-1] = 387420489
Let n = 9⁹ = 387420489







Then 9^9[sup]9[/sup] = 9ⁿ = (10 - 1)ⁿ = [_nC_n, ..., -_nC₁₀, _nC₉, ..., -_nC₂, _nC₁, -_nC₀]
And finally, 9ⁿ mod 10¹⁰ = [_nC₉ mod 10¹⁰, _nC₈ mod 10¹⁰, ..., -_nC₂ mod 10¹⁰, 387420489, -1]
Now we can use modular arithmetic to calculate each _nC_i*10ⁱ and add:

0 =          -1
1 =  3874204890
2 = -5478931600
3 =  9038964000
4 = -4541260000
5 =  3422200000
6 = -3908000000
7 =  6520000000
8 = -3300000000
9 =  7000000000
  =  2627177289

Maybeso you are A genious! The first time I am veiwing a solution that ma
kes sense and very elegantly excuted too.
Please await my next post to crack out a much larger number which author Madachy gives the answer too. Your theory and method we will be able to test out.
Mfgoode

[mfgoode]

Originally Posted by nfortino

Maybeso has given a solution that might actually solve your stated problem on a normal desk calculator as was the restriction. The normal method of calculating these is by using successive squaring, and modular arithmetic. The GIMPS Math Page gives an example of how do calculate 2²³ mod 47 in this way. Obviously, you are calculating 9^9[sup]9[/sup]mod 10¹⁰. The problem with this method is that it gives intermediates twenty digits long, which would give an error on a desk calculator. If all you wanted were the last 6 digits, this will work on a desk calculator in 1-3 minutes (assuming it can handle 13 digits). A computer program will do this for you in under a second.

Thank you for pointing the way! I will certainly follow up the example.
The term [sup ] seems to be a standard. Kindly tell me what it means tho I have an inkling but am not sure.
Mfgoode.

[Maybeso]

Originally Posted by mfgoode

Thank you for pointing the way! I will certainly follow up the example.
The term [sup ] seems to be a standard. Kindly tell me what it means tho I have an inkling but am not sure.
Mfgoode.

[sup ] is superscript and [sub ] is subscript.

nfortino,

Actually, I used my PC calculator to verify that the process was workable. It will go up to 2¹⁰⁸ or 10³¹ before showing 1.622...813e+32. Since my method involves multiplying 2+3 8 digit #'s, 4 7, 5 6, ..., and 9 2 digit #'s, it provides some precision advantage over the successive squaring method.
(Yes, I knew about that, I just wanted to solve the puzzle ... because it was there.)

To get the answers I posted, I used zzmath in XL. Without that, I would have to use two 5 digit columns to represent each number. Which means a two step multiply, plus the mod-with-carry. Duplicating that on a desk calculator would be difficult. A calculator with two memories might make it possible - but then the squaring method would still be better.

[Maybeso]

mfgoode,
I finally got it that some browsers can't show superscript and subscript. It only took me a day.

I guess my post would get pretty mangled if the [ sup] and [ sub] were broken.
So here is the first part using x^n and n_C_k formats:

9 = 10 - 1
9^2 = (10 - 1)^2 -> use binomial expansion -> = [1,-2, 1] = 10^2 - 2*10 + 1 = 81
9^9 = (10 - 1)^9 = [1,-9, 36,-84, 126,-126, 84,-36, 9,-1] -> lets check it ...
carry digits -> [1,-9+3, 6-8+1,-4+2-1, 6-2,-6+8, 4-3,-6, 9,-1] = [1,-6,-1,-3, 4, 2, 1,-6, 9,-1]
subtract ---> [10-7,10-2,10-3, 4, 2, 0,10-6, 8,10-1] = 387420489
Let n = 9^9 = 387420489
Then 9^9^9 = 9^n = (10 - 1)^n = [n_C_n, ..., -n_C_10, n_C_9, ..., -n_C_2, n_C_1, -n_C_0]
And finally, 9^n mod 10^10 = [n_C_9 mod 10^10, n_C_8 mod 10^10, ..., -n_C_2 mod 10^10, 387420489, -1]
Now we can use modular arithmetic to calculate each n_C_i*10^i and add: ...

[Maybeso]

How to use a desk calculator to find the last 10 digits of 9^9^9.

n = 9^9 = 387420489, so we'll be working with [387420481..387420489].
I use fractions instead of /100000. I subtract leading digits to preserve trailing digits.
{123456} shows the display, bold shows our goal. d8 = 8 digits, d7 = 7 digits, ...

• n_C_0 = 1
• n_C_1 = 387420489
• n_C_2 = 387420489 x 387420488 /2, d8 -> (874 20489)(937 10244)
  874 x 1.0244 + 937 x 2.0489 = {2815.1449} - 2815 = MS
  1.0244 x .20489 = {0.209889316} + MR = {0.354789316}
• n_C_3 = n_C_2 x 387420487 /3, d7
  54789316 / 3 = {18263105.33} -> prev. mods deleted 2e8, add for divisibility.
  254789316 / 3 = {84929772} -> (49 29772)(74 20487)
  49 x 2.0487 + 74 x 2.9772 = {320.6991} - 320 = MS
  2.0487 x .29772 = {0.609938964} + MR = {1.309038964}
• n_C_4 = 9038964 x 387420486 /4, d6 -> (2 59741)(4 20486)
  2 x 2.0486 + 4 x 5.9741 = {27.9936} - 27 = MS
  2.0486 x .59741 = {1.223854126} + MR = {2.217454126}
• n_C_5 = 454126 x 387420485 /5, d5 ->
  54126 x 84097 = {45518 34222}
• n_C_6 = 34222 x 387420484 /6, d4 ->
  4222 /6 = {703.666} -> +2e4 for divisibility.
  24222 /6 = {4037} -> 4037 x 0484 = {1953908}
• n_C_7 = 3908 x 387420483 /7, d3 ->
  908 /7 = {129.7142857} -> +5e3 for divisibility.
  5908 /7 = 844 -> 844 x 483 = {407652}
• n_C_8 = 652 x 387420482 /8, d2 -> 52 x 82 /8 = {533}
• n_C_9 = 33 x 387420481 /9, d1 -> 33 x 81 /9 = {297}
• ----------------------------------
  -1 + 387420489 e1 - 54789316 e2 + 9038964 e3 - 454126 e4 + 34222 e5
  - 3908 e6 + 652 e7 - 33 e8 + 7 e9 = {1262717729} - 1e10 = {2627177289}

[Cyclamen Persicum]

has anyone ever heard about RSA? This is a simple modular power.
The fifty last digits:

9^(9^9) mod 10^50 =
74036682906190174923494324178799359681422627177289