ITRIX12E - R Numbers
R - Numbers
R-numbers are numbers which have the property that they do not have the digit '0 ' and sum of every two adjacent digits of the number is prime. 123 is a R-number because 1+2 =3 and 2+3 =5 and 3 , 5 are primes.
How many R-numbers can be formed with atmost length N?
i.e R-numbers of length 1 + R-numbers of length 2 + R-numbers of length 3+....... R-numbers of length N
Length of a number = Number of digits in the number
Only four single digit numbers are R-numbers which are nothing but single digit primes 2,3,5,7
The first line of the input file contains T which denotes the number of Test cases.The next T lines contain an integer N <= 10^9
Print the numbers of R-numbers modulo 1000000007. [10^9+7];
Sample Input: 2 1 2 Sample Output: 4 33
Used G.P. sum with common ratio in the form of matrix.
I can find it for particular N in log N
Amazing problem , solved using linear recurrence relation :)
ONE HELL OF A QUESTION
(correct) answers for a few values of n:
NICE QUESTION LEARNT A LOT
@david : wrong
Sorry - my bad and WA at the time.
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
Finally I got AC...