[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
