[2015-10-14] Challenge #236 [Intermediate] Fibonacci-ish Sequence : dailyprogrammer

[2015-10-14] Challenge #236 [Intermediate] Fibonacci-ish Sequence : dailyprogrammer
The Fibonacci Sequence is a famous integer series in the field of mathematics. The sequence is recursively defined for n > 1 by the formula f(n) = f(n-1) + f(n-2). In plain english, each term in the sequence is found by adding the previous two terms together. Given the starting values of f(0) = 0 and f(1) = 1 the first ten terms of the sequence are:

0 1 1 2 3 5 8 13 21 34

We will notice however that some numbers are left out of the sequence and don't get any of the fame, 9 is an example. However, if we were to start the sequence with a different value for f(1) we will generate a new sequence of numbers. Here is the series for f(1) = 3:

0 3 3 6 9 15 24 39 102 165

We now have a sequence that contains the number 9. What joy!
Today you will write a program that will find the lowest positive integer for f(1) that will generate a Fibonacci-ish sequence containing the desired integer (let's call it x).

Input description

Your input will be a single positive integer x.
Sample Input 1: 21
Sample Input 2: 84

Output description

The sequence of integers generated using the recursion relation starting from 0 and ending at the desired integer x with the lowest value of f(1).
Sample Output 1: 0 1 1 2 3 5 8 13 21
Sample Output 2: 0 4 4 8 12 20 32 52 84

private static ArrayList<Integer> fibonacci = new ArrayList<Integer>();

public static void main(String []args){
    long timeNow = System.currentTimeMillis();
    int input = 123456789,divisor=0,index=0,fib;
    generateFibonacci((int)Math.floor(Math.sqrt(input)));
    if(fibonacci.contains(input)){
        printFibonacci(fibonacci.indexOf(input),1);
    }else{
       // we can first locate the next bigger than reverse from i-1 to 0
        for(int i=1;i<fibonacci.size();i++){
            fib=fibonacci.get(i);
            if(input%fib==0){
                divisor=input/fib;
                index=i;
            }  
        }
        printFibonacci(index,divisor);
    }
    System.out.println("The calculation took "+(System.currentTimeMillis()-timeNow)+" ms.");
}

private static void generateFibonacci(int input){
    fibonacci.add(0);
    fibonacci.add(1);
    fibonacci.add(1);
    fibonacci.add(2);
    int fib1=1, fib2=2, zw=0;
    for(int i=0; i<=input; i++){
        zw=fib1;
        fibonacci.add(fib1+fib2);
        fib1=fib2;
        fib2+=zw;
    }
}

private static void printFibonacci(int index, int multiplicator){
    for(int i=0; i<=index; i++){
        System.out.print((fibonacci.get(i)*multiplicator)+" ");
    }
    System.out.println("");
}

http://shenseye.github.io/dailyprogrammer/challenge/2015/10/14/dailyprogrammer-day-10/

From the hint i noticed that Fib-ish(i) = Fib(i)*Fib-ish(1) so i just loop from 0 to input number and use it as Fib-ish(1) and generate a Fib-ish sequence from that. If the last number of that Fib-ish sequence equal input number i will return that. Because it take 14556ms to process the 123456789, i have to reduce runtime by checking if inputNumber/Fib-ish(1) is a Fibonacci number or not. If yes then i will generate the Fib-ish sequence if no then move to another number. And now the runtime is 375ms, 40x faster pretty good right

var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

var number;

rl.question('Enter the number: ', function(answer){
    number = parseInt(answer);
    rl.close();
});

rl.on('close', function(){
    console.time('generate-fib');
    console.log(generateFibIsh(number) || "Can't generate Fibonacci-ish number from this number.");
    console.timeEnd('generate-fib');
});

function generateFib(n){
    if (n < 2)
        return n;
    return generateFib(n - 1) + generateFib(n - 2);
}

function isPerfectSquare(number) {
    return Math.sqrt(number) == Math.floor(Math.sqrt(number));
}

function isPib(number){
    return isPerfectSquare(5*number*number + 4) || isPerfectSquare(5*number*number - 4);
}

function generateFibIsh(number){
    for (var i = 1; i < number; i++) {
        if (number % i == 0 && isPib(number/i)){
            var j = 0;
            var temp = 0;
            var fibIshSeq = [];
            while (temp < number){
                temp = generateFib(j) * i;
                fibIshSeq.push(temp);
                j++;
            }
            if (fibIshSeq[fibIshSeq.length -1] == number)
                return fibIshSeq;
        }
    };
    return number == 0 ? [0] : false;
}

public static List<Integer> fibonacciIsh(int n) { List<Integer> seq = new ArrayList<>(); for(int i = 1; i <= n / 2 ; i++) { seq.add(0); seq.add(i); while(true) { seq.add(seq.get(seq.size() - 1) + seq.get(seq.size() - 2)); int x = seq.get(seq.size() - 1); if(x > n) { seq.clear(); break; } if(x == n) { return seq; } } } return Arrays.asList(0, n); }
Read full article from [2015-10-14] Challenge #236 [Intermediate] Fibonacci-ish Sequence : dailyprogrammer