对 Mathematica 着迷了,虽然我知道这热情不会持续多久。还是喜欢在解决问题中学习,这次是 Project Euler 的第 38 问。
提问:一个数依次×1,×2,……把所得连接成一个 9 位数,如果这个 9 位数正好是 1 到 9 的一个组合,则称其为原数的 pandigital 数。
回答:
(原图已丢失)
这段代码自己都觉得有点对不住观众,于是到论坛去取经。果然又找到了one-liner。
f = Join @@ IntegerDigits[# {1, 2}] &
For[n = 1*^4, Union@f@n =!= Range@9, n--]
Row@f@n
不过最让人惊叹的还是占着沙发的老兄,这哥们自豪地写道“我已经用纸和笔解决了”。这是 Project Euler 界的最高荣誉了。
他这样分析道:
我们已经知道 9 的 pandigital 数是 918273645 了,我们要找的数应该大于等于它。
- 既然 pandigital 数是由 ×1,×2,……连接而来,那么最大的 pandigital 数必定以 9 开头(因为它要大于等于 918273645 );
- 它不可能是 9 开头的两位数
9[0-9]
,这种数的 pandigital 数要么是 8 位,要么是 11 位;它不可能是 9 开头的三位数
9[0-9][0-9]
,这种数的 pandigital 数要么是 7 位,要么是 11 位; 它不可能大于 100,000 ,这种数的 pandigital 数位数肯定多于 9 位;所以,我们要寻找的数只能是 9 开头的四位数
9[0-9][0-9][0-9]
。
- 它不含 0 ,因为 0 乘任何数仍为 0 ,而该数的 pandigital 数只含 1 到 9 ;
- 它的各位均不同,否则 ×1 时就会产生相同的数;
- 它必然不含 1 ,因为 ×2 的时候会产生 1 ,谁让你 9 打头呢;
- 它的次高位不会是 5 以上,因为 ×2 的时候会出现 9 ,与 ×1 的时候的 9 重复(
9[5-9][2-9][2-9]×2 = 19xxx
);- 它的次高位不会是 4 ,因为 ×2 的时候会出现两个 8 或者一个 9(
94[2-9][2-9]×2 = 18[8-9]xx
);现在看来,可能是数只能是
9[2-3][2-7][2-7]
了。我们试试93[2-7][2-7]
:
- 它的第 3 位不会是 7 ,因为 ×2 的时候会出现 7 ,与 ×1 时重合(
937[2-7]×2 = 187xx
);- 它的第 3 位不会是 6 ,因为 ×1 的时候曾出现 3 ,所以 ×2 时不能有进位(
936[2-4]×2 = 1872x
,x
必为偶数,其 pandigital 数缺 5 );- 它的第 3 位不会是 5 ,因为 ×2 的时候会出现两个 1 或者一个 0(
935[2-7]×2 = 187[0-1]x
);- 它的第 3 位不会是 4 ,因为 ×2 的时候会出现两个 8 或者一个 9(
934[2-7]×2 = 186[8-9]x
);- 它的第 3 位不会是 3 ,因为出现了两个 3(
933[2-7]
);我们试试 9327 吧:
9327 × 1 = 9327
9327 × 2 = 18654
就是它了!