Maximum Integer Partition Product

An integer partition of a number $n$ is a way of writing $n$ as a sum of positive integers.
Partitions that differ only in the order of their summands are considered the same.
A partition of $n$ into distinct parts is a partition of $n$ in which every part occurs at most once.
The partitions of $5$ into distinct parts are:
$5$, $4+1$ and $3+2$.
Let $f(n)$ be the maximum product of the parts of any such partition of $n$ into distinct parts and let $m(n)$ be the number of elements of any such partition of $n$ with that product.
So $f(5)=6$ and $m(5)=2$.
For $n=10$ the partition with the largest product is $10=2+3+5$, which gives $f(10)=30$ and $m(10)=3$.
And their product, $f(10) \cdot m(10) = 30 \cdot 3 = 90$.
It can be verified that
$\sum f(n) \cdot m(n)$ for $1 \le n \le 100 = 1683550844462$.
Find $\sum f(n) \cdot m(n)$ for $1 \le n \le 10^{14}$.
Give your answer modulo $982451653$, the $50$ millionth prime.

This is quite a challenging problem that stitches together number theory, combinatorics, and programming. It belongs to the advanced topics usually addressed in math contests or competitive programming.

Firstly, the problem can be interpreted as follows – we are to partition a number in such a way that we extract the maximum product of its partitions, and counting the number of partitions that lead to that product, for every number from 1 to 10^14. And then we are asked to find the sum of the product of the maximum product and count of the respective partitions, finally providing the answer modulo 982451653.

Let’s breakdown the solution step by step:

Step 1: Look for Patterns

We can find a pattern for smaller values of `n`. For `n=1 to 10`, we find the respective `f(n)`, `m(n)` and `f(n) · m(n)`,

“`
n f(n) m(n) f(n) · m(n)
——————————————–
1 1 1 1
2 2 1 2
3 3 1 3
4 4 1 4
5 6 2 12
6 6 1 6
7 7 1 7
8 8 1 8
9 12 2 24
10 30 3 90

“`

From this table, we notice a pattern that `f(n) = n` for `n=1 to 4`, and `f(n) = 2*(n-2)` for `n >= 5`. Except, whenever we have `n` that can be written as `n= 3 + x + 2x`, `f(n)` equals `2x * 3 *x`.

Step 2: Develop an Algorithm

Here’s an algorithm to calculate `f(n)`:

– If `n <= 4`, then return `n` - If `n` can be written as `n=3+x+2x` for some integer `x > 1`, then return `2x*3*x`
– Else return `2*(n-2)`

For `m(n)`, it is usually `1` except for when `n=5` (it’s `2`) and whenever `n=3+x+2x` (it’s `3`).

To find out when `n` can be written in the form `3+x+2x`, we can use a quadratic equation. The sum `n=3+x+2x` can be rewritten as `n = 3x + 3 => 3x = n – 3`; solving this quadratic gives us roots `x = [-b ± sqrt(b^2 – 4ac)] / 2a`.

Step 3: Coding the Algorithm

Coding this solution requires more than basic coding skills. It is also computationally expensive to execute for `n=10^14` without implementing it as a fast algorithm in a language like C++, Python or Java.

Lastly, the sum `f(n) · m(n)` for `n=1 to 10^14` will result in a large number. To find this large number modulo `982451653`, which is a prime number known as the `50000000`-th prime, you use the modulo operation during each step of the summation to prevent overflow and keep the number manageable.

The specific implementation details will vary depending on the programming environment you use, your prior knowledge with these concepts, and your comfort level with mathematics. If you’re not familiar with coding, consider collaborating with someone who is, or seek additional help.

Please note that getting to these insights and proposing an optimized implementation means a deep understanding of problem-solving, number theory, and computer science concepts. It is not a trivial task.

More Answers: