## Project Euler 288: An enormous factorial

#### Problem Description

For any prime `p` the number N(`p`,`q`) is defined by

N(`p`,`q`) = ∑_{n=0 to q} T_{n}*`p`^{n}

with T_{n} generated by the following random number generator:

S_{0} = 290797

S_{n+1} = S_{n}^{2} mod 50515093

T_{n} = S_{n} mod `p`

Let Nfac(`p`,`q`) be the factorial of N(`p`,`q`).

Let NF(`p`,`q`) be the number of factors `p` in Nfac(`p`,`q`).

You are given that NF(3,10000) mod 3^{20}=624955285.

Find NF(61,10^{7}) mod 61^{10}

#### Project Euler 288 Solution

Runs < 5 seconds in Python 2.7.Use this link to get the Project Euler 288 Solution Python 2.7 source.

#### Afterthoughts

- The Trinket above will run the problem’s smaller example in a few seconds. The larger problem would take the Trinket too long to run.

*Project Euler 288 Solution last updated*

In addition to my previous comment…

I can’t seem to gather why there’s “z” for N < n and p**n… for the rest. Could anybody enlighten me?

This program could be cleaned up a bit to make it easier to understand.

The intention is to use z as often as required to prevent the expensive calculation as doing so would slow down the program considerably.

So, since the answer is mod 61

^{10}we only need to calculate 61^{0}+61^{1}+61^{2}+…+61^{9}then use precalculated z for the rest.Why “[…] if N < n […]" ???