Jump to content
BrainDen.com - Brain Teasers
  • 0
Sign in to follow this  
Rainman

Inequalities for large integers

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

Share this post


Link to post
Share on other sites

14 answers to this question

  • 0

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

Let a

n = 12^^(n+1) and bn = 1000^^n. How does a1 compare to b1? How can you express an+1 and bn+1 in terms of an and bn?

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)?

Share this post


Link to post
Share on other sites
  • 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.

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


Link to post
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

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
Share on other sites
  • 0

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.

Share this post


Link to post
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

Share this post


Link to post
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.

Share this post


Link to post
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this  

  • Recently Browsing   0 members

    No registered users viewing this page.

×