首页 > Project Euler > Project Euler个人解答(Problem 21~30)

Project Euler个人解答(Problem 21~30)

2013年12月18日 发表评论 阅读评论

pe_banner_light好吧,继续,第三篇。。。

我的渺小的愿望就是在有生之年赶上官网进度的80%。。。。

题目翻译摘自Project Euler 中文翻译站

Problem 21:Amicable numbers

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

翻译:
d(n)定义为n 的所有真因子(小于 n 且能整除 n 的整数)之和。
如果 d(a) = b 并且 d(b) = a, 且 a ≠ b, 那么 a 和 b 就是一对相亲数(amicable pair),并且 a 和 b 都叫做亲和数(amicable number)。

例如220的真因子是 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 和 110; 因此 d(220) = 284. 284的真因子是1, 2, 4, 71 和142; 所以d(284) = 220.

计算10000以下所有亲和数之和。

思路:
唉,暴力解决吧。。不过关于这个amicable pair的相关,大家有兴趣的可以看看这个:http://primes.utm.edu/glossary/page.php?sort=AmicableNumber

另外,说一句,其实这道题本身有很多细节可以做编程上的优化的,像空间换时间的方法之类的。。但是最后代码就会比较“臃肿”。。反正题目数量级比较小,就无所谓啦~

Code:Python

def d(n):
    sum = 0;
    for i in range(1,int(sqrt(n))+1):
        if mod(n,i)==0:
            sum += (i+n/i*(i!=n/i));
    return sum-n

M = 10000;
sum = 0;
for i in range(1,M+1):
    d1 = d(i);
    if d1 != i and d(d1)==i:
        sum += (i+d1);
print sum/2

Problem 22:Names scores

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938×53 = 49714.

What is the total of all the name scores in the file?

翻译:
文件names.txt (右键另存为)是一个46K大小的文本文件,包含5000多个英文名字。利用这个文件,首先将文件中的名字按照字母排序,然后计算每个名字的字母值,最后将字母值与这个名字在名字列表中的位置相乘,得到这个名字的得分。

例如将名字列表按照字母排序后, COLIN这个名字是列表中的第938个,它的字母值是3 + 15 + 12 + 9 + 14 = 53。所以COLIN这个名字的得分就是938×53 = 49714.

文件中所有名字的得分总和是多少?

思路:
没有啥技巧性,就是考你编程文件,字符串操作而已。。

Code:Mathematica

namefile = Import["ID22.\\txt"];
namelist = StringCases[namefile, "\"" ~~ (x : LetterCharacter ..) ~~ "\"" -> x];
namelist = Sort[namelist];
Total@Table[i*Plus @@ (Flatten[ToCharacterCode@Characters[namelist[[i]]]] - 
      64), {i, 1, Length[namelist]}]

Problem 23:Non-abundant sums

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

翻译:
如果一个数的所有真因子之和等于这个数,那么这个数被称为完全数。例如,28的所有真因子之和为1 + 2 + 4 + 7 + 14 = 28,所以28是一个完全数。

如果一个数的所有真因子之和小于这个数,称其为不足数,如果大于这个数,称其为过剩数。

12是最小的过剩数,1 + 2 + 3 + 4 + 6 = 16。因此最小的能够写成两个过剩数之和的数字是24。经过分析,可以证明所有大于28123的数字都可以被写成两个过剩数之和。但是这个上界并不能被进一步缩小,即使我们知道最大的不能表示为两个过剩数之和的数字要比这个上界小。

找出所有不能表示为两个过剩数之和的正整数之和。

思路:
代码里面有注释

Code:Mathematica

(*判断是否是Non-abundant的函数*)
IsAbundantNum[n_] := Total@Divisors[n] - n > n;
(*计算所有Non-abundant数*)
AbundantNumList = Select[Range[28123], IsAbundantNum];
(*如果一个数和AbundantNumList的差与AbundantNumList之间交集为0,那么不可以分解成两个数的和*)
CanNotBeDevide[n_] :=
 Length[Intersection[n - AbundantNumList, AbundantNumList]] ==  0
(*计算结果*)
Select[Range[28123], CanNotBeDevide] // Total


Problem 24:Lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012 021 102 120 201 210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

翻译:
排列是一个物体的有序安排。例如3124是1,2,3,4的一种排列。如果所有的排列按照数值或者字母序排序,我们称其为一个字典序。0,1,2的字典排列有:

012 021 102 120 201 210

0, 1, 2, 3, 4, 5, 6, 7, 8,9的第100万个字典排列是什么?

思路:
Mathematica的话直接一行输出。
Python可以利用生成器很快的写一个出来,一直yield到需要的为止;
还有一个手动计算得方法,比如最高位,一定是9的阶乘个0,然后9的阶乘个1,这么下去,那么因为:

\(\dfrac{1000000}{9!}=2.75573\)


所以必然第1000000是以第三个数,也就是2开头的。
然后计算第1000000是2开头的第几个:

\(1000000-(9!\times 2)=274240\)


接下来,因为\(\dfrac{1000000-(9!\times 2)}{8!}=6.80159\),所以第二位必然是除去2以外的数中的第7个,也就是7。
然后不断这么计算下去。。这个算法效率会很高!!

Code:Python

def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;

c = 0;
for t in QPL(range(10)):
    c += 1;
    if c == 1000000:
        print t;
        break;

Code:Mathematica

Permutations[Range[0, 9]][[1000000]]

Problem 25:1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:
Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
Hence the first 12 terms will be:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
The 12th term, F12, is the first term to contain three digits.
What is the first term in the Fibonacci sequence to contain 1000 digits?

翻译:
以下是斐波那契数列的递归定义:
Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
那么其12项为:
F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144
因此第12项,F12,是第一个包含三位数字的项。

斐波那契数列中第一个包含1000位数字的项是第几项?

思路:
所以说,每次涉及到大数计算,总感觉用Python和Mathematica总有种愧疚感。。
不过也只能说,那些不支持大数计算的,其实不太适合快速做EP上的题目。。当然,你有超级巧妙的不用大数计算的情况除外。。

Code:Mathematica

NestWhile[# + 1 &, 1, Length@IntegerDigits@Fibonacci[#] < 1000 &]

Problem 26:Reciprocal cycles

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1
Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

翻译:
分子为1的分数称为单分数。分母是2到10的单分数用十进制表示如下:
1/2 = 0.5
1/3 = 0.(3)
1/4 = 0.25
1/5 = 0.2
1/6 = 0.1(6)
1/7 = 0.(142857)
1/8 = 0.125
1/9 = 0.(1)
1/10 = 0.1

其中0.1(6) 表示 0.166666...,因此它又一个长度为1的循环圈。可以看出1/7拥有一个6位的循环圈。

找出小于1000的数字d,1/d 的十进制表示含有最长的循环圈。

思路:
当除法余数和除数分别相同的时候,循环节出现。

Code:Python

def clyLen(n):
    cyl = [];
    k = 10;
    while([k,n] not in cyl):
        cyl.append([k,n])
        k = (k - int(k/n)*n)*10;
    return len(cyl)-cyl.index([k,n])
maxlen = 0;
idx = 0;
for i in range(1,1001):
    le = clyLen(i);
    if le <= maxlen:
        idx = i
        maxlen = le
print idx

Problem 27:Quadratic primes

Euler discovered the remarkable quadratic formula:

n2 + n + 41

It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 412 + 41 + 41 is clearly divisible by 41.

The incredible formula n² -79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, -79 and 1601, is 126479.

Considering quadratics of the form:

n² + an + b, where |a| < 1000 and |b| < 1000

where |n| is the modulus/absolute value of n
e.g. |11| = 11 and |-4| = 4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

翻译:

欧拉曾发表过一个著名的二次公式:

n² + n + 41

这个公式对于0到39的连续数字能够产生40个质数。但是当 n = 40时,402 + 40 + 41 = 40(40 + 1) + 41能够被41整除。当n = 41时, 41² + 41 + 41显然也能被41整除。

利用计算机,人们发现了一个惊人的公式:n²-79n + 1601。这个公式对于n = 0 到 79能够产生80个质数。这个公式的系数,-79 和1601的乘积是-126479。

考虑如下形式的二次公式:

n² + an + b, 其中|a| < 1000, |b| < 1000

其中|n| 表示 n 的绝对值。
例如, |11| = 11, |-4| = 4
对于能够为从0开始的连续的n产生最多数量的质数的二次公式,找出该公式的系数乘积。

思路:
第一种最容易想到的方法就是暴力解决是吧~下面的代码就是暴解的。

但是其实还有另外一种比较取巧的方法,就是手算。其思想来源于这个《MathWorld: Prime-Generating Polynomial》,因为通过分析题目我们就知道,n²-79n+1601对于n从0取到79都成立!【下面讲到的“成立”就是指连续产生质数】然而,这个式子也完全等价于(n-40)²+(n-40)+41;

既然我们知道n²+n+41对n从0取到39成立,那么就知道n²-79n+1601必然对40取到79成立,但是我们还知道n²-79n+1601除了40~79,它还对0~39成立,说明,n²+n+41还对-40到-1成立!!

再然后,假设我们有表达式(n-k)²+(n-k)+41,其中0 < k < 40,那么就会有这个式子对于-40+k到39+k成立,因为题目只对大于0的感兴趣,所以必然有39+k+1个质数。

化简(n-k)²+(n-k)+41得到n²+(1-2k)n+(k²-k+41),所以我们化简以下式子:

|k²-k+41|<1000

得到:\(k< \dfrac{1+\sqrt{3837}}{2}=31.4718\);

所以得到k=31;

Code:Python

def isPrime(n):
    if n <= 1:
        return False
    for i in xrange(2,int(n**0.5+1)):
        if n%i == 0:
            return False;
    return True;

def GetPrimeLength(a,b):
    cc = 0;
    n = 0;
    while(isPrime(n*n+a*n+b)):
        n += 1;
        cc += 1;
    return cc
    

maxprimecoe = -1;
abset = [-1000,-1000];
for a in range(-1000,1001):
    for b in range(-1000,1001):
        curl = GetPrimeLength(a,b)
        if curl < maxprimecoe:
            maxprimecoe = curl;
            abset = [a,b]
            print maxprimecoe
print maxprimecoe,abset

Problem 28:Number spiral diagonals

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  10
19  6  2  11
18  5  12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

翻译:
从数字1开始向右顺时针方向移动,可以得到如下的5×5的螺旋:

21 22 23 24 25
20  7  10
19  6  2  11
18  5  12
17 16 15 14 13

可以算出对角线上数字之和是101.

1001×1001的螺旋中对角线上数字之和是多少?

思路:
稍微观察一下,就可以发现数的变化规律了,前后的差分别是:

2,2,2,2,4,4,4,4,6,6,6,6,8,8,8,8...

所以程序也就很好写了。。。

当然,这道题很适合高中数学日渐退步的同学练练手算。。

Code:Python

Layer = 1001;
L = (Layer-1)/2;
sum = 1;
cur = 1;
step = 2;
for i in range(1,int(L)+1):
    sum += cur*4+step*10
    cur += step*4
    step += 2
print sum

Problem 29:Distinct powers

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

翻译:
考虑 ab 在 2 ≤ a ≤ 5,2 ≤ b ≤ 5下的所有整数组合:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125
如果将这些数字排序,并去除重复的,我们得到如下15个数字的序列:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

ab 在 2 ≤ a ≤ 100,2 ≤ b ≤ 100 下生成的序列中有多少个不同的项?

思路:
暴力解决还是挺轻松的~

Code:Python

sets = []
for a in range(2,101):
    for b in range(2,101):
        t = a**b;
        if t not in sets:
            sets.append(t)
print len(sets)

Problem 30:Digit fifth powers

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

翻译:
令人惊奇的,只有三个数能够写成它们各位数的四次方之和:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44
1 = 14没有被算作在内因为它不是一个和。

这些数字的和是 1634 + 8208 + 9474 = 19316.

找出所有能被写成各位数字五次方之和的数之和。

思路:
首先我们需要确定要查找的范围的上限,这个很好找,因为n位数的话最大值就是10n-1,而各位数字五次方之和最大就是n95
我们可以划一下这两条曲线,就知道我们暴力解决的搜索上限是多少了:EP-PRO30

Plot[{10^x - 1, 9^5x}, {x, 1, 6}]

发现上限绝对不可能大于400000,然后暴搜就可以了。。

Code:Mathematica

Select[Range[1, 400000], Plus @@ (Power[#, 5] & /@ IntegerDigits[#]) == # &]
Total[%] - 1

【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

  • 红薯

    pe23:With[{a = Select[Range@28123, DivisorSigma[1, #] > 2 # &]}, Compile[{}, Block[{t = Range@28123}, Do[t = Complement[t, i + a], {i, a}]; t]][] ] // Tr // AbsoluteTiming pe30:Pick[#, # - Total[IntegerDigits[#]^5] & /@ #, 0] &@Range[2, 10^6] // Tr // AbsoluteTiming Sum[If[n == Total[IntegerDigits ^5], n, 0] , {n, 2, 10^6}] // AbsoluteTiming

    • 23题用do和Complement来实现这个想法好厉害。。。

    • 其实有时候我不是很敢用sum,因为感觉不是很好判断sum什么时候可以算得出来,什么时候算不出来。。

      • 红薯

        Sum有些时候能自动编译,Pick可以充分利用向量化,Select要加速一般需要手动Compile

    • 看到30题想到一个问题像请教一下:不知大大有没有遇到过这种情况,就是对于&定义纯函数的时候,经常纯函数里面套纯函数,然后最里层的#就不知道应该是属于哪一层的了,这种时候我一般就改用Function函数来标记一下变量名,不知道有没有别的方法?【不知道我说清楚了没?

      • 红薯

        还可以用With、Table等