Ackerman function

[Stewbond]

Consider this super-exponential recursive function:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include <stdio.h> int ack(int m, int n) { if (m == 0) return n+1; if (n == 0) return ack( m - 1, 1 ); return ack( m - 1, ack( m, n - 1 ) ); } int main() { for (int i = 0; i < 6; ++i) for (int j = 0; j < 6; ++j) printf("ack(%d,%d) = %d\n", i, j, ack(i,j)); return 0; }

ack(0,0) = 1 ack(0,1) = 2 ack(0,2) = 3 ack(0,3) = 4 ack(0,4) = 5 ack(0,5) = 6 ack(1,0) = 2 ack(1,1) = 3 ack(1,2) = 4 ack(1,3) = 5 ack(1,4) = 6 ack(1,5) = 7 ack(2,0) = 3 ack(2,1) = 5 ack(2,2) = 7 ack(2,3) = 9 ack(2,4) = 11 ack(2,5) = 13 ack(3,0) = 5 ack(3,1) = 13 ack(3,2) = 29 ack(3,3) = 61 ack(3,4) = 125 ack(3,5) = 253 ack(4,0) = 13 ack(4,1) = 65533 Segmentation fault (core dumped)

Can anyone compute ack(4,2)?

[Ispil]

Yeah, that would be quite the large number: It is 2^(ack(4,1)+3) - 3. So... 2^65536 - 3. Ah, the wonderful world of tetration (ack(4,n) is tetration), how its values are always so large that they can't even be written out due to their size.

[ResidentBiscuit]

Ooh I had never heard of tetration before, though I had thought about it before.

[helios]

There's also the hyperoperator:
hyper(0, a, b) = b + 1
hyper(1, a, b) = a + b
hyper(2, a, b) = a * b
hyper(3, a, b) = a ^ b
hyper(n, a, b) = hyper(n - 1, a, hyper(n, a, b - 1))
Therefore:
g(1) = hyper(6, 3, 3)
g(n) = hyper(g(n - 1), 3, 3)
G = g(64)

[Ispil]

Yeah, if you want to get into the actual "what does a mathematician do" kind of math, look into tetration- you'll see that there is a lot of undiscovered stuff that needs looking into.

[Stewbond]

Is that a gogolplex?

[helios]

Way, way, way bigger.

[13bSLyTq]

gogolplex is 10^{10^100}where as this is 2^{65536 - 3} which is WAY WAY WAY WAY WAY WAY WAY SUPER SUPER SUPER GIANT compared to the tiny gogolplex in this case.

[Disch]

OrionMaster wrote:

gogolplex is 1010^100where as this is 265536 - 3 which is WAY WAY WAY WAY WAY WAY WAY SUPER SUPER SUPER GIANT compared to the tiny gogolplex in this case.

Errr....

wouldn't 10^10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 be more than 2^65533? Like a lot more?

Or am I misunderstanding your numbers.

[NoXzema]

>.>

[13bSLyTq]

Sorry I mean 3 *2^65536 and then the next would take 2 ^ 2^65536 * 3 which is (4,3) and then the next would be recurisve so by the next few numbers it would start to show up but you are right.

However Its the minutes and if you see it in terms of seconds it is is 2^65536 * 60 which is a long time so overall by (4,3) it would be 60 * 2 ^ 2^65536 * 3

which will start to get really large by then you start seeing it but yea you are right but if you measure it in nanoseconds it would be larger than googlplex easily but we are not so I guess you are correct.

[a k n]

I came across the same problem in brilliant.org , I hope you are not cheating !!
Moreover , you can easily compute the last few digits by applying mod 10^(digits required) on the sub steps...
Alternatively you can find the 2^(exponent everyone provided here/on Wikipedia) by using mod as above and in the result subtract 1.

Disch wrote:

wouldn't 10^10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 be more than 2^65533? Like a lot more?

Intuitively and Mathematically , you are correct.
Intuitive result goes without saying ...
Lets see about the Math part.
log₁₀(10ⁿ) = n ;
log₁₀(2^m) = log₁₀(10^m)*(log₁₀(2))^-1
so , log₁₀(2^m) = m*3.32192809489...
We can write , log(googolplex) = googol ;
and log₁₀(2⁶⁵⁵³³) = 665533*3.321... ~ 2210852.77077
Clearly 2210852.77077 << googol.

Hoping , I got the math right.