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.

Brute Force,当然如果n为0时,可知b必为素数.还可以试图代入n = 1等,得出a,b相应性质,减小复杂度

-59231

Source:C++

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

brute force,没什么好说的

55

Source:C++

The decimal number, 585 = \(1001001001_2\) (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

872187

Source:C++

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

问题的关键只要找出上界就行.跟Project Euler Problem 30 类似,设上界为n位数字,则

\(10^n\) < 9! * n

易知n最大为7,更确切的说其上界为 9! * n = 2540160;
剩下的就是遍历查找了

40730

Source:C++

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.

上界很明显为28123

1. 计算到上界为止所有数的和,记为sum,并将abundant数保存
2. 将abundant数两两相加,如不大于上界,则将这两数的和记为可以表示为abundant数相加,即不满足题意要求的数
3. 所有可表示为abundant数相加的数其和记为abundantsSum
4. 所求答案即为 sum - abundantsSum

4179871

Source:C++

Consider all integer combinations of \(a^b\) for 2 \(\leq\) a \(\leq\) 5 and 2 \(\leq\) b \(\leq\) 5:

\(2^2\) =4, \(2^3\) =8, \(2^4\) =16, \(2^5\) =32 \(3^2\) =9, \(3^3\) =27, \(3^4\) =81, \(3^5\) =243 \(4^2\) =16, \(4^3\) =64, \(4^4\) =256, \(4^5\) =1024 \(5^2\) =25, \(5^3\) =125, \(5^4\) =625, \(5^5\) =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 \(a^b\) for 2 \(\leq\) a \(\leq\) 100 and 2 \(\leq\) b \(\leq\) 100?

Set集合

9183

Source:C++

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 in triangle.txt (right click and ‘Save Link/Target As…’), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10¹²) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

请查看Problem 18

7273

Source:C++

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits: \begin{eqnarray*} 1634 = 1^4 +6^4 + 3^4 + 4^4 \ \end{eqnarray*} \begin{eqnarray*} 8208 = 8^4 + 2^4 + 0^4 + 8^4 \ \end{eqnarray*} \begin{eqnarray*} 9474 = 9^4 + 4^4 + 7^4 + 4^4 \ \end{eqnarray*} As 1 = \(1^4\) 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.

很直接,关键是找出上界.个位数是不符合题意的。我们检查多少位时其位数上的值的五次方的和不能表示相应的位数.我们可以看到,到7位数时,其最大就只能表示413343,更不用说8位,9位等了.故上界为354294

\begin{eqnarray*} 9^5 + 9^5 = 118098 \ \end{eqnarray*} \begin{eqnarray*} 9^5 + 9^5 + 9^5 = 177147 \ \end{eqnarray*} \begin{eqnarray*} 9^5 + 9^5 + 9^5 + 9^5 = 236196 \ \end{eqnarray*} \begin{eqnarray*} 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 295245 \ \end{eqnarray*} \begin{eqnarray*} 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 354294 \ \end{eqnarray*} \begin{eqnarray*} 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 + 9^5 = 413343 \ \end{eqnarray*}

443839

Source:C++

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?

看到排列组合的问题,立马就想到了用排列组合的数学方法来求解。
只需要高中数学的知识即可,计算过程如下:
9!*2 <＝ 1000000 < 9!*3
最高位为从小到大排列未被使用的第三位数字2
1000000 – 9!*2 = 274240

8!*6 <＝ 27420 < 8!*7
现在数字2已经被使用,故从小到大排列未被使用的第七位数字为7
27420 – 241920 = 32320

…..

按这个过程计算出来的为2783915604,但这并不是真正所求的,而是所求序列的下一个。很容易知道2783915604序列的前一个数为2783915460

2783915460

Source:C++