How to calculate this sequence iteratively?

Question

I want calculate this sequence iteratively.

A(0,j)=j+1
A(i,0)=A(i-1,0)
A(i,j)=A(i-1,A(i,j-1))

This is my try

    public function calculsuite1Action($i,$j)
{
    $A = array();
    for ($k = 0; $k <= $i * $i * $i + $j; $k++) {
        $A[0][$k] = $k + 1;
    }
    for ($c = 1; $c <= $i; $c++) {
        for ($k = 0; $k <= $i * $i * $i + $j - $c; $k++) {
            if ($k == 0) {
                $A[$c][$k] = $A[$c - 1][1];
            } else {
                $A[$c][$k] = $A[$c - 1][$A[$c][$k - 1]];
            }
            if ($c == $i && $k == $j) {
                return $A[$i][$j];
            }

        }
    }
}

I'm trying to find a solution using PHP or any other programming language. How can I do that?

score 2 · Answer 1 · edited Apr 28 '19 at 11:16

2

I have tried looking for a pattern for the first few entries. If I haven´t done any mistakes the sequence is pretty simple. It boils down to

A(i, j) = j+1

Just used this JavaScript program to verify I didn't make any mistakes

for (i = 0; i < 5; i++){
  for (j = 0; j < 5; j++){
    console.log("A("+i+", "+j+") = "+calc(i,j));
  }
}

function calc(i, j){
  if(i==0)
    return j+1;
  else if(j == 0)
    return calc(i-1, 0);
  else
    return calc(i-1, calc(i, j-1));
}

edited Apr 28 '19 at 11:16

Zoe

27,060
21
118
148

answered Jan 04 '18 at 15:05

SaiBot

3,595
1
13
19

A(3,1)=13 not 2 ! – Naruto Uzumaki Jan 04 '18 at 15:19
1

Can you explain how you came to that conclusion? I somehow begin to believe you are trolling since you told @Philipp Maurer that A(3,1) = 5 – SaiBot Jan 04 '18 at 15:21
@NarutoUzumaki added a code snippet, where you can verify A(3,1) = 2 – SaiBot Jan 04 '18 at 15:30
@NarutoUzumaki glad that I could help. If you think the answer is correct you might want to consider [accepting it](https://meta.stackexchange.com/a/5235). – SaiBot Jan 04 '18 at 16:01
how do you find the solution ? – Naruto Uzumaki Jan 06 '18 at 12:17
I just looked at the first couple of results and saw the pattern. Proofing it, should be easily possible by induction. – SaiBot Jan 06 '18 at 17:16
you don't have a justification ? – Naruto Uzumaki Jan 07 '18 at 14:33
It's a straightforward proof, by induction on j (with both the base case and induction case proven by a very simple induction on i). – Paul Hankin Feb 11 '18 at 13:59

גלעד ברקן · Answer 2 · 2018-01-04T15:49:52.050

Here's a stack implementation. Please see here for an explanation of how I converted the recursion.

JavaScript code:

/**
* A(0,j)=j+1
* A(i,0)=A(i-1,0)
* A(i,j)=A(i-1,A(i,j-1))
***/

// Recursive
function f(i,j){
  if (i == 0) return j+1
  else if (j == 0) return f(i-1,0)
  else return f(i-1,f(i,j-1))
}

// Iterative
function iterative(_i,_j){
  let result = undefined;
  let stack = [[f, [_i, _j]]];

  function g(i){
    let Aij_1 = result;
    stack.push([f, [i-1, Aij_1]]);
  }

  function f(i, j){
    if (!i){
        result = j + 1;
        
    } else if (!j){
        stack.push([f, [i-1, 0]]);
        
    } else {
        stack.push([g, [i]]);
        stack.push([f, [i, j-1]]);
    }
  }

  while (stack.length){
    [func, params] = stack.pop();
    func.apply(func, params);
  }

  return result;
}

for (let i=0; i<11; i++){
  for (let j=0; j<11; j++)
    // Log both iterative and recursive results for comparison
    console.log(
      '(' + i + ', ' + j + ') => ' +
      JSON.stringify([iterative(i,j), f(i,j)])
    );
}

How to calculate this sequence iteratively?

2 Answers2

Linked