Posts: 2
Threads: 1
Joined: Apr 2008
I'm calculating a pretty big number, but I'm not getting very far due to limitations in the platform  I get "infinity" when I try to calculate 3^^4 and the number is much, much, much bigger than that (in the thousands). Is there an easier way to calculate tetration?
If it would make it any easier, I only care about the last 8 digits. I thought about using decimal places, but that doesn't help  either the number is still too big or it's too small and I lose the digits I care about... actually, it gets so small, I end up with 0.
I also thought about trimming the number down to 8 digits after each exponentiation, but the first one is still too big to even get that. Of course, I completely realize this nonscientific method of calculating the result may give me the wrong answer, but I'm looking for some answer.
There has to be an easier way!
Posts: 1,395
Threads: 91
Joined: Aug 2007
04/06/2008, 08:28 PM
(This post was last modified: 04/06/2008, 08:29 PM by bo198214.)
flanakin Wrote:I'm calculating a pretty big number, but I'm not getting very far due to limitations in the platform  I get "infinity" when I try to calculate 3^^4 and the number is much, much, much bigger than that (in the thousands). Is there an easier way to calculate tetration?
Wow, thats interesting. I just tried it with maple and it also gives an overflow. Hm 3^^3=7625597484987, so we want to compute
3^7625597484987.
Quote:If it would make it any easier, I only care about the last 8 digits.
Yes, that helps.
You know that (b^n) % m = (b%m)^n, where %m is the remainder when dividing by m. So if you want to know the last 8 digits then you just need to compute %100000000.
Perhaps in the following way:
3^(3^(3^3))=3^(3^27)=((...(3^3)...)^3
you just compute the cube 27 times. But each intermediate result %100000000. I get (hopefully without errors):
00739387
Here the detailed computation:
Code: 3^3^1 % 100000000 = 27
3^3^2 % 100000000 = 19683
3^3^3 % 100000000 = 97484987
3^3^4 % 100000000 = 49892803
3^3^5 % 100000000 = 25665627
3^3^6 % 100000000 = 38846883
3^3^7 % 100000000 = 69147387
3^3^8 % 100000000 = 38089603
3^3^9 % 100000000 = 17859227
3^3^10 % 100000000 = 41930083
3^3^11 % 100000000 = 67881787
3^3^12 % 100000000 = 69710403
3^3^13 % 100000000 = 59620827
3^3^14 % 100000000 = 6549283
3^3^15 % 100000000 = 80248187
3^3^16 % 100000000 = 27475203
3^3^17 % 100000000 = 85190427
3^3^18 % 100000000 = 384483
3^3^19 % 100000000 = 5606587
3^3^20 % 100000000 = 59704003
3^3^21 % 100000000 = 56008027
3^3^22 % 100000000 = 73515683
3^3^23 % 100000000 = 60116987
3^3^24 % 100000000 = 8316803
3^3^25 % 100000000 = 16713627
3^3^26 % 100000000 = 30422883
3^3^27 % 100000000 = 739387
Quote:There has to be an easier way!
See also the thread Recurring Digits.
Posts: 509
Threads: 44
Joined: Aug 2007
I haven't read your post all the way yet. But until I do, there are three references you might be interested in:
at MROB
at Wolfram
on JSTOR
Andrew Robbins
Posts: 2
Threads: 1
Joined: Apr 2008
bo198214 Wrote:You know that (b^n) % m = (b%m)^n, where %m is the remainder when dividing by m. So if you want to know the last 8 digits then you just need to compute %100000000.
I'm not sure that will work. What you're saying is...
Code: (3^^3) % 100000000 = (3 % 100000000)^^3
7625597484987 % 100000000 = 3^^3
97484987 = 7625597484987
Am I wrong or is this what you're saying? Ultimately, the left side is what I'm trying to get to, but if I can't calculate the tetration because the number is too big, then that won't get me anywhere.
Posts: 509
Threads: 44
Joined: Aug 2007
I'm not sure what BO is saying, but I do know this, you don't need 7 trillion digits of accuracy. You just have to be clever.
Any integer can be easily calculated for smallish n, so we can start with this and find cycles in the digits. The 1place will always cycle between {1, 3, 9, 7}, and the 10place will always cycle between {0, 0, 0, 2, 8, 4, 2, 8, 6, 8, 4, 4, 4, 2, 6, 0, 2, 6, 8, 6}, which means we can know for sure that if we wanted to find the first two digits (the 1place and 10place) of then we can find that (7625597484987 mod 4 = 3) so (counting from 0) the 3rd element of {1, 3, 9, 7} is 7, so the 1place of 3tetra4 is 7. Correspondingly, (7625597484987 mod 20 = 7) so the 10place of 3tetra4 is 8. Going a little bit further, the 100place of any integer will cycle between {0, 0, 0, 0, 0, 2, 7, 1, 5, 6, 0, 1, 4, 3, 9, 9, 7, 1, 4, 4, 4, 2, 6, 8, 4, 4, 3, 9, 9, 8, 6, 9, 8, 5, 5, 7, 1, 3, 0, 2, 8, 4, 2, 6, 8, 6, 9, 7, 3, 0, 2, 7, 2, 7, 1, 5, 5, 5, 6, 0, 2, 6, 8, 4, 2, 8, 5, 5, 7, 2, 8, 5, 6, 9, 7, 3, 9, 7, 2, 8, 6, 8, 4, 2, 6, 0, 1, 3, 1, 4, 4, 3, 0, 1, 3, 1, 3, 9, 8, 6} which means that given (7625597484987 mod 100 = 87), we know that the 100place digit of 3tetra4 is going to be 3, so we know the final decimal value of 3tetra4 will be of the form ...387
I found the size of the cycles above by experimental means, I have no idea how to find the cycle size by other means. So really, what is more important than the digits themselves is finding the size (or period) of these cycles, so you can say, "I want the 10th digit of 3tetra4" and somehow know that the 10th digit is a period50000 cycle or something (I just made up the 50000). Knowing this information allows one to calculate the 10th digit of by finding the 10th digit of .
Andrew Robbins
Posts: 509
Threads: 44
Joined: Aug 2007
Nevermind, I just found it. The 1000place is a period500 cycle, which means the period is probably .
Posts: 509
Threads: 44
Joined: Aug 2007
Sorry, you wanted to know . Using this information, the last few digits are ...30214289387
Thank you for that wonderful journey in modular arithmetic!
Andrew Robbins
Posts: 509
Threads: 44
Joined: Aug 2007
I felt like calculating the last few digits of lots of simple tetrations, because now that I can do it so easily, I feel like it is my duty.
I checked the period for other bases, and for some reason it worked perfectly, I have no idea why! For example, anyone with an arbitraryarithmetic calculator (like UNIX bc, just type "echo 4^4^4  bc") can find that 4^^3 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096 so I figured I would start with this. The code I used to calculate the last few digits is very simple. In Mathematica is looks like this:
Code: PowerDigit[base_, exp_, d_] :=
With[
{ls = IntegerDigits[base^exp, 10]},
If[Length[ls] < d, 0, ls[[d]]]
]
PowerLastFew[base_, exp_, places_] :=
(* Create a list *)
Table[
(* Calculate an equivalent digit *)
PowerDigit[base,
(* using the 4 * 5^d formula in the previous post *)
Mod[exp  1, 4 * 5^d] + 1,
(* this is because of 1based lists *)
d + 1],
(* where the index 'd' goes from 'places' to 0 *)
{d, places, 0, 1}
]
Using this with base4 now, and the last few digits I got were ...49006084096 so I'm thinking that the formula works. Going on to calculate some other tetrations:
 2^^4 = 65536
 2^^5 = ...5719156736 (by naive method: same)
 2^^6 = ...7437428736 (not previously calculable)!
 3^^2 = 27
 3^^3 = 7625597484987 (by naive method: same)
 3^^4 = ...30214289387 (not previously calculable)!
 4^^2 = 256
 4^^3 = ...49006084096 (by naive method: same)
 4^^4 = ...95261392896 (not previously calculable)!
 5^^2 = 3125
 5^^3 = ...80908253125? (by naive method: ...80908203125)?
 5^^4 = ...36371253125? (not previously calculable)?
However, as you can see from base5, one of my assumptions is wrong. Something to deal with another day.
Andrew Robbins
Posts: 1,395
Threads: 91
Joined: Aug 2007
andydude Wrote:Sorry, you wanted to know . Using this information, the last few digits are ...30214289387
Slowly, slowly, this contradicts my result 00739387.
As it seemed not to be explicit enough, I reexplain:
To get 3^(3^27) % 100000000 I just take 27 times the cube:
% 100000000
then % 100000000 by the law .
We can also shorten this to 3^(3^27)=((3^19683)^19683)^19683, where 19683=3^9. Lets compute again this way:
3^19683 % 100000000 = 17859227
17859227^19683 % 100000000 = 384483
384483 ^ 19683 % 100000000 = 739387
So I come again to 3^(3^27) % 100000000 = 00739387.
Posts: 509
Threads: 44
Joined: Aug 2007
04/07/2008, 04:24 PM
(This post was last modified: 04/07/2008, 04:32 PM by andydude.)
See, I told you I was wrong. I believe that the 4*5^d assumption is where my argument breaks down.
@bo: Now that I see your proof, I cannot argue with that, you are correct.
At least we agree on ...9387
Andrew Robbins
