原题链接 http://projecteuler.net/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.

数字的5次幂

令人惊奇的是只存在3个数可以写成数的每位数字的4次幂的和

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

这里1 = 14 不是和所以没有包括进来

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

求所有满足数的每位数字的5次幂等于数本身这个条件的数的和

解法:

没什么好说的。

原题链接 http://projecteuler.net/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中,唯一的数有多少个?

解法:

这里用一个set来存。数学方法还没想到。

原题链接 http://projecteuler.net/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 8 9 10
19 6 1 2 11
18 5 4 3 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 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

可以验证对角线上的数之和为101

求以相同形式构成的1001 * 1001的螺旋数的对角线之和。

解答:

这题没什么好说的,就是找规律。

原题链接 http://projecteuler.net/problem=27

Quadratic primes

Euler discovered the remarkable quadratic formula:

n² + 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, 41² + 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

当n从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的绝对值
e.g. |11| = 11 and |-4| = 4

求对于这个二项式表达式,从n = 0开始,连续产生最多素数的系数a和b的乘积。

解法:

这题没什么好说的,先用筛法生成一个素数判断表,之后就是遍历了。

原题链接 http://projecteuler.net/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/7有6个循环数字.

求d < 1000中 1/d包含最多循环数字的那个d.

解法:

这题还没想好。

更新于2013年8月15日:问题解决了,现在才知道,如果尝试自己去实现表示无穷小数,就会发现规律。

原题链接 http://projecteuler.net/problem=25

1000-digit Fibonacci number

The Fibonacci sequence is defined by the recurrence relation:

F(n) = F(n-1)+ F(n-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?

1000个数字的斐波纳契数

斐波那契数列由如下递归关系定义:

F(n) = F(n-1)+ F(n-2), 且 F1 = 1 ,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项,即是第一个包含三个数字的项

求数列中第一个包含1000个数字的项

解法:

用第二题中的方法,生成斐波那契数列,之后判断。

原文链接 http://projecteuler.net/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的字典序排列中第一百万个排列。

解法:

写一个函数,用非递归方法生成下一个排列,具体方法到算法书找。有了这个函数后,一个循环就可以搞定。

 

原题链接 http://projecteuler.net/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的所有整数都可以写成两个盈数之和。然而,通过分析,无法推断出这个上限,即使已经知道不能被表示成两个盈数之和的数中最大的数不会超过这个限制。

求所有不能被表示成两个盈数之和的正整数之和。

这题没什么好说的,直接算就是了。

原题链接 http://projecteuler.net/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, 字母值为3 + 15 + 12 + 9 + 14 = 53,在姓名表中为第938个,最终,

COLIN的得分为938 * 53 = 49714。

求文件中所有姓名的得分总和。

解答:

这题没什么好说的,将名字排序,默认就是字典序了,然后按照说明算就行了。

原题链接 http://projecteuler.net/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组成亲和数对,a和b都被称为亲和数。

例如,220的真因子有1,2,4,5,10,11,20,22,44,55和110,则d(220) = 284。284的真因子是1,2,4,71和143,所以d(284) = 220。

找到1000以内所有亲和数的和。

解答:

这题我没想到好的方法,暴力解决,复杂度为 O(n^2),一分钟之内可以得出结果,也就没想再优化了。