FUSC - Obfuscated Property

no tags 

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

hide comments
Dawid Chmura: 2023-06-07 11:56:08

Please a more test case.

chienstar: 2022-10-14 12:19:57

the first thing if you see the terms you could see max always in the last 2 rows and each row if element 1 is omitted, it is always symmetric so from the given number n i calculate the log 2 of n .after that i use the floor function to calculate the integer nearest log2(n) so let call the variable floor_n = floor(log2(n)), n_start = pow(2, floor_n) - 1 is 2^m - 1, n_end = pow(2, floor_n+1) -1 is 2^(m+1) - 1 and n_end2 = n_start + (2^(m+1)-2^m)/2. So i check if n_end- n <= n -n_start i find max by looping from n_start to n_end2 else i find max by looping from n_start to n. For Example The given number n = 50 => log2(n) = 5,6 => m = floor(n) = 5 , 2^m-1 = 31 < n=50 < 2^(m+1)-1=63 => n_start = 31, n_end = 63, n_end2 = 47 => n - start = 19, n_end - n = 13 so i will find max of f(i) with i from 31 to 47 ( 5, 1,6,5,9,4,11,7,10,3,11,8,13,5,12,7,9) is 13 but i still get the TLE (=.=). Can anyone publish some other idea.

chienstar: 2022-10-13 20:06:56

did anyone find max(f(i)) by not using loop ? my code always reach the TLE in test case 5

fjkexgnffhwihp: 2022-07-01 17:00:58

a clearer definition of this sequence:
f(0) = 0
f(1) = 1
f(n) = f(n/2) if n is even
f(n) = f((n-1)/2) + f((n+1)/2) if n is odd

Last edit: 2022-07-02 11:18:58
louis_22: 2022-06-30 00:01:35

I have no idea what I’m doing

louis_22: 2022-06-30 00:00:31

I need help

maestro092: 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

maestro092: 2022-02-18 08:01:33

10 PRINT "I CAN'T READ"
20 GOTO 10

Last edit: 2022-02-20 14:51:24
crookedriff: 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.

akash1203: 2021-08-30 19:39:27

can anyone explain me this question actually i am not getting this question??????


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