平方数の和の1の位が5になる回数 /「算数にチャレンジ!!」第1127問

問題概略
割ってから足す
足してから割る
おまけ：プログラムで計算

問題概略

次のような動作をする機械があります。
「キーボードから数 $n$ を入力すると $n^2$ を計算し，それまでの合計に加算する」
この機械に 1 から 1000 までの整数を小さい順に入力していき，1 回ごとに表示される数値を確認していきます。
次のように表示されますね。

1 回目は $1\times 1=1$

2 回目は $2\times 2+1=5$

3 回目は $3\times 3+5=14$

表示される数値の 1 の位が 5 になることは 1000 回のうち何回あるでしょうか。

http://www.sansu.org/used-html/index1127.html

解説の pdf も作りました。きれいなレイアウトで読みたい方はこちらをどうぞ。

drive.google.com

割ってから足す

平方数を 10 で割った余りは周期 10 で，その値は 1, 4, 9, 6, 5, 6, 9, 4, 1, 0 です。

これらの和は 45 で，2 倍した 90 は 10 の倍数。
$n$ 回目に表示される数を $S_n$ とおいて， $S(n)$ を 10 で割った余りを $g(n)$ とおくと，これは 20 を周期にもちます。

$g(n)=\bmod (S_n,\, 10)=\bmod\left(\sum_{k=1}^n k^2,\, 10\right)$
$=\bmod\left(\sum_{k=1}^n \bmod(k^2, 10),\, 10\right)$

数式で書くとなにやら仰々しいのですが，「全部足してから 10 で割る」のと「10 で割った余りを足して，最後にもう一回 10 で割る」のは同じです。

$g(n)$ の関係式を求めましょう。 $S_{n+1}=S_n+(n+1)^2$ から

\begin{align*}
g(n+1) &=\bmod (S_{n+1},\, 10)=\bmod (S_n+(n+1)^2,\, 10)\\
&=\bmod\big(\bmod(S_n,\,10)+ \bmod\left((n+1)^2,\, 10\right),\, 10\Big)\\
&=\bmod\Big(g(n)+\bmod\left((n+1)^2,\, 10\right),\, 10\Big)
\end{align*}

$g(1)=\bmod(S_1,\, 10)=1$ からスタートして
「 $2^2=4$ を 10 で割った余り 4 を足して 10 で割る」のような計算を 20 回やることは手計算でも簡単でしょう。

$S_n$ の 1 の位が 5 になるのは $n$ が 2, 5, 9, 10, 14, 17 のときで 6 回あります。
答えはこの $\frac{1000}{20}=50$ 倍なので「300 回」です。

足してから割る

$S_n=\sum_{k=1}^n k^2=\frac{1}{6}n(n+1)(2n+1)$ を利用します。
$f(n)=n(n+1)(2n+1)$ とおきます。

$S_n=\frac{1}{6}f(n)$ の 1 の位が 5 のとき $f(n)=6(10m+5)=60m+30$ とおけて $f(n)$ を 60 で割った余りは 30 です。

法が 60 では手計算で解く気がおきないので， $60=2^2\cdot 3\cdot 5$ を利用して法を小さくします。

法として 3, 4, 5 をとると条件はこうなります。

$f(n)\equiv 30\equiv 0\pmod{3}$
$f(n)\equiv 30\equiv 2\pmod{4}$
$f(n)\equiv 30\equiv 0\pmod{5}$

$S_n=\frac{1}{6}f(n)$ は整数なので $f(n)$ は 6 の倍数で， $f(n)\equiv 0\pmod{3}$ はつねに成立します。
$n$ の条件として考えないといけないのは $f(n)\equiv 2\pmod{4}$ と $f(n)\equiv 0\pmod{5}$ です。

まず $\bmod\, 5$ で考えます。 $f(n)\equiv 0$ の条件は「 $n\equiv 0$ または $n+1\equiv 0$ または $2n+1\equiv 0$ 」です。

$n+1\equiv 0$ のとき $n\equiv 4$ 。 $2n+1\equiv 0$ は次のように変形できます。

$2n\equiv -1\equiv 4\quad \therefore n\equiv 2\quad (\because \text{2と5は互いに素})$

まとめると $n\equiv 0,\, 2,\, 4\pmod{5}\mbox{　……(1)}$ です。

次は $\bmod\, 4$ で考えます。
$f(n)$ は整数係数で $a\equiv b\Rightarrow f(a)\equiv f(b)$ が使えるので
$f(0)$ , $f(\pm 1)$ , $f(2)$ を 4 で割った余りを調べるのが手っ取りばやいです。

$f(0)=0\equiv 0,\, f(1)=6\equiv 2,\, f(-1)=0\equiv 0,\, f(2)=30\equiv 2$

余りが 2 になる条件は $n\equiv 1,\, 2\pmod{4}\mbox{　……(2)}$ です。

1～ $20\ (=4\times 5)$ で考えると(1)(2)をみたす $n$ は 2, 5, 9, 10, 14, 17 の 6 個。
答えはこの $\frac{1000}{20}=50$ 倍なので「300 回」です。

おまけ：プログラムで計算

項が 1000 個しかないので愚直にコードを書いても十分高速です。約 0.003 秒でした。

    In[]:= AbsoluteTiming[
        f[n_] := Mod[n (n + 1) (2 n + 1)/6, 10] == 5;
        ans = Length@Select[Range@1000, f]]
       
    Out[]= {0.0030521, 300}

variee.hatenablog.com