Project Euler with Ruby on WSL [Problem 32]

Project Euler Programming ruby

32 = 25

職業病ですね

問題

Pandigital products

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

私訳

全数的*1な積

n 桁の数が pandigital である、とは 1 から n までがちょうど1回現れるものと定義する。例えば、 15234 は 5 桁の pandigital 数である。

7254 = 39x186 は乗数、被乗数、積全体でみて 1～9 の pandigital である。

1～9 について、それ自身が pandigital である数と、積の形式で pandigital であるものすべての和を求めよ。

ヒント : 同じ数が複数の積表現を持つことがある。和を求める際は2重に足さないようにすること

解答方針

pandigital な数には明らかに 2 種類あって

  1. それ自身が pandigital (identity)
  2. 積の表式全体で pandigital

前者はほとんど自明なので特に考えることはない

また前者の和は、例えば 1xxxxxxxx の形式を考えると 8! 通りあることを考えると、 各位について、1～9 がそれぞれ 8! 通りずつあるわけで、 その合計は 8! \cdot \sum_{i=1}^9 iiiiiiiii = 8! \cdot 111111111 \cdot 45

後者が大問題で、ナイーブに考えると 9! x 9C2 くらいある…

i 桁の数 d_i と j 桁の数 d_j の積を考えると 10^{i-1} \le d_i \lt 10^i, 10^{j-1} \le d_j \lt 10^j \therefore 10^{i+j-2} \le d_i d_j \lt 10^{i+j}

つまり積は i+j-1桁～i+j桁 ということがわかる。 合計は 9 桁だから 2i+2j-1 =9 or 2i+2j = 9 後者はありえないから i+j = 5 しか許されないことが分かった ここまで絞り込めたらあとは総当たりだ(identity の分を足し忘れそう)

・・・。identity の分を足さないのが正解だった。…？おかしくないか

*1:pandigital を上手く訳せない。全ての桁について、とかすべての数字についてなんだけど