@hiroyuking
前提知識
記事に回答のネタバレが含まれるので、自分で答えたい人は読まないでください
問題
すべての桁に 1 から n が一度だけ使われている数をn桁の数がパンデジタル (pandigital) であるということにしよう: 例えば5桁の数 15234 は1から5のパンデジタルである.
7254 は面白い性質を持っている. 39 × 186 = 7254 と書け, 掛けられる数, 掛ける数, 積が1から9のパンデジタルとなる.
掛けられる数/掛ける数/積が1から9のパンデジタルとなるような積の総和を求めよ.ヒント: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.
一応自分なりの回答としては、 $0,1,2,3,4,5,6,7,8,9,=,*$ を順列として並べてevalで評価して答えを出した。つまりは $39 × 186 = 7254$ 、みたいな数の組み合わせを調べるためにすべての並びを数え上げているのだが、それでは時間がかかってしまう。
数学的なトリックを見抜きたいがわからないので、他の人の回答を読んだ。
回答
- ProjectEuler 正答後のスレッドにて
以下、翻訳は筆者がしている。
我々は $A+B=C$ になる数列かつ 文字列の長さが $a+b+c = 9$ になる答え を検索しています。
(1) aとbの文字列長だけで $(a+b-1) \lt c \lt (a+b)$ の積の形を作ることができる
また (2) 合計の長さ a+b+c は 9 でなければならない
(1)がいきなりわからなかったのですが
-
2つの正の整数a, bの積cの桁数について、 aの桁数d1 、bの桁数d2 、cの桁数d3としたとき、その関係は
$$ d1 + d2 -1 \leq d3 \leq d1 + d2$$
になるようだ。この話に関する原典みたいなものをないか探したが、いいのはなかったが、Slide Rule Decimal Point Location Methodsのp.40にそのような記述があった。おそらく数学ではよく知られた概念なので言及されないのだろう。というかよく考えてみれば自明かもしれない。
$$ a+b+( a + b + \underbrace{f}_{ s.t. \space 0 \lt f \lt 1 } ) = 9 \\ 2a+2b = 9-f \\ a+b = \frac{(9-f)}{2} \\ 4.5 \lt a+b \lt 5$$(1),(2)から、次のように結論付けることができます；
よって、式 A+B=C において、長さ $1 \lt a \lt 5$ の数値 A が与えられた場合、他の数値 B は長さ $4.5-a \lt b \lt 5-a$ である。
この性質を利用して、4 桁までカウントする数値 A のループと、長さ 4.5-長さ (A) から 5-長さ (A) の数をカウントするループ B を作成しました。
要は
- 数値$a$は桁数が $1 \lt a \lt 5$ までしか探索不要
- その条件において数値$b$は桁数が$4.5-a \lt b \lt 5-a$までしか探索不要
サンプルコード
- あとは、重複なく数え上げる必要がある。Rubyだとhashが使いやすいのでそれを使った。
DIGITS = (1..9).to_a
ans = {}
(1..9999).each do |a|
a_digits = a.to_s
for b_digit in (4.5 - a_digits.size).to_i..(5 - a_digits.size)
tmp_digits = DIGITS - a_digits.split("").map(&:to_i).to_a
tmp_digits.permutation(b_digit) do |b_arr|
c_arr = tmp_digits - b_arr
next if b_arr.size==0
b = b_arr.join.to_i
c = a * b
a_arr = a.to_s.split("").map(&:to_i)
c_arr = c.to_s.split("").map(&:to_i)
digits = a_arr + b_arr + c_arr
if DIGITS.all? {|d| digits.include? d } && [a_arr.size,b_arr.size,c_arr.size].inject(&:+)==9
puts "#{a} * #{b} = #{c}"
# product => [small, large]
ans.merge!({c => [[a,b].min, [a,b].max]})
end
end
end
end
p ans.map{|k,v| k.to_i}.inject(&:+)
