038. 全数字乘积(pandigital multiples)

用数字192分别乘以1,2,3可以得到:

$$ 192\times1=192\\ 192\times2=384\\ 192\times3=576 $$
把每个乘积前后相接,我们可以得到一个全数字192384576。我们把192384576称为192和(1,2,3)的拼接乘积。

类似的,我们可以用数字9乘以1,2,3,4和5得到全数字918273645,是9和(1,2,3,4,5)的拼接乘积。

求用一个整数和\((1,2,3\cdots,n)\),其中\(n>1\)形成的拼接乘积中最大的1至9的全数字。

分析:题目中给出了918273645这个拼接乘积,所求的全数字必然要大于这个数字,所以所求的全数字的首位数必然是九。此外,这个乘积是也是一位数所能构成的最大拼接乘积,因此我们可以直接考虑两位数。假设这个两位数是9A的形式,用它乘以(1,2,3)得到的拼接乘积形式为9A18B27C是一个八位数,不可能是一个全数字;假如用其乘以(1,2,3,4)得到的拼接乘积是9A18B27C36D的形式,是一个十一位数,也不可能是一个全数字,所以满足题目要求的整数不可能是一个两位数。同理,设我们有一个三位数9AB,则其与(1,2)的乘积为9AB18CD的形式,共有七位数;其与(1,2,3)的拼接乘积为9AB18CD27EF的形式,共有十一位数,不可能是一个全数字,因此所求整数也不是一个三位数。

接下来,我们看四位数,设其形式为9ABC,则其与(1,2)的拼接乘积为9ABC18DEF的形式,共有九位数,有可能成为一个全数字。依次类推,我们可以发现五位数及以上的整数的形成的拼接乘积都要超过九位数,不可能是全数字,所以唯一能够形成九位数全数字的拼接乘积只能是四位数。通过观察四位数拼接乘积的形式,我们可以发现:第一,当9ABC与2相乘时,可能由于A的数值太大,导致相乘时前一个数字进位,形成9ABC19DEF的形式,出现了两个九,不符合题目要求,则A最大不应该超过4,否则必然会出现进位,则我们搜寻的最大的四位数应该是9487;第二,观察拼接乘积的形式,我们发现其中必然会出现一,则9ABC中不能出现一,否则也会违反全数字的要求,则这个四位数最小只能为9234。因此,我们只需要在9234和9487之间进行筛选,待筛选数字仅有254个。

def is_pandgital(x):
    digits_set = set(str(x))
    if digits_set == set(str(123456789)):
        return True
    return False

def main():
    for p in range(9487,9233,-1):
        ans = int(str(p) + str(p*2))
        if is_pandgital(ans):
            return ans