a fast growing integer function

[danbaron]

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
>

[danbaron]

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