It’s easy to get the last nine digits(just mod 10^9) and we can get the first nine digits using general fomula of Fibonacci numbers: $ f_n = \frac{(\frac{\sqrt{5} + 1}{2})^n + (\frac{\sqrt{5}-1}{2})^n}{\sqrt{5}} $. It is evident that the term $\frac{\sqrt{5} - 1}{2}$ is smaller than 1.0 (more exactly, 0.6xxxxx) and it can be ignored when n is large enough(e.g. n = 10^5). Then we compute $\log_{10}^{f_n}$ and discard it’s integeral part. Now you need figure out the dramatic mothod of calculating the first nine(or eight, any number you want) digits of $f_n$ yourself.

It is sad that I am a brute forces :-( My code runs in about 60 seconds. I know brute force is not a good way to solve this problem but it needs some time for me to figure out the brilliant solution.

My code runs in 1.57 seconds. First of all, it’s envident that the number of admissible numbers are few and in order to generate all of them, only primes under sqrt(10^9) are need. Then, we calculate contribution of each prime. As we all known, pseudo-Fortunate numbers are non-decreasing for sorted admissible numbers. BTW, primesieve library is used in order to iterate all primes under 10^9. It feels like cheating :-(

Although this is a simple problem associated with dynamic programming with digits, but I spend about 1h to code it…It’s really an annoying thing for me when it needs count integers under some constraints like this one. Anyway, I worked it out and I’ll be more careful and patient next time when encounter this type of problems.

Got accepted with simple dynamic programming and my code runs in nearly 0 seconds. It helps a lot using fractions in Python. I first try to use C++ but unfortunately numbers may too large to hold by long long.

This is a quite simple problem about probability but it costs me 20 minutes to varify the correctness of my method. Fortunately, I got Accepted at the first try. BTW, my code runs in about 0 seconds(cuz time complexity is O(32 * 32)). As described, every integer in this sequence are independent and their possibility to be a specific integer are equal. Assuming that we already collect i bits out of 32 bits then we take another integer from the sequence and how many different kind of bits we can get now. It’s simple to figure out the fomula.

As we only need calculate the number of divisors for integers 1 < n < 10^7, It says possible to bruteforce whose running time is $O(n \times \sqrt{n})$. Of course this method is far from satisfy. My code runs in 0.869 seconds. The insights is that for every number n we have $n = p_1^{m_1} \times p_2^{m_2} \times … \times p_i^{m_i}$ and the number of factors of n is $m_1 \times m_2 \times … \times m_i$.

This is an easy problem with only 25% difficulty rating and it costs me about 10min to code. My code runs in 0s. The idea is so simple that we can calculate rad(n) for every n from 1 to 100000. As an optimization, a priority queue is used to keep the first 10000 smallest values.

It’s too hard for me that didn’t figure out the answer until refer to others’ solution.

First of all, we can find that the number of moves is n(n + 2)refer to A005563 then what we need is to solve integes solution of equation n*(n+2) = t(t+1)/2 using this tool.