Numerological Fibonacci sequence

Numerological Fibonacci sequence

Numerology

Increasingly popular today, numerology is an ancient tradition that attracted attention of civilization’s greatest minds. There is evidence that numerology was in use in China, Greece, Rome, and Egypt for a long time before Pythagoras, who is generally considered to be the “father” of numerology.     Numerology, not unlike astrology and other esoteric subjects, has experienced a revival in recent years. Many modern numerologists have adopted the original Pythagorean system. It is a simple system that assigns a number value (from one to nine) to every letter of the alphabet: A is 1, B is 2, and so on. According to traditional summation, we add for example, 7+8=15. In numerology, this is not enough: we use a further method of summation known as the “Fadic” system, or “natural summation.” This simply means we sum two or more digits together until we arrive at a single digit. For our example, for the number 78, 7 and 8 add up to 15, however, in numerology we sum 1+5, for a final answer 6.

Fibonacci numbers

The Fibonacci numbers are the sequence of numbers defined by the linear recurrence equation

With f(n) = f(n-1) + f(n-2) and f(1) = f(2) = 1. First few numbers of this sequence are 1, 1, 2, 3, 5, 8, 13, 21, 34.

Problem

In this problem you will have to find out numerological values of the Fibonacci numbers (<= 1000000) . For example

F₁₅ = 610, k(F₁₅) = 6 + 1 + 0 = 7

F₂₂ = 17711, k(F₂₂) = 1 + 7 + 7 + 1 + 1 = 17 = 1 + 7 = 8

Input

First line of input: T (Number of test cases). In next T lines, each have one integer N <= 1000000.

Output

The numerological value of F_N.

Sample Input

5

1

2

5

100

1000

Sample Output

1

1

5

3

6

Idea Behind This Problem

Its a periodic sequence. And here period number is 24.

C Solution
Idea 1:(Without knowing period number)

#include <stdio.h>

int numer(int n){
 int sum;

 while(n > 9){
  sum = 0;
  while(n){
   sum += n % 10;
   n /= 10;
  }
  n = sum;
 }

 return n;
}
int f[1000001];
int main(){
 int i,n,t;

 f[1] = f[2] = 1;
 for(i = 3; i <= 1000000; i++){
  f[i] = numer(f[i-1] + f[i-2]);
 }

 //freopen("nfsIn.txt","r",stdin);
 //freopen("nfsOut.txt","w",stdout);

 scanf("%d",&t);
 while(t--){
  scanf("%d",&n);
  printf("%d\n",f[n]);
 }

 return 0;
}

Idea 2:(If period number can be found)

#include <stdio.h>

int numer(int n){
 int sum;

 while(n > 9){
  sum = 0;
  while(n){
   sum += n % 10;
   n /= 10;
  }
  n = sum;
 }

 return n;
}

int main(){
 int i,f[25],n,t;

 f[1] = f[2] = 1;
 for(i = 3; i <= 24; i++){
  f[i] = numer(f[i-1] + f[i-2]);
 }
 f[0] = f[24];

 //freopen("nfsIn.txt","r",stdin);
 //freopen("nfsOut.txt","w",stdout);

 scanf("%d",&t);
 while(t--){
  scanf("%d",&n);
  printf("%d\n",f[n % 24]);
 }

 return 0;
}