FUSC - Obfuscated Property

Consider the sequence:

    0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4...

This sequence is defined recursively by the formula:

  • f(2n) = f(n)
  • f(2n+1) = f(n) + f(n+1)

with the initial values f(0) = 0 and f(1) = 1

In 1982, Dijkstra called this sequence fusc because it possesses a curious obfuscated property: if the sum of two indices, n and m, is a power of 2, then f(n) and f(m) are coprime.

The sequence of the ratios of two consecutive elements un = f(n) / f(n+1) runs through all non-negative rational numbers (in reduced form) just once!

    0, 1, 1/2, 2, 1/3, 3/2, 2/3, 3, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4 ...

Moreover, if the terms are written as an array:

    1
    1, 2
    1, 3, 2, 3
    1, 4, 3, 5, 2, 5, 3, 4
    1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5
    1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6

then the sum of the k-th row is 3k-1, each column is an arithmetic progression, and the steps are nothing but the original sequence!

In this problem, given n, you have to find max{f(i); 0 <= i <= n)}

Input

One single line contains n (0 <= n <= 1015).

Output

One single line contains max{f(i); 0 <= i <= n)}.

Example

Input:
10

Output:
4

Added by:Jimmy
Date:2006-12-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET

hide comments
2022-02-18 08:02:19
Can someone please tell me what's wrong with my code it' s showing wrong after test case 5
2022-02-18 08:01:33
10 PRINT "I CAN'T READ"
20 GOTO 10

Last edit: 2022-02-20 14:51:24
2021-09-05 09:20:25
@akash1203 for a value of n and i such that 0<=i<=n since f(i) is not linear you have to find the greatest value that occurs.
2021-08-30 19:39:27
can anyone explain me this question actually i am not getting this question??????
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.