Calculating Tetration flanakin Junior Fellow Posts: 2 Threads: 1 Joined: Apr 2008 04/06/2008, 06:04 PM 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! bo198214 Administrator Posts: 1,389 Threads: 90 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. andydude Long Time Fellow Posts: 509 Threads: 44 Joined: Aug 2007 04/06/2008, 10:39 PM 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 flanakin Junior Fellow Posts: 2 Threads: 1 Joined: Apr 2008 04/07/2008, 01:44 AM 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. andydude Long Time Fellow Posts: 509 Threads: 44 Joined: Aug 2007 04/07/2008, 06:06 AM 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 andydude Long Time Fellow Posts: 509 Threads: 44 Joined: Aug 2007 04/07/2008, 06:14 AM Nevermind, I just found it. The 1000-place is a period-500 cycle, which means the period is probably $4\times5^d$. andydude Long Time Fellow Posts: 509 Threads: 44 Joined: Aug 2007 04/07/2008, 06:22 AM 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! Andrew Robbins andydude Long Time Fellow Posts: 509 Threads: 44 Joined: Aug 2007 04/07/2008, 08:06 AM 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 bo198214 Administrator Posts: 1,389 Threads: 90 Joined: Aug 2007 04/07/2008, 02:26 PM 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. andydude Long Time Fellow 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 « Next Oldest | Next Newest »