Product Oriented Recurrence

Read the problem and summarise the task requirements.
- Try to keep your response to a couple of sentences.

The − 6 in the right-hand side is suspicious. It seems to not be a coincidence that the other three terms include − 1, − 2 and − 3!

Let g_x = c^xf_x, and rewrite the recurrence using only terms of this new sequence.
- If you knew g_x modulo 10⁹ + 7, could you recover f_x?

We’ve solved lots of recurrences where terms are added, but here the terms are multiplied. Recall that the multiplicative structure of positive integers is fully described by the Fundamental Theorem of Arithmetic!

Let h_x, p be the largest power of prime p in g_x, and infer a recurrence for h_x, p in terms of h_{x − 1, p}, h_{x − 2, p} and h_{x − 3, p}.
If you knew h_x, p modulo 10⁹ + 7, could you recover g_x?
- The answer is no! But if we change the question slightly, the answer becomes yes.

Solving this recurrence iteratively for each x ≤ n would take O(n) time for each prime p, but n can go up to 10¹⁸.

Design an algorithm to find the nth term of the sequence h_⋅,p (or at least enough to reconstruct g_x from it) in o(n) (sub-linear) time.
Analyse the time complexity of your algorithm.
- Many things to account for:
  - Finding the primes.
    - Note that you can’t sieve all the way to 10⁹!
    - Instead find those that are relevant to each test case.
    - How many relevant primes could there be?
  - Finding the base cases for each prime.
  - Finding the nth term of each h_⋅,p recurrence.
  - Recovering g_n.
  - Recovering h_n.
- Estimate the running time of your algorithm.
Implement this algorithm in code.
- Reflector:
  - What potential pitfalls can you think of?
  - Write some tests to check for these pitfalls.
- Other group members:
  - Write a program which solves the problem.
  - Subroutines and unit tests are particularly highly recommended due to the modular nature of the algorithm.
- Run your tests and debug if necessary.
Submit your output for judging!
- Debug as required.