RT,接着上次
Euler Project解题汇总 013 ~ 022继续贴我写的解题代码。题目的难度相比之前的大了一些,有些题不是看一眼直接就能想出正确的方法了。建议想做这些题的同学先自己做下再来看我写的代码。
题目23:
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
题目简介:首先引入一个数学中的概念(呵呵,普及下数学知识):
自然数n称为
盈数(又称过剩数abundant number),如果除n之外的正约数之和大于n。
譬如12是最小的盈数,因为:1+2+3+4+6 =16 > 12
已知数学中的一个结论:所有大于28123的自然数都能分解为两个盈数之和。现在要求所有不能分解为两个盈数之和的自然数之和。(有点绕口:-))
答案:4179871
//Scala
val MAX =28123
val fs = new Array[Boolean](MAX+1)
for(i <- 0 to MAX){
var k = 2
var s = 1
while(k*k < i){
if(i%k == 0) s =s+k+i/k
k += 1
}
if(k*k == i) s += k
fs(i) = s>i
}
var res =0
for(n <- 1 to MAX){
val f =1.to(n/2).forall{k => !(fs(k)&&fs(n-k)) }
if(f) res += n
}
res
题目24:What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
题目简介:将数字0, 1, 2, 3, 4, 5, 6, 7, 8 ,9的所有排列按字典顺序排序,求排在第1,000,000位的那个数字。(注意:从第一位记起)
譬如,数字0,1,2的所有排列按字典排序为:
012 021 102 120 201 210
第3位为 102
答案:2783915460
//Scala
def nth(n:BigInt,a:Array[Char]):String ={
var idx = a.length -1
var fac = 1.to(idx).foldLeft(1:BigInt){ _*_ }
var cpy = n
for(i <- 0 until idx){
var k = (cpy/fac).intValue
var t = a(i+k)
for(p <- (k+i).until(i,-1)) a(p) =a(p-1)
a(i) = t
cpy = cpy%fac
fac = fac/(idx-i)
}
String.valueOf(a)
}
nth(1000000-1,"0123456789".toCharArray)
问题25:
What is the first term in the Fibonacci sequence to contain 1000 digits?
题目简介:对于斐波那契数列:
F1 =1, F2 =1, Fn =Fn-1 +Fn-2 (n>=3)
求第一个为1000位数的项数。
答案:4782
//Scala
var fib:Stream[BigInt] = Stream.cons(1,Stream.cons(1,
fib.zip(fib.tail).map{case(x,y) => x+y}
))
fib.findIndexOf{ _.toString.length == 1000 }+1
问题26:
Find the value of d < 1000 for which 1/d contains the longest recurring cycle.
题目简介:我们知道有些分数不能用有限位的小数表示出来,那些分数的小数表示叫无限循环小数,其循环部分称为循环节,循环节的长度称为周期。
现在求小于1000的自然数d,使得1/d的循环周期最大。
譬如,d从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
其中d=7时的循环节为142857,其长度为6。
答案:983
//Scala
def cycle(n:Int):Int ={
var k:BigInt =10
var c =1
while((k-1)%n != 0){
k =k*10
c +=1
}
c
}
var max =0
var res =0
for( n <- 2 until 1000;if !(n%2==0||n%5==0)){
var c =cycle(n)
if(c>max){
max =c
res =n
}
}
res
问题27:
Find a quadratic formula that produces the maximum number of primes for consecutive values of n.
题目简介:对于整数a,b,定义函数 f:
f(n) = n*n + a*n +b
又记len(f)表示f(n)从n =0开始能连续生成素数(质数)的最大长度。也就是:
len(f) = max{n : f(0),f(1),...,f(n-1)都是素数}
现在对|a|<1000,|b|<1000,求a,b使得len(f)最大。
输出a,b的乘积
譬如: a =1,b =41的时候,f(n) =n^2+n+41。
f(0),f(1),...,f(39)都是质数,并且f(40)不是质数。
所以此时len(f) =40。 (这个式子是Euler发现的)
答案:-59231 (a = -61,b = 971)
//Scala
val ps:Stream[Int] = Stream.cons(2,
Stream.from(3).filter{ n =>
ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
})
def suit(a:Int,b:Int,n:Int):Boolean ={
val v = n*n+a*n+b
if(v <= 0) false
else ps.takeWhile{p =>p*p<=v}.forall{ v%_ !=0 }
}
var max = 40
var res = (1,41)
for(a <- -999 to 999;b <- ps.takeWhile{_<1000};if suit(a,b,max)){
var n =0
while(suit(a,b,n)) n += 1
if(n > max){
res =(a,b)
max =n
}
}
res._1*res._2
问题28:
What is the sum of both diagonals in a 1001 by 1001 spiral?
题目简介:将自然化按顺时针方向螺旋形依次排列形成一个方阵。
求这样的1001*1001的方阵的两条对角线上数字之和。
譬如,对于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。
答案:669171001
//Scala
var num =1
var res =1
for(k <- 2.until(1001,2);p <- 1 to 4){
num += k
res += num
}
res
问题29:
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
题目简介:对 2 ≤ a ≤ 100 ,2 ≤ b ≤ 100:a^b一共产生了多少个不同的数。
答案:9183
/**
&#Euler029.scala
@author Eastsun
*/
import scala.util.Sorting.quickSort
object Euler029 extends Application {
var buf =new Array[BigInt](99*99)
for(a <- 2 to 100;b <- 2 to 100){
var ba:BigInt =a
buf((a-2)*99+b-2) =ba.pow(b)
}
quickSort(buf)
var res =0
var pre:BigInt =0
for(n <- buf)
if(n != pre){
res += 1
pre = n
}
println(res)
}
(for(a <- 2 to 100; b <- 2 to 100) yield (a: BigInt).pow(b)).toSet.size
问题30:
Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.
题目简介:求所有能表示为其各位数字五次方之和的自然数的和。
注意:虽然1 = 1^5,但由于这不是“各位数字五次方之和”,所以不包括在内。
答案:443839
//Scala
10.to(1000000).filter{ n =>
var t =n
var s =0
while(t != 0){
var r =t%10
s += r*r*r*r*r
t = t/10
}
s ==n
}.foldLeft(0){ _+_ }
分享到:
相关推荐
NULL 博文链接:https://linuke.iteye.com/blog/1056283
ProjectEuler题1-16题代码,直接引入Eclipse就可以用
project euler代码库1,已测试通过
NULL 博文链接:https://lifethinker.iteye.com/blog/290159
solution to problem 5
Project Euler solutions in assembler.
NULL 博文链接:https://lampeter123.iteye.com/blog/423036
欧拉计划projecteuler.net
projecteuler.net 我对 Project Euler 问题的一些解决方案: :
project euler代码库第二部分(已测试通过
project euler代码库第三部分(已测试通过
project euler代码库第五部分(已测试通过
项目欧拉解决方案该存储库包含我对 Project Euler (projecteuler.net) 上发现的编程问题的所有答案。 每个解决方案都是用 Java 编写的,旨在从命令行运行。 解决方案文件中将提供指向相关欧拉问题的链接。 某些解决...
ProjectEulerQuestions projecteuler.net 上问题的解决方案
project-euler:多种语言的projecteuler.net问题解决方案
project_euler Project Euler 问题的解决方案 ###Problem 1 - 3 和 5 的倍数### 如果我们列出所有 10 以下是 3 或 5 的倍数的自然数,我们得到 3、5、6 和 9。这些倍数的和是 23。求1000 以下所有 3 或 5 的倍数之...
EulerPy是一种命令行工具,旨在简化使用Python解决Project Euler问题的过程。 该软件包着重于两个主要任务:首先,创建一个带有文档字符串的Python“模板”文件,该字符串包含Project Euler问题的文本,以便于参考...
Algorithm-hacktoberfest-projecteuler.zip,此repo包含多种语言的projecteuler问题的解决方案。为新来者特别设计,作为黑客节挑战的一部分。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
投影仪Project Euler 问题的解决方案,请参阅地位# 名称秒1 3 和 5 的倍数0.02 甚至斐波那契数列0.03 最大素因数0.94 最大的回文产品0.15 最小倍数2.56 和平方差0.07 第 10001 个素数0.1解决方案8 系列中最大的产品...
Project-Euler 我使用 C++ 解决 Project Euler 问题 摘自网站: “欧拉计划是一系列具有挑战性的数学/计算机编程问题,需要的不仅仅是数学洞察力来解决。虽然数学可以帮助你找到优雅有效的方法,但解决大多数问题...