← Complete problem index

PROJECT EULER · #0636

Restricted Factorisations

Statement only · UnsolvedOriginal problem ↗

Consider writing a natural number as product of powers of natural numbers with given exponents, additionally requiring different base numbers for each power.

For example, 256 can be written as a product of a square and a fourth power in three ways such that the base numbers are different.
That is, 256=12×44=42×24=162×14

Though 42 and 24 are both equal, we are concerned only about the base numbers in this problem. Note that permutations are not considered distinct, for example 162×14 and 14×162 are considered to be the same.

Similarly, 10! can be written as a product of one natural number, two squares and three cubes in two ways (10!=42×52×42×33×23×13=21×52×22×43×33×13) whereas 20! can be given the same representation in 41680 ways.

Let F(n) denote the number of ways in which n can be written as a product of one natural number, two squares, three cubes and four fourth powers.

You are given that F(25!)=4933, F(100!)mod1000000007=693952493,
and F(1000!)mod1000000007=6364496.

Find F(1000000!)mod1000000007.

Write-up coming later

The complete problem is available here. An approach, code, and answer will be added later.