Inequalities for large integers

[Rainman]

These problems use Knuth's up-arrow notation (http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation), with ^ being the up-arrow.

1. Find the smallest value for n, such that 1000^^n > 12^^(n+1).

2. We define the sequence g, by assigning g(1) = 3^^^^3, and g(n+1) = 3^^^...^3, where the number of up-arrows is g(n). A famously large number is Graham's number = g(64). Which is larger, Graham's number or 2^^^...^2, where the number of up-arrows is Graham's number?

[bonanova]

Aaaargh. Up arrows are famously non intuitive to think about. I'm thinking nonetheless.

[Rainman]

The answers may be counter-intuitive (translation: I'm a tricky bastard)

Let a

_n = 12^^(n+1) and b_n = 1000^^n. How does a₁ compare to b₁? How can you express a_n+1 and b_n+1 in terms of a_n and b_n?

Let F(n) = 2^^^...^2, where the number of up arrows is n. How do you define F(n+1) in terms of F(n)?

[phil1882]

second one seems fairly straight forward, 2^...^2 where the number of up arrows is grams number is definitely bigger than grams number itself.

we can discover that fairly easily. let 3^^^3 = 7 trillion aprox.

2^..^2 where the number of up arrows is 7 trillion is definitely bigger.

first one is slightly harder, but 1 definitely fits the bill.

[phil1882]

i like the think of up arrow notation in the following way.

1 + 1 +1 = 3

3 ++ 3 = 3 +(3 +3) = 9

3+++ 3 = 3++(3++3) = 3++9 = 27

3++++ 3 = 3 +++ (3 +++ 3) = 3 +++ 27 = 3^27 = 7.6 trillion.

with two we have...

1 +1 = 2

2 ++ 2 = 2 +2 = 4

2 +++2 = 2 ++(2 ++2) = 2 ++ 4 = 8

2 ++++ 2 = 2 +++ (2 +++2) = 2+++8 = 2^8 = 256.

[phil1882]

whoops....

1+1 = 2

2++2 = 2 +2 = 4

2+++2 = 2++2 = 4

2++++2 = 2+++2 = 4

etc.

so.... 2^^...2 grams number is 4.

[Rainman]

Actually, just one up-arrow is the same as exponentiation.

3^3 = 3³ = 27

3^^3 = 3^(3^3) = 3^27 = 7625597484987

3^^^3 = 3^^(3^^3) = 3^^(7625597484987) = 3^3^3^3^3...^3, where the number of threes is 7,625,597,484,987.

So 12^^2 = 12^12 = 8916100448256, which is much larger than 1000^^1 = 1000. The inequality doesn't hold for n=1.

Generally, 1000^^n is 1000^1000^1000^...^1000, where the number of 1000s is n.

You solved puzzle 2 2^^^....^2 always equals 4, no matter how many up-arrows you have.

[Rainman]

Intuition works differently for different people, but my intuition says the right hand side of the image wins out as n grows larger. The advantage of having a bigger exponent seems more important than the advantage of having one more exponent. However, the actual answer might be counter-intuitive.

Edited February 23, 2014 by Rainman

[phil1882]

hmmm.

so let me start over.

we want the smallest value n such that

1000^^n > 12^^(n+1)

or where 1000^1000^1000^...n > 12^12^12^12..^n+1

log(1000^1000) = 3000

log(12^12^12) = 12*log(12^12) = 155 aprox

so i'd say 2.

[Rainman]

12^12^12 should be interpreted as 12^(12^12) rather than (12^12)^12. So log(12^12^12) = log(12^(12^12)) = (12^12)*log(12) ~ 9 600 000 000 000.

[phil1882]

12^12^12 = 10^155 aprox.

[Rainman]

Yeah, and a googolplex = 10^10^100 = 10^1000...

[phil1882]

okay i see. i was entering it in to the calc wrong

consider the two functions

Tn = log((Tn-1)^1000) where T1 = 1000

and

Wn = log((Wn-1)^12) where W1 = 12^12

we are interested to know, when if ever Tn exceeds Wn.

by setting the inequality to each other, we have...

1000*log(Tn-1) >12^12*log(Wn-1)

log(Tn-1) >12^12/1000 *log(Wn-1)

so i'd say the smallest n is 3,207,362,798

[Rainman]

How did you get from the last inequality to the answer? Did you assume that T_n-1 = 1000ⁿ and W_n-1 = 12?

You might be on the right track with your idea, but you got the recursive functions wrong from the start.

Consider the sequence A

_n = 12^^(n+1). We would have A_n+1 = 12^A_n, not A_n+1 = A_n¹². Similarly, for B_n = 1000^^n, we have B_n+1 = 1000^B_n.

[Rainman]

It was a trick question: there is no n, such that 1000^^n > 12^^(n+1). I claim that 12^^(n+1) > 4*1000^^n for all n in Z

⁺.

Proof: for n = 1, certainly 12^^2 = 12¹² > 4000 = 4*1000 = 4*1000^^1. Now suppose 12^^(n+1) > 4*1000^^n. Then 12^^(n+2) = 12^{12^^(n+1)} > 12^{4*1000^^n} = (12⁴)^{1000^^n} > 4000^{1000^^n} = 4^{1000^^n}*1000^{1000^^n} > 4*1000^{1000^^n} = 4*1000^^(n+1). So the claim holds for n = 1, and if it holds for n = p, then it also holds for n = p+1. Hence it holds for all n.

Furthermore, the ratio 12^^(n+1)/1000^^n tends to infinity as n tends to infinity. Proving this is left as an exercise to the reader.