Saving Paper

When wrapping several cubes in paper, it is more efficient to wrap them all together than to wrap each one individually. For example, with 10 cubes of unit edge length, it would take 30 units of paper to wrap them in the arrangement shown below, but 60 units to wrap them separately.

Define $g(n)$ to be the maximum amount of paper that can be saved by wrapping $n$ identical $1\times 1\times 1$ cubes in a compact arrangement, compared with wrapping them individually. We insist that the wrapping paper is in contact with the cubes at all points, without leaving a void.
With 10 cubes, the arrangement illustrated above is optimal, so $g(10)=60-30=30$. With 18 cubes, it can be shown that the optimal arrangement is as a $3\times 3\times 2$, using 42 units of paper, whereas wrapping individually would use 108 units of paper; hence $g(18) = 66$.
Define
$$G(N) = \sum_{n=1}^N g(n)$$
You are given that $G(18) = 530$, and $G(10^6) \equiv 951640919 \pmod {1\,000\,000\,007}$.
Find $G(10^{16})$. Give your answer modulo $1\,000\,000\,007$.

This appears to be a problem from Project Euler (Project Euler Problem 552), an online platform that posts challenging math and computation problems. Solving it requires significant knowledge in number theory and experience with programming. Here is a skeletal approach:

1. **Decomposite $n$:** To get the optimal arrangement, each cube should be decomposed into product of smaller integers, since wrapping a $k1 \times k2 \times k3$ box always requires less papers than wrapping $k1 \times k2$, $k3$ individual boxes.

2. **Dynamic Programming:** Define $dp[i][j][k]$ as the least number of papers to wrap a $1 \times i \times jk$. You may initiate $dp[i][j][k]$ as infinite. All states can be updated from $dp[i’][j’][k’]$ where $i’ \times j’ \times k’ | i \times j \times k$. Also $dp[i][j][k]$ should be updated from states of $dp[i’][j’][k’] + dp[i”][j”][k”]$ where $i’ \times j’ \times k’ = i \times j \times k$ and $i”>\times j”\times k” \div i’\times j’\times k’ = 1$. With this, you can find the minimum possible surface area for each $n = 1 \times i \times j \times k$.

3. **Finding $g(n)$ and $G(N)$:** After obtaining least number of papers to wrap a $1 \times i \times jk$, $g(n)$ can be easily obtained from $6n-dp[1][i][j*k]$ and then $G(N)$ is the summation of all $g(n)$ for $1\leq n \leq N$.

4. **Modulo Calculation:** As the problem asks for $G(10^{16})$ mod $1,000,000,007$, you need to perform all additions under modulo to avoid integer overflow.

This problem is very challenging and requires good knowledge in number theory and dynamic programming. It may still be very difficult even with the above hints, due to the large constraints and precision required.

More Answers: