← All resources

Write a program to input a number and print whether it is a Keith Number or not

A Keith number is an n-digit integer N>9 such that if a Fibonacci-like
sequence (in which each term in the sequence is the sum of the n previous terms)
is formed with the first n terms taken as the decimal digits of the number N,
then N itself occurs as a term in the sequence. For example, 197 is a Keith number
since it generates the sequence 1, 9, 7, 1+9+7=17, 9+7+17=33, 7+17+33=57, 17+33+57=107,
33+57+107=197, ... (Keith).

There is no known general technique for finding Keith numbers except by exhaustive search.
Keith numbers are much rarer than the primes, with only 84 Keith numbers with <26 digits.
The first few are 14, 19, 28, 47, 61, 75, 197, 742, 1104, 1537, 2208, 2580, 3684, 4788, 7385,
7647, 7909, ...
import java.util.Scanner;
public class keith
{
    private static Scanner sc = new Scanner(System.in);
    int n, ar[], l;
    public void input()
    {
        System.out.println("Enter a number:");
        n = sc.nextInt();
        int x = n;
        l=0;
        while(x!=0)
        {
            x = x/10;
            l++;
        }
        ar = new int[l];
    }
    public boolean check()
    {
        int sum=0, x=n, i;
        for(i=l-1;i>=0;i--)
        {
            ar[i]=x%10;
            sum = sum+x%10;
            x = x/10;
        }
        while(sum<=n)
        {
            for(i=0;i<l-1;i++)
            {
                ar[i] = ar[i+1];
            }
            ar[l-1]=sum;
            sum=0;
            for(i=0;i<l;i++)
            {
                sum = sum+ar[i];
            }
            if(sum==n)
                return true;
        }
        return false;
    }
    public static void main()
    {
        keith kt = new keith();
        kt.input();
        if(kt.check())
        {
            System.out.println("The number is a keith number.");
        }
        else
        {
            System.out.println("The number is not a keith number.");
        }
    }
}

.