欧拉工程第三十一至四十题解题思路分析

三十一、硬币之和(coin sums)

英格兰的货币单位由英磅和便士构成,并且日常流通的共有八种硬币:

$$ 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p),£2 (200p) $$
两英磅可以由以下方式构成:
$$ 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p $$
求使用以上八种硬币,组成两英磅的方式共有多少种?

分析:这是一首典型的动态规划入门问题,可以用动态规划的方式来解决。首先我们要把所求问题分解成一个规模更小的问题。我们从一便士开始,我们只能用一便士来组成一便士,所以组成一便士的方法只有一种。再来看二便士,我们可以用两个一便士或者一个二便士来组成二便士,所以组成二便士的方法有两种。对于三便士,可以选用的只能是一便士和二便士两种硬币,我们可以用三个一便士或者一个一便士一个两便士两种方法组成三便士。对于以上的观察,我们可以画一个表格:

img

表格中行表示我们想要的构成的货币量,列则为我们能够使用的硬币,表格中的数字即为方法数,比如第三行第二列表示只能使用一便士和二便士的情况下,要组成三便士共有两种方法。通过观察这个表格我们可以发现,第一行和第一列都是一,第一行都是一是因为构成一便士只有一种方法,第一列是一是因为如果只允许使用一便士,那么任何货币量都只能用一种方法构成。这个表格也是我们在分析动态规划问题中经常会使用的表格,用行表示我们的目标,用列表示不断缩小的问题规模,而行和列对应的数字即为我们想要优化的数值,通过观察表格中数值之间的相互关系,我们就可以分析出动态规划问题中的问题分解方式或者说状态转移方程。

比如当我们要求构成四便士共有多少种方式,我们可以用四便士减去两便士等于两便士,然后我们查看表格中构成两便士的方法有几种,答案是两种,分别是两个一便士和一个两便士,在它们基础上各加上一个两便士,就可以得到构成四便士的两种方法,两个一便士加上一个两便士,和两个二便士。此外我们知道总可以用四个一便士来组成四便士,所以很容易得到组成四便士的方法有三种。如果只允许使用一便士和二便士,我们可以用类似的方法推出组成五便士的方法有三种,如果允许使用五便士,则组成五便士的方法有三种,因为可以用一个五便士。至此我们可以总结如下:设表格中的第\(i\)行第\(j\)列对应的方法数量为\(w(i,j)\),那么我们有:\(w(0,j)=1,w(i,0)=1,coins=[1,2,5,10,20,50,100,200]\),则:

上述关系可以进一步简化为:

$$ w(i,j)= \begin{cases} w(i,j-1)+w(i-coins[j],j)& i\ge coins[j]\\ w(i,j-1)& i< coins[j] \end{cases} $$

根据以上的递推关系式,我们可以使用自上而下或者自下而上的动态规划的方式求解该问题。在我写的两个算法中,自上而下的方式性能表现更好。不过我把两种方法都列出来,以供参考。

# top-down method, time cost = 88.6 ns ± 0.468 ns

from functools import lru_cache

@lru_cache(maxsize=128)
def ways(x,y=8):
    coins = [1, 2, 5, 10, 20, 50, 100, 200]
    if x == 1 or y == 1:
        return 1
    elif x < coins[y-1]:
        return ways(x,y-1)
    else:
        return ways(x,y-1) + ways(x-coins[y-1],y)

# bottom-up method, time cost = 221 µs ± 686 ns

def dp(target=200):
    coins = [1, 2, 5, 10, 20, 50, 100, 200]
    d = {i:1 for i in range(target+1)}
    for j in range(1,len(coins)):
        for i in range(coins[j],target+1):
            d[i] = d[i] + d[i-coins[j]]
    return d[target] 

三十二、全数字乘积(pandigital products)

如果一个\(n\)位数的各位数恰好包含了从\(1\)\(n\)的所有数字各一次,我们就可以说这个数字是一个全数字,比如五位数15234是一个从1至5的全数字。

乘积7524是独特的,因为\(39\times186=7254\),将乘数、被乘数和乘积结合起来刚好构成一个从1至9的全数字。求所有乘数、被乘数和乘积可以构成从1至9的全数字的乘积的和。

提示:有些满足条件的乘积可以通过多种方式产生,确保它们在计算总和时只被包含了一次。

分析:这道题相对比较容易,解题的核心在于缩小搜寻乘数和被乘数的范围。经过简单的分析只有当乘数是一位或两位数,对应被乘数是四位或三位数时,乘积是四位数,从而三者加起来共有九位数。由于乘法满足交换律,我们要避免进行重复核对,假设的所求的乘数和被乘数为\(i\)\(j\)\(i<j\),则\(i\)的筛选范围是\([1,99]\)。如果\(i\)是一位数,则\(j\)的范围是\([1234,10^4/i)\);如果\(i\)是两位数,则\(j\)的范围是\([123,10^4/i)\)

确定筛选范围后,我们将乘数、被乘数和乘积转化为字条串并拼接在一起,如果形成的字符串长度为9且包含从一至九的所有数字,则该乘积满足条件,从而添加到所求结果的集合中,避免出现重复的乘积结果,最后对集体加总即为所求。

def main():
    res = set()
    for i in range(1,100):
        start = 1234 if i <=9 else 123
        for j in range(start,10000//i):
            s = str(i) + str(j) + str(i*j)
            if len(s) == 9 and set(s) == set('123456789'):
                res.add(i*j)
    return sum(res)

三十三、抵消分数(digit cancelling fractions)

分数\(49/98\)是一个好奇分数,因为一个没有经验的数学家在化简它的时候可能会不正确的在分子分母同时划掉\(9\),即\(49/98=4/8\),但是结果却是正确的。我们认为像\(30/50=3/5\)这样的分数是平凡的,在这里不做考虑。只有四个非平凡的好奇分数,满足分数值小于一且分子分母都是两位数。将这四个非平凡的好奇分数相乘,并取其最简形式,求其分母的值。

分析:假设我们所求分数的分子为\(n\),分母为\(d\),由于分数值必须小于一,则有\(1\le n<d\le9\);同时假设我们想要约去的数为\(i\),则有\(1\le i\le9\)。因此该分数对应的原好奇分数有四种可能的形式:

$$ 1)\frac{10i+n}{10i+d}=\frac{n}{d}\\ 2)\frac{10n+i}{10d+i}=\frac{n}{d}\\ 3)\frac{10i+n}{10d+i}=\frac{n}{d}\\ 4)\frac{10n+i}{10i+d}=\frac{n}{d} $$

我们来看一下以上四种形式是否都可以成立。首先第一种形式:

$$ \frac{10i+n}{10i+d}=\frac{n}{d}\Leftrightarrow 10di+nd=10ni+nd \Leftrightarrow d=n $$

和题目要求相矛盾,不成立。再来看第二种形式:

$$ \frac{10n+i}{10d+i}=\frac{n}{d} \Leftrightarrow10nd+di=10nd+ni \Leftrightarrow d=n $$

和第一种形式一样,也不成立,再看第三种形式:

$$ \frac{10i+n}{10d+i}=\frac{n}{d}\Leftrightarrow10di+nd=10nd+ni\Leftrightarrow 9d(n-i)=i(d-n) $$

由于\(d>n\),所以要使得上式成立,则\(n>i\),对上式简单变换:

$$ n-i=\frac{i}{9}-\frac{in}{9d} $$

由于\(n>i\)\(n,i\in N\),则等式左边的\(n-i\)必然大于一;又由于\(i\le9\),则\(i/9\le1\),则等式右边必须要小于一,两相矛盾,则第三种形式也不成立。综上,满足题目要求的只能是第四种形式,则有:\(d(10n+i)=n(10i+d)\),对满足这一条件的进行筛选,对满足条件的分数分子分母分别相乘,并从分母中除以分子分母的最大公约数,即为所求。

from math import gcd

def main():
    nom,den = 1,1
    for i in range(1,10):
        for d in range(1,i):
            for n in range(1,d):
                if d*(10*n+i) == n*(10*i+d):
                    nom *= n
                    den *= d
    return den/gcd(nom,den)

三十四、数字阶乘(digit factorials)

\(145\)是一个好奇数,因为\(1!+4!+5!=1+24+120=145\),求所有这样的好奇数字之和。

注:因为\(1!=1\)以及\(2!=2\)都不是和,所以不包括在内。

分析:这道题的解题思路和第三十题的非常相似,也就是先通过好奇数需要满足的条件确定一个合理的上界,然后在上界之内寻找符合要求的值并求和即可。回忆我们在第三十题中的分析思路,假设符合要求的数字\(n\)总共有\(d\)位,则\(10^{d-1}<n<10^d\)。此外,由于该数字等于它各位数的阶乘之和,则各位数的阶乘之和最大只能为\(d\cdot9!\),即\(n<d\cdot9!\),综合上面的两个条件我们有:

$$ 10^{d-1}<d\cdot9! \Leftrightarrow d-1<log(9!)+log(d) \Leftrightarrow d-log(d)<log(9!)+1 $$

解此不等式,我们有\(d<7.43\),因为\(d\)为整数则\(d\)最大为7。因此有:

$$ n<7\cdot 9!=2540160 $$

根据上式,所求数字的首位数只能是1或者2,则可进一步把上界缩小为\(2!+6\cdot9!=2177282\),经过分析,我们还可以进一步缩小上界,不过对于题目中的数字规模,这个上界已经足够了。

from math import factorial

def main():
    fac_dict = {str(n):factorial(n) for n in range(10)}
    res = 0
    for i in range(10,2177282):
        if sum([fac_dict[x] for x in str(i)]) == i:
            res += i
    return res

三十五、圆形素数(circular primes)

数字197是一个圆形素数,这是因为所有它各位数的轮换197,971以及719也都是素数。一百以下总共有十三个这样的素数,包括:2,3,5,7,11,13,17,31,37,71,73,79和97。求一百万以下有多少个这样的圆形素数?

分析:首先我们来看一下如何尽可能的缩小待筛选的素数范围。题目已经给出一百以下的所有素数,所以一百以下的的素数不需要再做筛选,只需要考虑一百至一百万之间的所有素数,共有78473个。其次,除二以外的所有素数均为奇数,所以个位数不能是偶数且不为能为五,因为个位数为五的数字可以被五整除,又由于我们这里所求的圆形素数要求一个素数的所有轮换必须都为素数,任何数位上的数都会轮换到个位数上,这就要求整个数字的数位中不能包括偶数和五,只能包括1、3、7、9四个数字的至少两个。比如对于素数262147,做一次轮换就变成621472是一个偶数,不满足圆形素数的条件。为此,我们可以使用集合推导式,要求素数各个位数构成的集合是集合{1,3,7,9}的一个子集,可以将待筛选的素数从78473个降低到1099个。

为了计算特定素数的所有轮换,我们需要编写一个函数,它将特定的数字转化为对应的字符串,并将字符串的第一位拼接到剩余字符串的末尾,如此循环下去只到遍历所有数位,最后将一个数字的所有轮换存入到集合中并返回。在正式进行筛选时,我们只需要对上述满足条件的1099个素数进行筛选,依次检测素数的所有轮换是否为素数,只要有一个不是素数,则停止检测剩下的轮换,并从素数集合中去掉该素数的所有轮换,以避免之后重复检测。如果一个素数的所有轮换都为素数,则是满足条件的圆形素数并保留在集合中。最后我们计算该集合的元素个数并加上一百以下的十三个数,则为一百万以下的所有圆形素数的个数。

from sympy import sieve,isprime

def rotate_set(num):
    s = str(num)
    res = {num}
    for i in range(len(s)):
        new = s[1:] + s[0]
        res.add(int(new))
        s = new
    return res

def main():
    primes = set(sieve.primerange(100,1e6))
    digitset = {'1','3','7','9'}
    res_set = {i for i in primes if set(str(i))<=digitset}
    for ele in res_set:
        x = rotate_set(ele)
        for i in x:
            if isprime(i) == False:
                res_set = res_set-x
                break
    return len(res_set)+13

三十六、双基回文数(double-base palindromes)

十进制数585对应的二进制表示是1001001001,这两个数字都是回文数。求一百万以下十进制和二进制表示都是回文数的所有数字之和。(注意在两种进制下,回文数的首位都不能为零)

分析:此题至少有两种解法,第一种可以利用我们在第四题里已经编写的检验数学是否是回文数的函数,遍历一百万以下的所有数字,计算它的二进制表示,并分别检测十进制和二进制表示是否都是回文数,如果都是则加入到总和中,最后的总和即为所求。这种方法在我的电脑大约耗时640毫秒,尚可以接受,不过我们还有一种效率更高的算法。

我们可以考虑如下回文数的生成过程,比如说数字123可以生成两个回文数,分别是123321和12321。通过观察我们可以发现,每个数字都可以生成两个对应的回文数。不过根据题目要求,我们需要保证生成的回文数不能大于一百万,因此999是满足这个条件的最大数,它可以生成999999这个回文数,是一百万以下最大的回文数。因此,我们不需要遍历一百万以下的所有数字,而只需要遍历1到999这999个数字,可以将搜寻的规模缩小一千倍。

我们需要编写一个生成回文数的函数,它生成原数字对应的两个回文数。此外我们需要编写一个检测数字是否是回文数的函数,这个函数在第四题我们已经编写过了,这里引用即可。然后我们遍历从1至999的所有数字,生成两个对应的回文数并检测这两个回文数的二进制表示是否也为回文数,如果是则加入到总和中,最后的总和即为所求。执行这种算法在我的电脑上大约需要花费2.5毫秒,所耗时间大约缩小了256倍。

def make_palindrome(x):
    s = str(x)
    p1 = s + s[::-1]
    p2 = s + s[:-1][::-1]
    return int(p1),int(p2)

def main():
    is_palindrome = lambda x : x[-1]!=0 and x == x[::-1]
    res = 0
    for i in range(1,1000):
        p1,p2 = make_palindrome(i)
        p1_base2,p2_base2 = bin(p1)[2:],bin(p2)[2:]
        if is_palindrome(p1_base2):
            res = res + p1
        if is_palindrome(p2_base2):
            res = res + p2
    return res

三十七、可截短素数(truncatable primes)

数字3797有一个有趣的性质:它自己是一个素数,同时我们可以从左至右逐步截断这个数字,得到3797,797,97和7,它们也都是素数。同样,我们也可以从右至左逐步截断这个数字,得到3797,379,37和3也都是素数。求仅有的十一个从左至右和从右至左都可以截短的素数之和(注:2,3,5和7不被认为是可截短素数)。

分析:题目已经说明2,3,5,7不是可截短素数,所以我们只需要对10以上的素数进行判断。首先我们需要编写一个判断某数学是否是双边可截短素数的函数,按从左到右以及从右到左的顺序依次截短某个数字,并判断截短后的数字是否是素数,如果不是,则返回假;如果所有截短数字都是素数,则满足双边可截短数的条件,返回真。

题目并没有给出双边可截短素数的上界,只说了只有十一个这样的数字,但为筛选特定范围的素数,我们仍然需要一个上界,这个上界需要保证我们能产生所有十一个双边可截短素数。经过尝试,一百万是一个符合要求的上界,因此我们可以据此生成从十到一百万的所有素数。对于两位数的素数,我们直接调用上面编写的函数判断其是否为双边可截短素数。对于三位数以上的素数,我们还可以发现一些条件能缩小筛选的范围,提高筛选的速度。

首先,由于可截短素数最后都会截短到只剩一位数,则三位及以上的可截短素数的首位和末尾数字必须是素数,又由于末尾是二或者五的数字必可以被二或五整除,所以为了保证每次截短后的数必然是素数,则首位和末尾数字只能是三或者七。其次,同样为了保证截短的数为数字,数字中的所有数位都不能有偶数以及五,因此只能出现一、三、七、九这四个数字。从数学角度说,这要求各数位数字构成的集合是集合{1,3,7,9}的一个子集。通过以上条件,我们可以将待筛选素数的范围从七万多降低两百多,大大减小了筛选范围。在判断满足以上两个条件后,我们再用上面的函数来检测数字是否是双边可截短素数。如果是,则对计数值累加一,同时对求和值进行累加,当计数值达到十一后,我们停止循环,并返回最后的求和值,即为所求。

对于可截短数字更完整系统的介绍可以参见维基百科

from sympy import isprime,sieve

def is_twoside_truncatable_prime(x):
    s = str(x)
    for i in range(1,len(s)):
        if not isprime(int(s[i:])) or not isprime(int(s[:i])):
            return False
    return True

def main():
    num,ans = 0,0
    for i in sieve.primerange(10,1e6):
        if i < 100 and is_twoside_truncatable_prime(i):
            num += 1
            ans += i
        elif i>=100:
            s = str(i)
            cond1 = (s[0]=='3' or '7') and (s[-1]=='3' or '7')
            cond2 = set(s)<={'1','3','7','9'}
            if cond1 and cond2 and is_twoside_truncatable_prime(i):
                num += 1
                ans += i
        if num>=11:
            return ans

三十八、全数字乘积(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

三十九、整数直角三角形(integer right triangles)

如果\(p\)是一个整数边\(\{a,b,c\}\)的直角三角形的周长,对于\(p=120\)仅有三个符合要求的解:

$$ \{20,48,52\},\{24,45,51\},\{30,40,50\} $$
求使得符合要求的解的数量最大的\(p\)值,其中\(p\le1000\)

分析:此题的解题思路相对直接,据题意我们有\(a+b+c=p\),则\(c=p-a-b\),则有:

$$ a^2+b^2=c^2=(p-a-b)^2=p^2+a^2+b^2-2pa-2pb+2ab $$

则可以得到:

$$ b=(p^2-2pa)/(2p-2a) $$

则所有使得\(b\)为整数的\(p\)\(a\)都可以满足题目的要求,从而可以得到一组符合要求勾股三元数。此外,不失一般性,我们假设\(a\le b<c\),又因为\(a+b+c=p\),则应有\(a<p/3\),这可以缩小我们需要筛选的数\(a\)的范围。据此,我们可以编写一个计算特定周长下有多少对勾股三元数的函数。

题目要求\(p\le 1000\)时满足条件的勾股三元数对最多的\(p\)值,则我们只需要把不同的\(p\)代入上面的函数,算出对应的勾股数对的数量,最后统计勾股数对最多的对应周长即可。但考虑到题目的性质,我们可以对需要筛选的\(p\)值范围再做精减,假设:

据此,我们可以得出结论:\(p\)必然为一个偶数,则我们只需要筛选1000以下的所有偶数周长即可,缩小了一半的筛选范围。

def number_of_solution(p):
    num = 0
    for a in range(1,p//3):
        if (p**2-2*p*a)%(2*p-2*a) == 0:
            num += 1
    return num

def main(n=1000):
    d = {p:number_of_solution(p) for p in range(2,n+1,2)}
    ans = max(d,key=d.get)
    return ans

四十、钱珀努恩数(Champernowne’s constant)

十进制下的钱珀努恩数可以通过将所有正整数前后相接来构成:

$$ 0.123456789101112131415161718192021... $$
可以看出来小数点后的第十二位数是一。如果\(d_n\)代表小数点后的第\(n\)位数,求以下表达式的值:
$$ d_1\times d_{10} \times d_{100} \times d_{1000} \times d_{10000} \times d_{100000} \times d_{1000000} $$

分析:由于这道题的问题规模比较小,最大只需要求第一百万位数字,所以可以直接使用暴力破解的方法,先生成一个足够长的满足要求的字符串,再求取相应位置上的数字相乘即可,这种方法在我的电脑上大约耗时4.8秒。但是如果问题规模进一步扩大,这种方法将变得非常缓慢,所以我们可以对问题进一步深入分析,找到更高效的算法。

通过分析钱珀努恩数的规律,我们可以发现它小数点后的构成方法如下:首先是九个一位数、然后是九十个二位数,再是九百个的三位数,依次类推。根据这个规律,我们可以推断出每个位数的从第几位开始,到第几位结束,比如一位数从第一位开始,到第九位结束;二位数的区域共有九十个数,因此需要占180个位置,则应该在第189位结束;三位数区域共有九百个数,需要占2700个位置,则应该在第2889位结束。依次类推,我们可以推算出每个区域开始和结束的位置。

一般的,要求第\(n\)位数\(d_n\),假设其所处区域是\(k\)位数的区域,我们可以求出这个区域的位数范围,设这个范围的上界为\(U\),则:

$$ U(k)=\sum_{i=1}^{k}i\cdot(10^i-10^{i-1})=9\sum_{i=1}^k i\cdot10^{i-1}=10^{k}(k-\frac{1}{9})+\frac{1}{9} $$

根据这个公式,我们可以计算出特定位数的位置区域如下:

img

假设我们要求第一千位的数,因为\(189<1000<2889\),则其应该处在三位数的区域,也就是说\(k=3\)。在确定\(k\)以后,我们可以很方便的确定\(U(k)\)\(U(k-1)\),则第\(n\)位和其所在区域的上一个区域的上界之间共有\(D=(n-U(k-1))\)个数位,假设\(D\)除以\(k\)的商为\(m\)且余\(r\),则所求第\(n\)位数所在的整数\(T=10^{k-1}+m+1\),而\(d_n\)就等于数\(T\)的第\(r\)位数,即为所求。总结一下上面的计算步骤:

通过以上的算法优化,解决题目中的问题在我的电脑上需要花费36微秒,相比于暴力破解的方法,所用时间缩短了约133333倍。

def get_k_pub(n):
    previous_bound = lambda k : 10**k*(k-1/9)+1/9
    k = 1
    while previous_bound(k)<n:
        k += 1
    return k,int(previous_bound(k-1))

def get_digit(n):
    if n < 10:
        return n
    elif n >= 10:
        k,pub = get_k_pub(n)
        m = (n-pub) // k
        r = (n-pub) % k
        t = 10**(k-1) + m + 1
        dn = int(str(t)[r-1])
        return dn

def main():
    n = [10**x for x in range(7)]
    ans = 1
    for i in n:
        ans *= get_digit(i)
    return ans