Project Euler Solutions(Problem 1~7)

时间:2021-07-18 17:02:32

Project Euler 1-7

原地址如下
https://projecteuler.net/about
翻译题目地址如下:
http://pe.spiritzhang.com/index.php/2011-05-11-09-44-54
有点怀念做题的感觉,就从这开始吧(嘿嘿,PE大神都做过肯定会有答案滴,不会卡死),关键是一定要坚持下去,有进步有收获。~w_w~
默认使用Mathematica(Mma 9)实现,使用Python(2.7.2)会特别说明。


Problem 1 Multiples of 3 and 5

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3 or 5 below 1000.

译:10以下的自然数中,属于3和5的倍数的有3,5,6和9,它们之和是23. 找出1000以下的自然数中,属于3和5的倍数的数字之和。

思路:1000内3的倍数,5的倍数加起来减去15的倍数。
比较笨的法1:

Sum[n*3, {n*3, {n, 1, N[999/3, 1]}]+
Sum[n*5, {n, 1, N[999/5, 1]}] - Sum[n*15, {n, 1, N[999/15, 1]}]

想起来用列表更好,参考Map的例子,有了法2:
Project Euler Solutions(Problem 1~7)

Total[#] & /@ {Range[3, 999, 3], Range[5, 999, 5], -Range[15, 999, 15]} // Total

看到还有暴力解决的法3:

Total@Union@Flatten@Append[Range[3, 999, 3], Range[5,999, 5]]

Problem 2 Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

译:斐波那契数列中的每一项被定义为前两项之和。从1和2开始,斐波那契数列的前十项为: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … 考虑斐波那契数列中数值不超过4百万的项,找出这些项中值为偶数的项之和。

参考NestWhile的例子,有法1:
Project Euler Solutions(Problem 1~7)

Total@Select[Table[Fibonacci[n], {n, 1, NestWhile[(# + 1) &, 1, Fibonacci[#] < 4000000 &]}], EvenQ]

发现项数为3的倍数均为偶数。

Table[Fibonacci[n], {n, 20}]
{1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765}

也可以这样写法2:

m = NestWhile[(# + 1) &, 1, Fibonacci[#] < 4000000 &];
Total@Take[Table[Fibonacci[n], {n, 1, m}], {3, m, 3}]

Problem 3 Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

译:13195的质数因子有5,7,13和29. 600851475143的最大质数因子是多少?

参考Sort的例子,暗喜这里不用写排序函数了。有法1:
Project Euler Solutions(Problem 1~7)

First[#] & /@ Sort@FactorInteger[600851475143] // Last

他人的法2:

Sort[FactorInteger[600851475143], First &] // Last // First

好严谨,看着也顺眼。


Problem 4 Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99. Find the largest palindrome made from the product of two 3-digit numbers.

译:一个回文数指的是从左向右和从右向左读都一样的数字。最大的由两个两位数乘积构成的回文数是9009 = 91 * 99. 找出最大的有由个三位数乘积构成的回文数。

Select[Union@Flatten@Map[#*Range[100, 999] &, Range[100, 999]], 
   IntegerDigits[#] == Reverse[IntegerDigits[#]] &] // Sort // Last

列表制造的那个部分好像可以写的简单些。

Table[i*j, {i, 100, 999}, {j, 110, 999}]

Problem 5 Smallest multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

译:2520是最小的能被1-10中每个数字整除的正整数。 最小的能被1-20中每个数整除的正整数是多少?

最先想到的是暴力破解,有法1:

NestWhile[# + 1 &, 1, Or[! IntegerQ[#/Range[10]] &]]

写着是简单,运行了好久好久……也没出来。
貌似可以把1~20所有里面每个质因数的最高的次直接相乘。
直接参考吧,他人的法2:

Times @@ Power @@@ 
  Function[p, (Select[
        Flatten[FactorInteger /@ Range[2, 20], 1], #[[1]] == p &]~
       SortBy~Last) // Last] /@ Select[Table[i, {i, 2, 20}], PrimeQ]

知道LCM(最小公倍数)的存在就变成了酱紫,心已死无力吐槽。

Apply[LCM, Range[20]]

Problem 6 Sum square difference

The sum of the squares of the first ten natural numbers is, 12+22+...+102=385 The square of the sum of the first ten natural numbers is, (1+2+...+10)2=552=3025 Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640. Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

译:前十个自然数的平方和是: 12+22+...+102=385 前十个自然数的和的平方是: (1+2+...+10)2=552=3025 所以平方和与和的平方的差是3025 − 385 = 2640. 找出前一百个自然数的平方和与和平方的差。

暴力破解so easy,法1:

Sum[i, {i, 1, 100}]^2 - Sum[i^2, {i, 1, 100}]

据数学公式 k2(1+k)4k(k+1)(2k+1)6 ,有法2:

k = 100; 1/4 k^2 (1 + k)^2 - 1/6 k (k + 1) (2 k + 1)

Problem 7 10001st prime

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10 001st prime number?

译:前六个质数是2,3,5,7,11和13,其中第6个是13. 第10001个质数是多少?

写这个题的时候,对Mma的爱就又多了一点。

Prime[10001]