By

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

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

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

联系作者

By

原题链接 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。

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

解答：

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

联系作者

By

原题链接 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),一分钟之内可以得出结果，也就没想再优化了。

联系作者

By

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

Factorial digit sum

n! means n (n 1) … 3 2 1

For example, 10! = 10 9 … 3 2 * 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

n!的意思是 n (n - 1) … 3 2 * 1

例如,10! = 10 9 … 3 2 * 1 = 3628800,

在10！这个数中的数字之和是 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

求100！这个数中的数字之和。

解答：

这题没什么好说的，没找到什么规律。只好算出100！用Python很随意。

联系作者

By

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

Counting Sundays

You are given the following information, but you may prefer to do some research for yourself.

  • 1 Jan 1900 was a Monday.
  • Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine.
  • A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.
    How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

计算星期天的天数

你将得到如下信息，你也可以自己做些探索。

  • 1900年1月1日是星期一

  • 一个月有三十天的月份有9月，4月，6月，11月。其它的月份都有31天，除了2月，如果是闰年29天，其它时候28天

  • 闰年是正好被4整除的年份，但不是世纪，除非此时它也可以被400整除。
    求二十世纪(1901年1月1日到2000年12月21日),一共有多少个星期天是每月的第一天。

解答：
这题没什么好说的，就是模拟，另外要知道怎么判断闰年。

联系作者

By

原题链接 http://projecteuler.net/problem=18
Maximum path sum I
By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

路径的最大和(1)

从下面的三角形顶部开始移动到下面一层相邻的数字，一直到底部，这条路径上的和为23.

也就是，3 + 7 + 4 + 9 = 23.

在下面的三角形中，找到从顶部到底部的路径的最大值

注意：在这个三角形中一共只有16384条从顶部到底部的路径，所以可以通过尝试每条路径来解决这个问题。但是，在问题67中，也是同样的问题，但是有100层，你不可能使用暴力方法，所以需要更聪明的方法!;0）

解答：
这题可以用动态规划。从下往上更容易一些。

联系作者

By

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

Number letter counts

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?
NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of “and” when writing out numbers is in compliance with British usage.

数字字母统计

如果数字1到5写成单词的话是：one,two,three,four,five,那么一共用了3 + 3 + 5 + 4 + 4 = 19个字母

如果将1到1000(one thousand)都写成单词，一共需要用多少个字母

注意：不需要统计空格和连字符。例如342(three hundred and forty-two)包括23个字母，115(one hundred and fifteen)包括20个字母. 当写数字时使用”and”是遵循英国写法。

解答：

这题没什么好说的，就是数字转化为英文单词。

联系作者

By

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

Lattice paths

Starting in the top left corner of a 2 2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20 20 grid?

格子路径

从2 * 2格子的左上角开始，只能右走和向下走，一共有6条路可以到达右下角。

求在20 * 20的格子中，一共有多少条路可以从左上角到右下角。

解答：
这题从数学的观点看是这样的，在2 2的格子中，一共要走4步才能从左上角到右下角，其中一定有两步是向下走，所以总共次数为 (C_4^2 = 6),对于20 20也可以这样计算。

联系作者

By

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

Longest Collatz sequence

The following iterative sequence is defined for the set of positive integers:

n ->n/2 (n is even)
n ->3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 -> 40 ->20 ->10 ->5 ->16 -> 8 -> 4 ->2 ->1
It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

最长的考拉兹数：

在正整数上定义如下迭代序列：

n -> n / 2 (n是偶数)

n -> 3n + 1 (n是奇数)
从13开始，使用上面的规则，我们将得到如下序列：
13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1
我们可以看到这个序列(从13开始到1结束)包含10个数。虽然这个还没有被证明(考拉兹问题),但我们可以认为所有的数都将在1结束。
求1 000 000以下的数，从哪一个数开始，产生的序列最长。
注意：一旦这个序列开始后，其中的数允许超过1 000 000。

解答：
如果将1到1000000都按照上述过程迭代，速度将会很慢，所以要保存一些计算结果，这样速度就会快很多了。
代码面前，了无秘密。直接上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/usr/bin/python
# -*- coding:utf-8 -*-
'''
Created on 2013-5-24

@author: shilong
@email: long470884130@163.com
'''
col = {}
col[1] = 1
def collatz(n):
    if n in col:
        return col[n]
    else:
        if n % 2 == 0:
            col[n] = collatz(n / 2) + 1
        else:
            col[n] = collatz(3 * n + 1) + 1
        return col[n]

联系作者