This problem is the harder version of Problem 61015
given a sequence of numbers arranged in the following order:
A=0,1,3,4,9,10,12,13,27,28,30,31,36,37,......
Write a function that takes n as a parameter, we expect the output to be the nth number of this sequence
note: with this plus version you have to find the Nth number with extremely large N. Because the result can be extremely large, we will take the modulus of the nth number by 1e9+7
eg:
n=5
--> output=9
Solution Stats
Problem Comments
6 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers34
Suggested Problems
More from this Author4
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
In Tests, how do the correct answers be possible?
The sequence works by blocks s < n < s + 2^k, with y(s+1) = 3^k <= y(n), as seen in Problem 61018.
However, y_correct < 3^k = 1162261467 if k = 19.
Please, what am I doing wrong?
@Luisa be sure to return the result modulo 1e9+7.
Thank you, @Christian Schröder. I have one more question.
Why the values of y_correct do not follow an increasing order, since the sequence is increasing?
Thank you in advance.
@Luisa you're welcome! And same reason: the sequence itself is increasing, but mod(..., 1e9+7) is not monotone. For instance, the correct answer for n=1e10 is 5790371712137536, which gives 671604939 modulo 1e9+7; for n=1e11 the correct answer is 174397460347225327 (larger), which gives 126443114 modulo 1e9+7, and that just so happens to be smaller than 671604939.
Of course, @Christian Schröder. I forgot the note!
Thank you so much.
You're welcome, Luisa!