Project Euler [Problem 38]

定期的にやりたいね

Relativity Space の Terran-1 は次の打ち上げ予定が出ないねぇ

問題

Pandigital multiples

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

私訳

パンデジタル倍数

192 とその 1, 2, 3 倍を取り上げると

192 × 1 = 192 192 × 2 = 384 192 × 3 = 576 これを結合すると 1 から 9 までのすべての数字, 192384576 が得られる. 我々は 192384576 を 192 と (1,2,3) の結合積(concatenated product) と呼ぶ。

同様のことは 9 と 1, 2, 3, 4, 5 の積でも成立して, 9 と (1,2,3,4,5) の結合積は 918273645 となる。 9 桁のパンデジタル数のうち, 整数と (1, 2, ..., n) ただし n > 1 の結合積として得られるものの中で最大のものはなにか？

解答方針

n = 1 が除外されているのは 987654321 が自明だからだろう。 整数 z と行ベクトル v の結合積を考えた時、z は何桁の整数になるだろうか？ 桁数関数を s(z) とすると

s(z)	v	説明
4	(1,2)	4+5桁
3	(1,2,3)	3+3+3桁
2	(1,2,3,4)	2+2+2+3桁
1	(1,2,3,4,5)	1+2+2+2+2桁

となり、1～4桁の整数を総当たりすればよいことがわかる。