Easiest way to verify whether a number is Fibonacci or not?

A number N is fibonacci number if 5N²+4 (or) 5N²-4 is a perfect square.

A smart way to check a number to be a perfect square is apply sqrt(N) % 1 == 0

Proof is here on page 418: http://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf
Source: http://www.hackerrank.com/blog

What happens when you enter an URL in a browser

I found this article very informative. So I am sharing it 🙂

http://igoro.com/archive/what-really-happens-when-you-navigate-to-a-url/

InterviewStreet Equations Solution

Find the no of positive integral solutions for the equations (1/x) + (1/y) = 1/N! (read 1 by n factorial) Print a single integer which is the no of positive integral solutions modulo 1000007.

Input:
N
Output:
Number of positive integral solutions for (x,y) modulo 1000007
Constraints:
1 <= N <= 10^6
Sample Input00:
1
Sample Output00:
1

Sample Input01:

32327

Sample Output 01:

656502

Sample Input02:

40921

Sample Output 02:

686720

My approach to the problem:

No of solutions for the equation XY=N! is
(e₁+1)(e₂+1)………..(e_n+1)
where e₁,e₂…e_n are multiplicities of Prime Numbers below N.

For Ex: XY=4!
No of primes below 4= {2,3}
4!= 24= 2³*3¹
where 3 and 1 are prime multiplicities of 24.
so applying the formula (3+1)*(1+1)=8 (no of factors of 24={1,2,3,4,6,8,12,24}.

Now the equation 1⁄x+1⁄y= N! can be transformed into
(x-N!)(y-N!)=N!²
Hence No. of solutions of the above equation is
(2e₁+1)(2e₂+1)………..(2e_n+1)

Hence to solve the problem:
1) First find out the primes less than N
2) Find the prime multiplicities
3) Apply the formula.

Any Suggestions are welcome 🙂

Java code for the problem

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {
	public static int getMultiplicity(int i,int N){
		int duplicate=N,multiplictiy=0;
		while(duplicate!=0){
			multiplictiy+=duplicate/i;
			duplicate=duplicate/i;
		}
		return (2*multiplictiy+1);
	}
	public static void computeNoOfFactors(int multiplicity[]){
		BigInteger result= new BigInteger("1");
		String str[]= new String[multiplicity.length];
		Arrays.fill(str," ");
		for(int i=2;i<multiplicity.length;i++){
			str[i]= Integer.toString(multiplicity[i]);
		}
		BigInteger b[]= new BigInteger[multiplicity.length];
		Arrays.fill(b,new BigInteger("1"));
		for(int i=2;i<str.length;i++){
			b[i]= new BigInteger(str[i]);
		}
		for( int i=2;i<b.length;i++){
			if(b[i].equals(new BigInteger("-1")));
			else{
				result= result.multiply(b[i]).mod(new BigInteger("1000007"));
		
			}
		}
		System.out.println(result.mod(new BigInteger("1000007")));
	}
	public static void computePrimeMultiplicity(int primes[],int N){
		int multiplicity[]= new int[primes.length];
		Arrays.fill(multiplicity,-1);
		for(int i=2;i<primes.length;i++){
			if(primes[i]==1){
				multiplicity[i]= getMultiplicity(i,N);
			}
		}

		computeNoOfFactors(multiplicity);
	}
	public static int[] generatePrimes(int N){
		int primes[]= new int[N+1];
		//int primes[]= new int[((int)Math.ceil(N/2))+1];
		Arrays.fill(primes,1);
		for(int i=2;i*i<=N;i++){
			if(primes[i]==1){
				for(int j=i;j*i<=N;j++){
					primes[j*i]=0;
				}
			}
		}

		return primes;
	}
	public static void main(String args[]) throws Exception{
		Scanner sc= new Scanner(System.in);
		int N=sc.nextInt();
		int primes[]=generatePrimes(N);
		computePrimeMultiplicity(primes,N);
	}
}