Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Large numbers

  1. Jun 19, 2013 #1

    Mentallic

    User Avatar
    Homework Helper

    I'd like to discuss numbers at "orders of magnitude" around Graham's number.

    If any readers haven't heard of this number but are curious to follow, you'll first need to understand Knuth's[/PLAIN] [Broken] up arrow notation and then read up on Graham's[/PLAIN] [Broken] number.

    My question is, since Graham's number (##G=g_{64}##) is essentially a very large power tower of 3's, can we replace the 3's with a larger (but relatively small) number such that we get a new number ##H=h_{63}>G##. So for example, let the larger number be a googol, so
    $$\newcommand\up{\mathbin{\uparrow}}$$
    $$g_0=h_0=4$$
    and
    $$g_{n}=3\hspace{1 mm}\underbrace{\up\dots\up}_{g_{n-1}} \hspace{2 mm}3,\hspace{5 mm}n>0$$
    $$h_{n}=10^{100}\hspace{1 mm}\underbrace{\up\dots\up}_{h_{n-1}} \hspace{2 mm}10^{100},\hspace{5 mm}n>0$$

    So clearly ##h_{63}>g_{63}## but can we relate ##h_{63}## to ##g_{64}##? The number of up arrows are by far the most powerful operator in ##a\up\dots\up b##, so I'd guess ##g_{64}## is larger, but I can't prove it.

    A naturally extension to the question could also be what size the number needs to be such that ##h_{63}>g_{64}##.
     
    Last edited by a moderator: May 6, 2017
  2. jcsd
  3. Jun 20, 2013 #2
    Okay, for convenience I will use ##a c## for ##a\underbrace{\uparrow\dots\uparrow}_{b} c## when there are a lot of up arrows.

    I will start by proving that ##3 \uparrow\uparrow b+3 > 10^{100} \uparrow\uparrow b## for all ##b \geq 1##. I will in fact prove the stronger statement
    ##3 \uparrow\uparrow b+3 > (10^{100} \uparrow\uparrow b)^2##, using induction.

    Case ##b=1##: ##3 \uparrow\uparrow 4 = 3^{3^{27}} > 3^{600} = 27^{200} > 10^{200} = (10^{100} \uparrow\uparrow 1)^2##.

    Now assume the statement is true for b, and prove it for b+1.

    $$3 \uparrow\uparrow b+4 = 3^{3 \uparrow\uparrow b+3} > 3^{(10^{100} \uparrow\uparrow b)^2} = (3^{10^{100} \uparrow\uparrow b})^{10^{100} \uparrow\uparrow b} \geq (3^{10 ^ {100}})^{10^{100} \uparrow\uparrow b} $$
    $$> (10^{10^{99}})^{10^{100} \uparrow\uparrow b} > (10^{200})^{10^{100} \uparrow\uparrow b} = ((10^{100})^{10^{100} \uparrow\uparrow b})^2 = (10^{100} \uparrow\uparrow b+1)^2.$$

    Next, we will prove that ##3 \uparrow\uparrow\uparrow b+2 > (10^{100} \uparrow\uparrow\uparrow b)+4## for ##b \geq 1##. We will use induction again.

    Case ##b = 1##:
    ##3 \uparrow\uparrow\uparrow 3 \geq 3 \uparrow\uparrow 4 > 10 ^ {100}##

    Next, we assume the statement for b, and prove it for b+1.

    $$3\uparrow\uparrow\uparrow b+3 = 3 \uparrow\uparrow (3\uparrow\uparrow\uparrow b+2) > 3 \uparrow\uparrow ((10^{100} \uparrow\uparrow\uparrow b) + 4) \text{(by induction)}$$
    $$ > 10^{100} \uparrow\uparrow (10^{100} \uparrow\uparrow\uparrow b+1) \text{(by the previous proposition)} \geq (10^{100}\uparrow\uparrow\uparrow b+1) + 4.$$

    Next, we have ##3 [a] b+1 > (10^{100} [a] b) + 3## for ##a \geq 4, b \geq 1##.
    We will prove it using double induction and a and b.

    Case ##b=1##:
    $$3 [a] 2 \geq 3 [4] 2 = 3 \uparrow\uparrow\uparrow 3 > 3 \uparrow\uparrow 4 > 10^{100}.$$

    Next assume that statement is true for (4, b), and we prove it for (4, b+1).
    $$3 [4] b+2 = 3 [3] (3 [4] b+1) > 3 [3] ((10^{100} [4] b) + 3) > 10 ^ {100} [3] ((10^{100} [4] b) + 1) $$
    $$> 10^{100} [3] (10^{100} [4] b) + 3 = (10^{100} [4] b) + 3.$$

    Finally we prove the statement for (a+1, b+1), given that it is true for (a+1, b) and (a, x) for any x.

    $$3 [a+1] b+2 = 3 [a] (3 [a+1] b+1) > 3 [a] ((10^{100} [a+1] b) + 3) > 10 ^ {100} [a] ((10^{100} [a+1] b) + 2) $$
    $$> 10 ^{100} [a] (10^{100} [a+1] b) + 3 = 10 ^{100} [a+1] (b+1) + 3.$$

    Next, we have ##3 [a+1]3 > 10^{100} [a] 10^{100}## for ##a \geq 3##.
    Indeed, ##3 [a+1] 3 = 3 [a] (3 [a] 3) > 3 [a] (10^{100} + 2) > 10^{100} [a] 10^{100}##.

    So ##h_n < g_{n+1}##, since ##h_0 = 4 < 3 [4] 3 = g_1##, and if ##h_n < g_{n+1}##, then
    $$h_{n+1} = 10^{100} [h(n)] 10^{100} < 3 [h(n)+1] 3 \leq 3[g_{n+1}] 3 = g_{n+2}$$.
     
    Last edited: Jun 20, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Large numbers
  1. Factoring a large number (Replies: 11)

  2. Dividing large numbers (Replies: 7)

Loading...