Fibonacci Modified:How to fix this algorithm?

Question

I have this problem in front of me and I can't figure out how to solve it. It's about the series 0,1,1,2,5,29,866... (Every number besides the first two is the sum of the squares of the previous two numbers (2^2+5^2=29)). In the first part I had to write an algorithm (Not a native speaker so I don't really know the terminology) that would receive a place in the series and return it's value (6 returned 29) This is how I wrote it:

public static int mod(int n)
{
    if (n==1)
        return 0;
    if (n==2)
        return 1;
    else
        return (int)(Math.pow(mod(n-1), 2))+(int)(Math.pow(mod(n-2), 2));
}

However, now I need that the algorithm will receive a number and return the total sum up to it in the series (6- 29+5+2+1+1+0=38) I have no idea how to do this, I am trying but I am really unable to understand recursion so far, even if I wrote something right, how can I check it to be sure? And how generally to reach the right algorithm?

Using any extra parameters is forbidden.

Thanks in advance!

Answer 1

We want:

mod(1) = 0
mod(2) = 0+1
mod(3) = 0+1+1
mod(4) = 0+1+1+2
mod(5) = 0+1+1+2+5
mod(6) = 0+1+1+2+5+29

and we know that each term is defined as something like:

   2^2+5^2=29

So to work out mod(7) we need to add the next term in the sequence x to mod(6).

Now we can work out the term using mod:

 x = term(5)^2 + term(6)^2
 term(5) = mod(5) - mod(4)
 term(6) = mod(6) - mod(5)
 x = (mod(5)-mod(4))^2 + (mod(6)-mod(5))^2

So we can work out mod(7) by evaluating mod(4),mod(5),mod(6) and combining the results.

Of course, this is going to be incredibly inefficient unless you memoize the function!

Example Python code:

def f(n):
    if n<=0:
        return 0
    if n==1:
        return 1
    a=f(n-1)
    b=f(n-2)
    c=f(n-3)
    return a+(a-b)**2+(b-c)**2

for n in range(10):
    print f(n)

prints:

0
1
2
4
9
38
904
751701
563697636866
317754178345850590849300

Answer 2

How about this? :)

class Main {

  public static void main(String[] args) {
    final int N = 6; // Your number here.
    System.out.println(result(N));
  }

  private static long result(final int n) {
    if (n == 0) {
      return 0;
    } else {
      return element(n) + result(n - 1);
    }
  }

  private static long element(final int n) {
    if (n == 1) {
      return 0L;
    } else if (n == 2) {
      return 1L;
    } else {
      return sqr(element(n - 2)) + sqr(element(n - 1));
    }
  }

  private static long sqr(final long x) {
    return x * x;
  }
}

Here is the idea that separate function (element) is responsible for finding n-th element in the sequence, and result is responsible for summing them up. Most probably there is a more efficient solution though. However, there is only one parameter.