Square the Smallest

A list initially contains the numbers $2, 3, \dots, n$.
At each round, the smallest number in the list is replaced by its square. If there is more than one such number, then only one of them is replaced.

For example, below are the first three rounds for $n = 5$:
$$[2, 3, 4, 5] \xrightarrow{(1)} [4, 3, 4, 5] \xrightarrow{(2)} [4, 9, 4, 5] \xrightarrow{(3)} [16, 9, 4, 5].$$

Let $S(n, m)$ be the sum of all numbers in the list after $m$ rounds.
For example, $S(5, 3) = 16 + 9 + 4 + 5 = 34$. Also $S(10, 100) \equiv 845339386 \pmod{1234567891}$.

Find $S(10^4, 10^{16})$. Give your answer modulo $1234567891$.

Due to the large scale of the question, we need to find a smart way to approach it. First, let’s identify the pattern after multiple rounds. As shown in the example:

[2,3,4,5] –> [4,3,4,5] –> [4,9,4,5] –> [16,9,4,5]

You can see that after each round, the numbers are gradually magnified by squaring. In the next round, the smallest number is squared, which makes it not the smallest anymore in most cases.

Looking at this, every round can be viewed as selecting the smallest number and square it (for the list not becoming unordered, the square should be considered as replacing the original one). Therefore, at any time, all the numbers in the list are in the form of 2^(2^i) * 2j (i >= 0, j=floor(n / 2^i)), for example at beginning all i=0, as rounds goes on, for each number ‘2’, i increase by 1 at a time.

This gives us a good way to calculate S(n, r), where r is much smaller than n:

For each number t, it’s square after p = min(r, floor(log2(t))) rounds, add the sum of t ^ (2^p) * ceil(r / 2^p) to the result.

But given r = 10^16 and n = 10^4 in the problem, r >> n. This means before all numbers are squared once, there are still lots of rounds go on. From above observation, every number will have the opportunity to be squared, and then the left rounds will be performed on the number ‘4’ (since ‘4’ is the smallest number, it will be chosen to be squared in the following rounds until there’s no round left).

With the above analysis, we can first calculate when all number’s first square happens, the sum is the sum of number from 2 to n, plus the sum of them squared. This will consume 2n rounds.

Then the left is to calculate the sum of ‘4’ being squared, the rounds left is 10^16 – 2*10^4, each ‘4’ will be squared every 2 rounds, so there will be 1/2* (10^16 – 2*10^4 ) ‘4’s in the final list. Every 4 will be squared (10^16 – 2*10^4) / 2 times.

So the final task is to calculate `(2+3+…+n + (2^2+3^2+…+n^2)) % 1234567891 + ((10^16 – 2*10^4) / 2 * (4 ^ ((10^16 – 2*10^4) / 2)) % 1234567891`, please note the ‘^’ here denotes power, not XOR.

Due to the extremely large number, the pow and multiplication operation should be implemented in O(log(n)) time. You can write a simple recursive function using the Divide-and-conquer algorithm to calculate a^(nb) mod c: if b is even, a^(nb)=a^(b/2)*a^(b/2); if b is odd, a^(nb)=a*a^(b-1).
Doing so, you can compute the final result within feasible time. This is a programming challenge combined with the mathematical problem.

More Answers: