# Megaprime Numbers

This post is associated with solution to Megaprime Number, in which two basic techonics are used, namely miller-robin prime test and implementation of next permutation.

# Random Number Generator in C++

This post is written to keep some simple and useful skills to generate random numbers in c++ and is inspired when I was trying to solve this problem on Hackerrank. What I was trying to do is hash a set of integers by assigning each distinct integer an unique random number and got these random numbers crossed together by applying xor operation one by one. Unfortunately, I got wrong answer at the first several tries and seek help from others’ solutions. Then I used a random number generator named mt19937_64 and pass all test cases. This is fucking amazing, that’s what I thought at that moment :P

We have already got used to use function rand() offered by C programming language, but as C++ standard library becomes more and more completed, it’s essential to know and master some basic usage of cpp random library.

First, there are many kinds of random number generation algorithms, the most frequently used are: Linear Congruential Generators (LCG), Mersenne Twister (MT) and Lagged Fibonacci generator(LFG). To be honest, I’ve never heared of LFG. The pseudo-random number generator used in C is LCG, I think. MT is one kind of the most robust and as well as fast generator, which is developed by two Japanese and is widely used until now.

There are two kinds of different MT implements: std::mt19937 and std::mt19937_64, with the letter generates random number fit in 64-bit integers. The reason that number 19937 in both of names is the length of circle of pesudo-random numbers generated by MT is $2^{19937}$.

In order to generate random sequence, a seed is needed as a start point. Here is an example of using random_device to generate random seed.

But using random_device directly is relatively slow, the wise choice is using it just as a start.
For example, the following code generates random numbers in range 0 to 99 (both inclusive):

std::uniform_int_distribution is implemented as a template for uniform distribution.

## References

https://gaomf.cn/2017/03/22/C++_Random/

# 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 145

## How many reversible numbers are there below one-billion?

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.

# 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 329

## Prime Frog

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.

# 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 243

## Resilience

I used a silly method and my code runs about 1 minutes…
Generating all phi(i) for i in range [1, 10^9] then check every number one by one.