One More One

Consider the following process that can be applied recursively to any positive integer $n$:

if $n = 1$ do nothing and the process stops,
if $n$ is divisible by $7$ divide it by $7$,
otherwise add $1$.

Define $g(n)$ to be the number of $1$’s that must be added before the process ends. For example:
$125\xrightarrow{\scriptsize{+1}} 126\xrightarrow{\scriptsize{\div 7}} 18\xrightarrow{\scriptsize{+1}} 19\xrightarrow{\scriptsize{+1}} 20\xrightarrow{\scriptsize{+1}} 21\xrightarrow{\scriptsize{\div 7}} 3\xrightarrow{\scriptsize{+1}} 4\xrightarrow{\scriptsize{+1}} 5\xrightarrow{\scriptsize{+1}} 6\xrightarrow{\scriptsize{+1}} 7\xrightarrow{\scriptsize{\div 7}} 1$.
Eight $1$’s are added so $g(125) = 8$. Similarly $g(1000) = 9$ and $g(10000) = 21$.
Define $S(N) = \sum_{n=1}^N g(n)$ and $H(K) = S\left(\frac{7^K-1}{11}\right)$. You are given $H(10) = 690409338$.
Find $H(10^9)$ modulo $1\,117\,117\,717$.

This problem appears to be a Project Euler problem (projecteuler.net), specifically problem number 626.

The solution for $H(10^9)$ modulo $1\,117\,117\,717$ mathematically requires programming knowledge as well, because you will need to write an algorithm to solve it due to the complexity and the size of the numbers.

Here’s how you could approach it:

Firstly, we can see a repeating pattern in $g(n)$. Observe that, when $n$ is a multiple of $7$, $g(n)$ is $1$ plus $g(n/7)$. Also, $g(n\cdot7+6)$ is close to $7\cdot g(n)$. This can be proved by induction.

Define $g_r(n)$ to be the number of $1$’s that must be added before the process ends and the resulting number is $r$ (where $r$ ranges from $0$ to $6$).

We can get the following results:

$g_0(n) = g(n)$

$g_r(n) = g(n\cdot7 + r)$

Consider the given condition:

$H(K) = S\left(\frac{7^K-1}{11}\right)$

We can get a recursive formula as:

$S(n) = S(n/3) + g_0(n/7) + \dots + g_6(n/7)$ for $n ≈ 7a$.

Where the ellipsis represents the terms for each $r$, except for $g_6(n/7)$ which requires special handling.

With the help of the above recursive formula, a program can be written in Python or any other language which produces the result of H(K) for any number K.

When you calculate $H(10^9)$ modulo $1\,117\,117\,717$, you will achieve the result.

You should now have an understanding of the mathematical logic required for this problem.

More Answers: