// Nacci.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* These number series are a generalization of the Fibonacci
   sequence:

    For n = 2, the sequence has initial values [1, 1]
    and F_k^2 = F_{k-1}^2 + F_{k-2}^2

    For n = 3, the 'tribonacci' sequence has initial values [1, 1, 2] 
    and F_k^3 = F_{k-1}^3 + F_{k-2}^3 + F_{k-3}^3

    For n = 4, the 'tetranacci' sequence has initial values [1, 1, 2, 4] 
    and F_k^4 = F_{k-1}^4 + F_{k-2}^4 + F_{k-3}^4 + F_{k-4}^4

    ...

    In general, the Fibonacci n-step sequence is F_k^n.
    The initial values are the first n values of the (n-1)'th 
    sequence F_k^{n-1}
    The k'th value of this n'th sequence is:
       F_k^n = \sum_{i=1}^{(n)} F_{k-i}^{(n)}

   https://mathworld.wolfram.com/Fibonaccin-StepNumber.html
and
   https://rosettacode.org/wiki/Fibonacci_n-step_number_sequences


   The easiest way of coding these sequences is by building 
   an n-step sequence using the n-1 sequence, i.e. by using
   recursion. In other words, this code does not use Nut.fib().
*/


public class Nacci
{

  public static void main(String[] args)
  {
    // generate 9 nacci sequences
    for (int n = 2; n <= 10; n++) {
      System.out.print("nacci(" + n + "):");
      for (int value : fib(n, 15))   // each seq has 15 values
        System.out.print(" " + value);
      System.out.println();
    }
  } /* main */



  private static int[] fib(int n, int numVals)
  // generate the n'th nacci sequence, made up of numVals values
  {
    if (n < 2)
      throw new IllegalArgumentException(
                         "Fib value must be at least 2");

    if (n == 2) 
      return fibonacci( new int[]{1, 1}, numVals);
         // the starting values for the standard fib sequence
    else  // n > 2
      return fibonacci( fib(n-1, n), numVals);
  } /* fib */


  private static int[] fibonacci(int[] svs, int numVals)
  // generate numVals starting values
  {
    int[] startValues = new int[numVals];
    int oldSize = svs.length;
    System.arraycopy(svs, 0, startValues, 0, oldSize);
           // copy existing starting values to a new array

    // calculate additional starting values
    for (int i = oldSize; i < numVals; i++)
      for (int j = 1; j <= oldSize; j++)
        startValues[i] += startValues[i - j];  // sum of prev vals
    return startValues;
  } /* fibonacci */


}  // end of Nacci class