---

Problem 672

---

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\stackrel{+1}{\to }126\stackrel{÷7}{\to }18\stackrel{+1}{\to }19\stackrel{+1}{\to }20\stackrel{+1}{\to }21\stackrel{÷7}{\to }3\stackrel{+1}{\to }4\stackrel{+1}{\to }5\stackrel{+1}{\to }6\stackrel{+1}{\to }7\stackrel{÷7}{\to }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$.

---

再多一个一

从正整数$n$开始进行如下迭代操作：

• 若$n=1$，则迭代中止；
• 若$n$能被$7$整除，则除以$7$；
• 否则加$1$。

记$g(n)$为迭代过程中加$1$的次数。例如：

$$125\stackrel{+1}{\to }126\stackrel{÷7}{\to }18\stackrel{+1}{\to }19\stackrel{+1}{\to }20\stackrel{+1}{\to }21\stackrel{÷7}{\to }3\stackrel{+1}{\to }4\stackrel{+1}{\to }5\stackrel{+1}{\to }6\stackrel{+1}{\to }7\stackrel{÷7}{\to }1$$

总共有八次加$1$的操作，因此$g(125)=8$。类似地，$g(1000)=9$，$g(10000)=21$。

记$S(N)=\sum _{n=1}^{N}g(n)$而$H(K)=S\left(\frac{7^K-1}{11}\right)$。已知$H(10)=690409338$。

求$H({10}^9)$并对$1,117,117,717$取余。

---