power-tower function

[danbaron]

Below is defined a function, "power-tower".

It takes two parameters.

Examples:

(power-tower 5 3) = 5 ^ 5 ^ 5,

(power-tower 7 9) = 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7 ^ 7, etc.

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

If you look at the Ackermann function,

http://en.wikipedia.org/wiki/Ackermann_function ,

you'll see that,

(power-tower 2 4) equals A(4, 1) + 3,
(power-tower 2 5) equals A(4, 2) + 3,
(power-tower 2 6) equals A(4, 3) + 3, etc.

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

It turns out that,

(power-tower m n) = m ^ (power-tower m n-1).

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

In the REPL interactions, you can see that (power-tower 2 5) has 19729 digits.

If I try to calculate (power-tower 2 6), DrRacket crashes.

:cry: :p


' code --------------------------------------------------------------------------------------------------------------------------

#lang racket

(define (num-digits n)
(add1 (order-of-magnitude n)))

(define (power-tower m n)
(if (= n 0) 1 (expt m (power-tower m (sub1 n)))))

' REPL interactions -------------------------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.

> (power-tower 2 1)
2
> (power-tower 2 2)
4
> (power-tower 2 3)
16
> (power-tower 2 4)
65536

> (define a (power-tower 2 5))
> (num-digits a)
19729
>