Robodevil likes to do some mathematics between rehearsals of his orchestra.
Today he invented devilish sequence No. 1729:
- x0 = 0,
- x1 = 1,
- xn = (xn − 1 + xn − 2) / 2.
For example, x10
= 0.666015625. Robodevil became interested
at once how many sixes there were at the beginning of an arbitrary xn
In 6 nanoseconds, he had a formula. Can you do the same?
You are given an integer n; 2 ≤ n ≤ 100000.
Output the number of sixes at the beginning of xn in decimal notation.
Problem Author: Alexander Ipatov
Problem Source: IX USU Open Personal Contest (March 1, 2008)