• 0
Sign in to follow this  
Followers 0

Inequalities for large integers

Question

Posted · Report post

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?

-1

Share this post


Link to post
Share on other sites

14 answers to this question

  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted (edited) · Report post

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
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

12^12^12 = 10^155 aprox.

-1

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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

0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.
0

Share this post


Link to post
Share on other sites
  • 0

Posted · Report post

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.

0

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  
Followers 0

  • Recently Browsing   0 members

    No registered users viewing this page.