Project Euler Problem 38

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?

地址:http://projecteuler.net/index.php?section=problems&id=38

这个题目看论坛里有人讨论得不亦乐乎的,另外还有一堆各种代码的求解方法,我看了一下,发现直接用数学逻辑推理就可以出结果了,简单描述如下:

题目是说将一个(正)整数分别是(1,2,……,n)相乘,然后将乘积连起来,在所有得到的这些结果中,只考虑由1-9这9个数字组成(每个数字仅出现一次)的结果,问最大的结果是多少?

分析:

题目已经给了一个例子:918273645。所以最大的可能要比这个大。因为第一个乘数总是1,而9位数中比918273645大的自然也是以9开头。所以最大的结果对应的整数必须也是以9开头的。

然后我们简单看一下长度。如果是两位数的,其格式为9x,第二个乘积格式为18x(不能为19x),同理,第三个乘积格式为27x(不能为28x),这样前面三个乘积加起来是8位数,无论如何也比一个9位数要小,而再加多一个乘积又会超出9位数的限制。那么如果是三位数呢?其格式为9XX,第二个乘积格式为18XX(同样不能为19XX),这时候前两个乘积连在一起已经有7位数了,而第三个乘积是个4位数,也不满足要求。另一方面,显然,位数不能大于等于5。因此,我们的结论是,这个整数是四位数。

到这里我们知道这个整数的格式为9abc,第二个乘积格式为18efg,并且9abc×2=18efg。因为千位不能进位,所以a只能是2,3或4。

若a=2,则92bc×2=18efg,因此g必须是偶数。这时候我们只剩下4或6了,对应的c为2(重复舍去)或3,

无论如何都不会向十位进位,必然导致f也只能为偶数。这样我们得到92b3×2=18e46,这时b=2,又重复了。故a不能取2。

上面的分析有问题,修正如下:

若a=2,则92bc×2=18efg,因此g必须是偶数。这时候我们只剩下4或6了。若取g=6,则c可以取3或8(舍去),分析同上;若取g=4,则c可以取7或2(舍去)。对应地e取5或4(舍去),剩下的只有b=6,f=3,得到一组解为9267*2=18534,串起来就是926718534。

若a=4,则94bc×2=18efg。很明显,e只能为8或9,这都将重复。

这时a只能取3了,有93bc×2=18efg,e只能为6或7。这时g同样为偶数,考虑到c不能取3,因此只有g=4,而对应得c=7,这样e取6,

也就是说百位不能有进位,在剩下的2和5当中,就只有b取2了,最后的f取5。

上面的分析有问题,修正如下:

若a=3,则93bc×2=18efg,因此g必须是偶数。这时候我们只剩下2或4或6了。若取g=2,只有c=6,从而e=7,剩下的5和4无论如何都无法使得等式成立。若取g=6,对应地c取2或8均重复。这样就只有g取4,然后分析同上。

最终的结果为为9327×2=18654。把两个乘积连起来,答案就是932718654。

打赏

发表评论

邮箱地址不会被公开。 必填项已用*标注