Jump to content
BrainDen.com - Brain Teasers
  • 0

Inequalities for large integers


Rainman
 Share

Question

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?

  • Downvote 1
Link to comment
Share on other sites

14 answers to this question

Recommended Posts

  • 0

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.

Link to comment
Share on other sites

  • 0

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.

Link to comment
Share on other sites

  • 0

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

3^3 = 33 = 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.

Link to comment
Share on other sites

  • 0

post-52528-0-40095600-1393181367_thumb.p

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 by Rainman
Link to comment
Share on other sites

  • 0

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

Link to comment
Share on other sites

  • 0

How did you get from the last inequality to the answer? Did you assume that Tn-1 = 1000n and Wn-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 An+1 = 12An, not An+1 = An12. Similarly, for Bn = 1000^^n, we have Bn+1 = 1000Bn.
Link to comment
Share on other sites

  • 0

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 = 1212 > 4000 = 4*1000 = 4*1000^^1. Now suppose 12^^(n+1) > 4*1000^^n. Then 12^^(n+2) = 1212^^(n+1) > 124*1000^^n = (124)1000^^n > 40001000^^n = 41000^^n*10001000^^n > 4*10001000^^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.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...