Project Euler 104

Pandigital Fibonacci ends

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.

Project Euler 293

Pseudo-Fortunate Numbers

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

Project Euler 113

Non-bouncy numbers

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.

Project Euler 323

Bitwise-OR operations on random integers

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.

Project Euler 179

Consecutive positive divisors

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$.

Project Euler 124

Ordered radicals

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.