Ackerman function 2

Algebra Level 5

Let's reiterate about Ackerman function $\mathcal{A}$ .

$\mathcal{A}(m,n) = \begin{cases} n+1 & \text{if } m = 0 \\ \mathcal{A}(m-1, 1) & \text{if } m > 0, n = 0 \\ \mathcal{A}(m-1, \mathcal{A}(m-1, n-1)) & \text{if } m > 0, n > 0 \end{cases}$

Unlike what's suspected , this function actually doesn't grow as quickly as Ackermann function!

Let $\displaystyle S(n) = \sum_{i=0}^n \sum_{j=0}^n \mathcal{A}(i,j)$ . It turns out that $S(n)$ is a polynomial for all sufficiently large $n$ ; that is, there exists some integer $N$ and a polynomial $P$ such that for all integer $n > N$ , $S(n) = P(n)$ . The sum of the coefficients of $P(n)$ can be expressed as $\frac{a}{b}$ for some positive integers $a,b$ that are relatively prime. Compute $a+b$ .

The answer is 10.

1 solution

Pebrudal Zanu
Jan 13, 2014

Firstly we check $S(n)$ function from $n=1,2,...,11$ from this problem using this ackermann:

We get

$S(0)=1$

$S(1)=7$

$S(2)=21$

$S(3)=47$

$S(4)=88$

$S(5)=149$

$S(6)=234$

$S(7)=347$

$S(8)=492,$

$S(9)=673$

$S(10)=894$

$S(11)=1159$

Now, analyze this sequence using wolframalpha.com

This is graphic analyze:

alt text

This graphic analyze given 3rd differences. $S(3),S(4),S(4)...$ have a patern in 3 rd differences.

alt text

Now, we using mathematic for solve this series:

$\displaystyle P(n)=\frac{2}{3}n^3+2n^2+\frac{7}{3}n+4$

now, only check for $S(12)$ , and I get $S(12)=P(12)$

So the $\frac{a}{b}=P(1)=\fbox{9}$

$a=9, b=1$ and the answer is $a+b=\fbox{10}$

I am sorry, it's combinatoric problem or computer science problem??? There is no categories in my problem. Same with this

pebrudal zanu - 7 years, 5 months ago

Solve this problem for check S(1), S(2), etc. Ackerman Check

pebrudal zanu - 7 years, 4 months ago

Ackerman function 2

The answer is 10.

1 solution

0 pending reports