Project Euler 170 / 連結された積が0から9までのパンデジタル数になるパンデジタル数の最大値

問題概略
右から攻めるか左から攻めるか
実例を 1 つ探す
分割数などをしぼりこむ
高速化のための微調整

問題概略

6 を 1273 と 9854 にかけると次のようになる。
\begin{align*}
&6 \times 1273 = 7638\\
&6 \times 9854 = 59124
\end{align*}
これらの積を連結すると，1 から 9 までを網羅するパンデジタル数 763859124 になる。
763859124 を「6 と $(1273,\, 9854)$ の連結された積」と呼ぶことにする。

かける前の数を連結した 612739854 も 1 から 9 までを網羅するパンデジタル数である。
同じことが 0 から 9 までを網羅するパンデジタル数に対してもできる。

かける前の数を連結した数も 0 から 9 までのパンデジタル数となるような，ある整数と 2 つ以上の整数の連結された積が 0 から 9 までのパンデジタル数の最大値を求めよ。
https://projecteuler.net/problem=170

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

drive.google.com

右から攻めるか左から攻めるか

パンデジタル数を $n$ 個に分割したときの各数を次のようにあらわします。

\begin{align*}
a\cdot b_1=c_1,\, a\cdot b_2=c_2,\, \cdots ,\, a\cdot b_n=c_n
\end{align*}

$a$ と $b_1$ ～ $b_n$ を連結した数を「左のパンデジタル数」とよんで， $c_1$ ～ $c_n$ を連結した数を「右のパンデジタル数」とよぶことにします。
この問題で要求されているのは右のパンデジタル数の最大値です。

「左」→「右」と「右」→「左」のどちらで攻めるかを考えました。

「左」から「右」を求める方法：

左のパンデジタル数を $a$ と $b_1$ ～ $b_n$ に分割する
$a\cdot b_i\ (1\leqq i\leqq n)$ の結果を連結してパンデジタルかどうか調べる

「右」から「左」を求める方法：

右のパンデジタル数を $c_1$ ～ $c_n$ に分割する
$c_1$ ～ $c_n$ の公約数 $a$ を求める
$a$ と $c_i/a=b_i\ (1\leqq i\leqq n)$ を連結してパンデジタルかどうか調べる
以上をすべての $a$ に対して調べる

「左」→「右」の方が楽ですが，かけ算して連結しないと右のパンデジタル数がどんな数なのかわからないのが難点です。
本当に全探索しないと最大値は求められないので，計算量の面から「右」→「左」でいくことにしました。

実例を 1 つ探す

0～9 を使ったパンデジタル数は $9\cdot 9!=3,265,920$ 個あります。

これらに対してすべての分割法を試すのは多分無駄なので，「適当な仮定をおいて実例を 1 個探す」→「その数より大きい数についてちゃんと調べる」でいこうと思いました。

「分割数 $n=2$ かつ $a$ は 2 桁以下」と仮定して計算しました。

  In[]:= AbsoluteTiming[
    lst = Select[Permutations@Reverse@Range[0, 9], First@# != 0 &];
    testk[lst_, k_] := Module[{c1, c2, aLst},
      {c1, c2} = FromDigits /@ TakeDrop[lst, k];
      aLst = Select[Divisors@GCD[c1, c2], # < 100 &];
      AnyTrue[aLst, 
       Sort[Join @@ IntegerDigits /@ {#, c1/#, c2/#}] == Range[0, 9] &]];
    isok[lst_] := AnyTrue[Range@9, testk[lst, #] &];
    ans = FromDigits@SelectFirst[lst, isok]]
   
  Out[]= {5.51237, 9857164023}

各行の内容はこうです。

2 行目：解の候補となるパンデジタル数の桁数字のリストを作り，降順に並べる
4 行目：桁数字のリストを先頭の $k$ 個と残りにわけてそれぞれ数に直す（ $c_1$ , $c_2$ ）
5 行目： $c_1$ , $c_2$ の公約数 $a$ で 2 桁未満のもののリストを作る
7 行目： $a$ , $c_1/a$ , $c_2/a$ を連結してパンデジタルかどうか調べる
9 行目：条件をみたす最初の桁数字のリストを抽出して数に直す

これでみつけた「9857164023」より大きなパンデジタル数は意外に多くて，10565 個ありました。
これらすべてに対して「右」→「左」のチェックをするのは大変なのでもう少しくわしく調べます。

分割数などをしぼりこむ

分割数をしぼりこむためのコードを書きました。
以下， $x$ の桁数を $len(x)$ であらわします。左のパンデジタル数の桁数の条件から

\begin{align*}
len(a)+\sum_{i=1}^n len(b_i)=10\mbox{　……(1)}]
\end{align*}

一般に $x$ 桁の数と $y$ 桁の数の積は $x+y-1$ 桁か $x+y$ 桁です（例： $2\cdot 1=2$ , $2\cdot 5=10$ ）。

$len(a\cdot b_i)=len(a)+len(b_i)-1$ が $k$ 回おこるとします。右のパンデジタル数の桁数の条件から

\begin{align*}
&\sum_{i=1}^n \left\{len(a)+len(b_i)\right\}-k=10\\
&\therefore n\cdot len(a)+\sum_{i=1}^n len(b_i)-k=10\mbox{　……(2)}
\end{align*}

(1)(2)を辺ごとに引くと $(1-n)len(a)+k=0\mbox{　……(3)}$ を得ます。

$2\leqq n\leqq 9$ , $1\leqq a\leqq 8$ , $0\leqq k\leqq n$ としてこれを解きました。

  eqn = {(1 - n) len_a + k == 0, 1 <= len_a <= 8, 
        2 <= n <= 9, 0 <= k <= n};
  sol = Reduce[eqn, {n, len_a, k}, Integers]

(3)をみたす $\left(n,\, len(a),\, k\right)$ は次の 9 個でした。

\begin{align*}
&(2,\, 1,\, 1),\, (2,\, 2,\, 2),\, (3,\, 1,\, 2),\, (4,\, 1,\, 3),\, (5,\, 1,\, 4)\\
&(6,\, 1,\, 5),\, (7,\, 1,\, 6),\, (8,\, 1,\, 7),\, (9,\, 1,\, 8)
\end{align*}

$(2,\, 1,\, 1)$ と $2,\, 2,\, 2)$ は「実例を 1 つ探す」で調べたケースです。

残り 7 パターンについては実は調べる必要がありません。

これらすべてが「 $len(a)=1$ かつ $k=n-1$ 」であることに注目しましょう。
$n$ 個の $a\cdot b_i=c_i$ のうち $n-1$ 個では $len(b_i)=len(c_i)$ が成り立ちます。

$len(c_i)=len(a\cdot b_i)=len(a)+len(b_i)-1=len(b_i)$

残り 1 個の $a\cdot b_i=c_i$ では $len(b_i)+1=len(c_i)$ が成り立ちます。

$len(c_i)=len(a\cdot b_i)=len(a)+len(b_i)=len(b_i)+1$

これらを使うと $n\geqq 3$ のケースはすべて $n=2$ のケースに帰着できることが示せます。

$n=3$ の場合を考えます。

$a \cdot b_1 = c_1\mbox{　……(4)}$
$a \cdot b_2 = c_2\mbox{　……(5)}$
$a \cdot b_3 = c_3\mbox{　……(6)}$

$len(b_1)=len(c_1)$ , $len(b_2)=len(c_2)$ , $len(b_3)+1=len(c_3)$ として一般性を失いません。

$len(b_2)=len(c_2)=L$ とおきます。(4)を $10^L$ 倍して(5)と辺ごとに足すと次のようになります。

$a(b_1\cdot 10^L+b_2)=c_1\cdot 10^L+c_2$

要するに 2 つの式を連結して1つにできるわけです。
これを繰り返すと $n=4$ ～ $n=9$ のケースはすべて「 $n=2$ , $len(a)=1$ , $k=1$ 」のケースに帰着できます。
結局，「実例を 1 つ探す」で求めた例がこの問題の解だったわけです。

高速化のための微調整

条件をみたすパンデジタル数を全部求めてみたら $a$ はすべて 48 以下の 3 の倍数でした。

$a=3,\, 6,\, 9,\, 12,\, 15,\, 18,\, 21,\, 24,\, 27,\, 36,\, 39,\, 42,\, 45,\, 48$

これを証明して計算にいかします。

a は 3 の倍数

$a\cdot b_1=c_1$ , $a\cdot b_2=c_2$ を辺ごとに足します。

$a(b_1+b_2)=c_1+c_2\mbox{　……(7)}$

パンデジタル数の条件から $a$ , $b_1$ , $b_2$ の桁数字の和も $b_1$ , $b_2$ の桁数字の和も $0+1+\cdots+9=45$ で 3 の倍数です。

$a+b_1+b_2\equiv c_1+c_2\equiv 0\pmod{3}$

(7)を $\bmod\, 3$ で考えます。

$a(-a)\equiv 0\pmod{3}$

$a\equiv 0,\, \pm 1\pmod{3}$ のうちこれをみたすのは $a\equiv 0\pmod{3}$ だけなので $a$ は 3 の倍数です。

a は 50 未満

$a\geqq 50$ の場合を考えます。これは「分割数などをしぼりこむ」の $\left(n,\, len(a),\, k\right)=(2,\, 2,\, 2)$ のケースです。

\begin{align*}
&a\cdot b_1=c_1,\, a\cdot b_2=c_2\\
&len(a\cdot b_1)=len(a)+len(b_1)-1=len(b_1)+1\mbox{　……(8)}\\
&len(a\cdot b_2)=len(a)+len(b_2)-1=len(b_2)+1
\end{align*}

$b_1$ , $b_2$ の少なくとも 1 つは首位の数字が 2 以上です。
$b_1$ の首位の数字が 2 以上だとしましょう。
これを $a\ (\geqq 50)$ 倍すると 2 桁以上増えます。

$len(a\cdot b_1)\geqq len(b_1)+2$

これは(8)と矛盾しているので $a< 50$ です。

再計算

以上をふまえてもう一度計算しました。計算時間は約 4 秒です。
もともとの計算時間が約 5.5 秒で，その半分は候補となるパンデジタル数の集合を作るのに費やされているので純粋な計算時間はだいたい半分になりました。

  In[]:= AbsoluteTiming[
    lst = Select[Permutations@Reverse@Range[0, 9], First@# != 0 &];
    testk[lst_, k_] := Module[{c1, c2, aLst},
      {c1, c2} = FromDigits /@ TakeDrop[lst, k];
      aLst = Intersection[Divisors@GCD[c1, c2], Range[3, 50, 3]];
      AnyTrue[aLst, 
       Sort[Join @@ IntegerDigits /@ {#, c1/#, c2/#}] == Range[0, 9] &]];
    isok[lst_] := AnyTrue[Range@9, testk[lst, #] &];
    ans = FromDigits@SelectFirst[lst, isok]]

砂場で遊ぼう

c++/python/mathematica などの練習帳