Calculating Tetration
#1
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 non-scientific 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!
#2
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!

Smile

See also the thread Recurring Digits.
#3
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
#4
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.
#5
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 \( 3^n \) can be easily calculated for small-ish n, so we can start with this and find cycles in the digits. The 1-place will always cycle between {1, 3, 9, 7}, and the 10-place 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 1-place and 10-place) of \( {}^{4}{3} = 3^{3^{27}} \) then we can find that (7625597484987 mod 4 = 3) so (counting from 0) the 3-rd element of {1, 3, 9, 7} is 7, so the 1-place of 3-tetra-4 is 7. Correspondingly, (7625597484987 mod 20 = 7) so the 10-place of 3-tetra-4 is 8. Going a little bit further, the 100-place of any integer \( 3^n \) 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 100-place digit of 3-tetra-4 is going to be 3, so we know the final decimal value of 3-tetra-4 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 3-tetra-4" and somehow know that the 10th digit is a period-50000 cycle or something (I just made up the 50000). Knowing this information allows one to calculate the 10th digit of \( 3^n \) by finding the 10th digit of \( 3^{(n\text{ mod }50000)} \).

Andrew Robbins
#6
Nevermind, I just found it. The 1000-place is a period-500 cycle, which means the period is probably \( 4\times5^d \).
#7
Sorry, you wanted to know \( {}^{4}{3}\text{ mod } 10^8 \). Using this information, the last few digits are ...30214289387

Thank you for that wonderful journey in modular arithmetic! Smile

Andrew Robbins
#8
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 \( 4 \times 5^d \) period for other bases, and for some reason it worked perfectly, I have no idea why! For example, anyone with an arbitrary-arithmetic 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 1-based lists *)
      d + 1],
      
    (* where the index 'd' goes from 'places' to 0 *)
    {d, places, 0, -1}
  ]

Using this with base-4 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 base-5, one of my assumptions is wrong. Something to deal with another day.

Andrew Robbins
#9
andydude Wrote:Sorry, you wanted to know \( {}^{4}{3}\text{ mod } 10^8 \). 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:
\( a_0 = 3 \)
\( a_{n+1} = {a_n} ^ 3 \) % 100000000
then \( a_{27}=3^{3^{27}} \) % 100000000 by the law \( (a\%m)^b=a^b\% m \).

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.
#10
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


Possibly Related Threads…
Thread Author Replies Views Last Post
  Calculating the residues of \(\beta\); Laurent series; and Mittag-Leffler JmsNxn 0 1,295 10/29/2021, 11:44 PM
Last Post: JmsNxn



Users browsing this thread: 1 Guest(s)