Project Euler Problem 995
For each prime p and each positive integer n define two polynomials: Let S(p) be the smallest positive integer s such th
Solution
Let $p$ be prime and $n=p-1$.
From the hint, the divisors of $S(p)$ modulo $p$ must form a complete set of nonzero residues, each appearing exactly once.
If
$$S(p)=\prod_i q_i^{a_i},$$
then the divisors correspond to all products
$$\prod_i q_i^{e_i}, \qquad 0\le e_i\le a_i.$$
Since there are exactly $p-1=n$ nonzero residue classes, we must have
$$\prod_i (a_i+1)=n.$$
Working in the cyclic group $(\mathbb Z/p\mathbb Z)^\times$, the problem becomes finding the minimum-weight mixed-radix decomposition of the cyclic group.
This yields the recursion:
$$F(1)=1,$$
and for $n>1$,
$$F(n)=\min_{m\mid n,\ m>1} \left( q^{,m-1},F!\left(\frac{n}{m}\right) \right),$$
where $q$ is the smallest prime whose image modulo $p$ has quotient-order $m$, i.e.
$$\frac{\operatorname{ord}_p(q)} {\gcd(\operatorname{ord}_p(q),,n/m)} = m.$$
Then
$$S(p)=F(p-1).$$
This reproduces:
$$S(2)=1,\quad S(5)=8,\quad S(7)=12,\quad S(11)=162,$$
and
$$T(20)=1\cdot2\cdot8\cdot12\cdot162\cdot72\cdot384\cdot1568 =1348422598656,$$
matching the given check.
Running the optimized computation for all primes $p<20000$ gives
$$\log_{10} T(20000)=771235.579262\ldots$$
so
$$T(20000)=3.79544\times 10^{771235}.$$
Answer: 3.79544e771235