Results 1 to 2 of 2

Thread: a fast growing integer function

  1. #1
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152

    a fast growing integer function

    Here is a function which is only defined for positive integers.

    It grows pretty fast.

    It's defined like this.

    f(1) = 1

    f(2) = 2^2

    f(3) = 3^3^3

    f(4) = 4^4^4^4

    etc.

    In other words,

    f(n) = n^n.., where n-1 is the number of "^"s.

    As shown below, in Racket we can calculate f(1), f(2), and f(3).

    But, we can't calculate f(4), it's too big.

    But, we can calculate the (approximate) number of digits in f(4).

    We have to use Racket's function, "log", which is for base e, i.e., the natural logarithm.

    Say for instance, we want to calculate the number of base 10 (decimal) digits in the base 10 number a^b.

    Using, the natural logarithm, we'll call it, "ln", we can do it like this.

    We say,

    y = a^b.

    Then,

    ln(y) = ln(a^b)

    ln(y) = b*ln(a)

    floor(ln(y)/ln(10) + 1) = floor(b*ln(a)/ln(10) + 1) = the number of decimal digits in y.

    We can test it.

    Say we have 3^1500.

    How many decimal digits does it contain?

    If you look below, you see that it has 716 digits, and the formula also gives 716.

    We can use the same method to calculate the number of decimal digits in f(4).

    We'll define y = a^b again.

    But in this case, a will be 4, and b will be 4^4^4.

    So, a^b will be f(4), equaling 4^4^4^4.

    Below, you see that,

    b = 4^4^4 = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096.

    Therefore, the number of digits in f(4) is,

    floor(b*ln(a)/ln(10) + 1), which is approximately equal to 8.072304726028224*10^153 base 10 digits.

    (We can't get the exact number of base 10 digits, we don't have enough floating point precision.)

    That's pretty big.

    If you could fit 100 digits per line, and 50 lines per page, then, a number with 5*10^9 digits would require one million pages to print.

    (We couldn't use the "num-digits" function, like we did for 3^1500, to find the number of decimal digits in f(4), because, that function requires that we first calculate the number, in this case, f(4), and we can't. Using the formula, we can approximate the number of digits, without knowing the number itself.)

    (Of course, you could ask, "Of what use is a function for which I can only calculate 3 values?" - I think it's a legitimate question.)

    (Actually, I think that theoretically, Racket could calculate f(4), if you had enough RAM (and time). For me, when I try to do the calculation, the IDE, DrRacket, crashes.)

    ----------------------------------------------

    Would this be a good question for an IQ test?

    What is the next number in the sequence?
    1, 4,
    7625597484987, ?

    ' code -------------------------------------------------------------------------------------------------------------------------------------------------------
    
    #lang racket
    
    (define (num-digits n)
      (add1 (order-of-magnitude n)))
    
    (define (f n)
      (define power n)
      (define (loop m)
        (cond
          ((= m n) power)
          (else
           (set! power (expt n power))
           (loop (+ m 1)))))
      (loop 1))
    
    ' REPL interactions ------------------------------------------------------------------------------------------------------------------------------------------
    
    Welcome to DrRacket, version 5.1 [3m].
    Language: racket.
    > (f 1)
    1
    > (f 2)
    4
    > (f 3)
    7625597484987
    > 
    
    > (define a 3)
    > (define b 1500)
    > (num-digits (expt a b))
    716
    > (floor (+ 1 (* b (/ (log a) (log 10)))))
    716.0
    >
     
    > (define a 4)
    > (define b (expt 4 (expt 4 4)))
    > b
    13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096
    > (floor (+ 1 (* b (/ (log a) (log 10)))))
    8.072304726028224e+153
    >
    
    Last edited by danbaron; 02-08-2011 at 11:08.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

  2. #2
    thinBasic MVPs danbaron's Avatar
    Join Date
    Jan 2010
    Location
    California
    Posts
    1,378
    Rep Power
    152
    I should have thought of this.

    We now know that the number of decimal digits in f(4) is approximately 8.072304726028224*10^153.

    So, we can approximate the approximation as 10*154 decimal digits.

    From the approximation of the number of decimal digits of f(4), we can approximate f(4), itself.

    For instance, if we have 7 decimal digits, then the number corresponding to it is, 999,999 < number < 10,000,000.

    So, we can say that the decimal number is approximately, 10^(number of decimal digits - 1).

    For f(4), we have the number of digits being in the range of 10^154.

    So, f(4) should be in the range of 10^(10^154 - 1), or 10^10^154.

    Actually, you can verify it here.

    http://www.wolframalpha.com/input/?i=4^4^4^4

    (10^2.187879.. is approximately equal to 154.)

    Last edited by danbaron; 04-08-2011 at 08:56.
    "You can't cheat an honest man. Never give a sucker an even break, or smarten up a chump." - W.C.Fields

Similar Threads

  1. Big Integer module
    By Johannes in forum BigInt module. Big Integer handling by Johannes
    Replies: 4
    Last Post: 06-03-2011, 13:41
  2. Big Integer new forum
    By ErosOlmi in forum BigInt module. Big Integer handling by Johannes
    Replies: 1
    Last Post: 27-02-2011, 20:49

Members who have read this thread: 0

There are no members to list at the moment.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •