平方コピペ数解答
はじめに
さる2016/3/5に行われた、CodeIQの感謝祭で、よく数学系の問題を出題されている@riverplusさんが次の特別問題を出題されたそうです。( こちらのページ にもあります )
CodeIQ感謝祭で出題した「平方コピペ数問題」です。開催中は2名の方に正解して頂きました。しばらく正誤チェックページを置いておくのでよければトライしてみて下さい! #codeiq39 https://t.co/lqm0e4I68r pic.twitter.com/QkTafTihld
— Kawazoe (@riverplus) 2016年3月5日
感謝祭には参加しなかったのですが、折角なので解いてみました。
解説
まず、「コピペ数」とはどんな数か? を調べてみます。繰り返しの桁数を$n$とすれば ( 全体では$2n$桁 )、次のように表せるはずです。 $$ \begin{eqnarray} A &=&\overbrace{a_1 a_2 \cdots a_n}^{n}\overbrace{a_1 a_2 \cdots a_n}^{n} \\ \,&=&a_1 a_2 \cdots a_n \times ( 10^n + 1 ) \end{eqnarray} \\ (\, a_1\ge 1 \,) $$
なお、$a_1$の条件は、ないと全体の桁数が縮んでしまいますので必要です。
では、この「コピペ数」$A$ が更に平方数でもある場合とは…??
例えば $n=1$ の場合で考えると 11 の倍数なので最小でも$11^2=121$ って…。桁数が振り切れてしまいますね。
平方数である以上、全ての素因数の指数が偶数となりますから、$10^n+1$ の部分の $11,\,101,\,1001=7\times 11\times 13, \cdots$ が各素因数の指数高々1の場合、平方数が最小でも$(10^n+1)^2$になってどうしても桁数が収まりません。
…しかし逆に考えれば、指数が2以上となるような素因数を持つ$10^n+1$を取り敢えず探せば良さそうです。
まあ計算は省略して ( というか factorコマンドで1つずつ見ていったのですが )、最初に見つかるのは$n=11$の時、$100000000001=11^2\times 23\times 4093\times 8779$で、素因数11の指数が2です。意外と大きい。この桁数の下界の状況で平方コピペ数が作れればそれで最小です。
なので、次の条件を満たす平方数$S$は? という話になります。
$$
a_1a_2\cdots a_{11}=S \times 23\times 4093\times 8779 \\
A=S\times 23\times 4093\times 8779 \times 100000000001 \\
$$
ここから計算していけば良いのですが、そもそも$(10^n+1)^2$ってのが、実は$2n$桁に僅かに収まらない数だったことを思い出すと、$a_1a_2\cdots a_n$の部分は $10^n+1$ より1桁小さい程度であり、素因数$11^2$が抜けて余裕ができている分、
$$
S\gt \frac{11^2}{10}
$$
とSを見積もることができます ( 不等式としては正確ではありませんが、大体のところ )。結局$\frac{11^2}{10}\approx 12$ を超える平方数で最小といえば 16 ですから、$S=16$ とした時の
$$
\begin{eqnarray}
A &=&16\times 23\times 4093\times 8779 \times 100000000001 \\
\,&=&36363636364^2 \\
\,&=&1322314049613223140496
\end{eqnarray}
$$
が答えと分かります。
終わりに
折角出題者ご本人がいらっしゃたのに参加できなくて残念でした。また機会があれば今度はお会いしたいですね。