问题41: 解答见
按字典顺序生成所有的排列,此处不再重复。
问题42:How many triangle words does the list of common English words contain?
答 案:162
import java.util.Scanner
import java.io.File
import scala.Math.sqrt
object Euler042 extends Application {
var scan = new Scanner(new File("words.txt")).useDelimiter("\"(,\")?")
var res = 0
while(scan.hasNext()){
var word = scan.next()
var vle = word.foldLeft(0){ _+_-'A'+1 }
var idx = sqrt(2*vle)
if(idx*(idx+1) == 2*vle) res += 1
}
scan.close()
println(res)
}
问题43:Find the sum of all pandigital numbers with an unusual sub-string divisibility property.
题目简介:数字1406357289具有以下性质:
1.它是0~9的一个排列
2.记di为它的第i为数字(从左至右,i从1开始),则:
* d2d3d4=406 is divisible by 2
* d3d4d5=063 is divisible by 3
* d4d5d6=635 is divisible by 5
* d5d6d7=357 is divisible by 7
* d6d7d8=572 is divisible by 11
* d7d8d9=728 is divisible by 13
* d8d9d10=289 is divisible by 17
求所有具有上述性质的数字之和。
答 案:16695334890
import eastsun.math.Util._
object Euler043 extends Application {
val ps =Array(2,3,5,7,11,13,17)
def suit(arr:Array[Int]):Boolean = {
var num = arr.slice(0,3).foldLeft(0){ _*10+_ }
for(idx <- 3 until arr.length){
num =num%100*10 + arr(idx)
if(num % ps(idx-3) != 0) return false
}
true
}
var arr = Array(0,1,2,3,4,5,6,7,8,9)
var sum = 0L
do{
if(suit(arr)) sum += arr.foldLeft(0L){ _*10+_ }
}while(nextPermutation(arr))
println(sum)
}
问题44:Find the smallest pair of pentagonal numbers whose sum and difference is pentagonal.
题目简介:由公式
Pn=n(3n1)/2生成的数称为五角数,前10个五角数依次为:
1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...
易见,
P4 + P7 = 22 + 70 = 92 = P8。但他们的差
P7-P4=70-22 =48不是一个五角数。
现在要求两个五角数Pj与Pk使得他们的和与差(绝对值)都是五角数,并且使得他们差的绝对值
D = |Pj-Pk| 最小。输出D的值。
答 案:5482660
object Euler044 extends Application {
def isPenta(n:Int):Boolean = {
val v = 6*n
val s = Math.sqrt(v)
s%3 == 2 && s*(s+1) == v
}
def penta(n:Int) = n*(3*n-1)/2
var res = 0
var k = 1
while(res == 0){
val pk = penta(k)
var j = 1
while(j < k && res == 0){
val pj = penta(j)
if(isPenta(pk+pj) && isPenta(pk-pj)) res = pk - pj
j += 1
}
k += 1
}
println(res)
}
问题45:After 40755, what is the next triangle number that is also pentagonal and hexagonal?
题目简介:三角数,五角数,六角数的生成公式如下:
Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, ...
可以验证,T285 = P165 = H143 = 40755
求下一个既是三角数又是五角数与六角数的数字。
题目分析:易见,六角数一定是三角数,因此只需寻找下一个是五角数的六角数即可。
答 案:1533776805
//Scala
Stream.from(144).map{ n => n*(2*(n:Long)-1) }.find{ v =>
var sq = Math.sqrt(6*v).toLong
(sq+1)%3 == 0 && sq*(sq+1) == 6*v
}.get
问题46:What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
题目简介:Christian Goldbach提出过一个猜想:
任意一个奇合数都能写成一个平方数的两倍与一个素数之和。如:
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
但后来发现这个猜想是错误的。现在要求不满足上面猜想的最小的那个奇合数。
答 案:5777
object Euler046 extends Application {
var ps:Stream[Int] = Stream.cons(2,
Stream.from(3).filter{ n =>
ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
})
def isPrime(n:Int) = ps.takeWhile{ p => p*p<=n }.forall{ n%_ !=0 }
var res = 3
var end = false
do{
do{
res += 2
}while(isPrime(res))
val sq = Math.sqrt((res-2)/2)
end = 1.to(sq).forall{ n => !isPrime(res-2*n*n) }
}while(!end)
println(res)
}
问题47:Find the first four consecutive integers to have four distinct primes factors.
题目简介:对于自然数n,记f(n)为满足下列条件的最小的那个数:f(n),f(n)+1,...,f(n)+n-1这连续n个数,每个数恰好有n个不同的素因子。
比如:
f(2) = 14,
14 = 2 ×7
15 = 3 ×5
f(3) = 644
644 = 2² ×7× 23
645 = 3× 5× 43
646 = 2× 17× 19
现在要求f(4)
答 案:134043
import java.util.ArrayList
object Euler047 extends Application {
val ps:Stream[Int] = Stream.cons(2,
Stream.from(3).filter{ n =>
ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
})
def f(size:Int):Int = {
var buf = new ArrayList[Int]
buf.add(0)
buf.add(0)
var num = 2
var cnt = 0
while(cnt < size){
var copy = num
var first = ps.find{ copy%_ == 0 }.get
while(copy % first == 0) copy = copy/first
var vau = buf.get(copy)+1
buf.add(vau)
if(vau == size) cnt += 1
else cnt = 0
num += 1
}
num - size
}
println(f(4))
}
问题48:Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.
题目简介:求1^1 + 2^2 + ... + 1000^1000末尾10位数字。
答 案:9110846700
//Scala
val MAX = 10000000000L
def pow(n:Int):Long = 1.to(n).foldLeft(1L){ (p,i) => p*n%MAX }
1.to(1000).foldLeft(0L){ (s,i) => (s+pow(i))%MAX }
问题49:
Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.
题目简介:数1487, 4817, 8147有以下性质:
1.它们都是素数
2.这三个数成等差数列
3.除了位置不同,组成它们的数字一样。
求出四位数中满足上述条件的另三个数,按从小到大连着输出。
答 案:296962999629
import java.util.Arrays.{ binarySearch => find}
object Euler049 extends Application {
val ps:Stream[Int] = Stream.cons(2,
Stream.from(3).filter{ n =>
ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
})
val pa = ps.takeWhile{ _<10000 }.dropWhile{ _<=1487 }.toArray
def suit(a:Int,b:Int):Boolean = {
var buf =new Array[Int](10)
var tmp = a
while(tmp != 0){
buf(tmp%10) += 1
tmp = tmp/10
}
tmp = b
while(tmp != 0){
buf(tmp%10) -= 1
tmp = tmp/10
}
buf.forall{ _==0 }
}
var i = 0
var res = ""
while(res == "" && i < pa.length){
var j = i+2
while(res == "" && j < pa.length){
var mid = (pa(i)+pa(j))/2
if(find(pa,i,j,mid) >= 0 &&
suit(pa(i),pa(j)) &&
suit(pa(i),mid) ) res = ""+pa(i)+pa(j)
j += 1
}
i += 1
}
println(res)
}
问题50:
Which prime, below one-million, can be written as the sum of the most consecutive primes?
题目简介:素数41能写成连续6个素数之和:
41 = 2 + 3 + 5 + 7 + 11 + 13
现在要求1,000,000以内的素数,能表示为最多的连续素数之和的那个数。
题目分析:我这儿采取的是类似“迭代加深搜索”的算法:首先对“连续素数”的个数做一个上界估计,记为len。然后看1000000以内有没有len个连续素数其和也为素数,并且在1000000以内。如果有,这这个和就是解;否则,将len减1,继续上述操作。
答 案:997651
import java.util.Arrays.{binarySearch => indexOf}
import java.util.BitSet
import scala.collection.jcl.LinkedList
object Euler050 extends Application{
//var start = System.currentTimeMillis
/**
get all primes below bound
Sieve of Eratosthenes
*/
def getPrimes(bound:Int):Array[Int] = {
if(bound <= 2) return Array()
var set = new BitSet(bound)
var idx = 2
var lst = new LinkedList[Int]
lst.add(2)
while(idx < bound){
var sp = lst.last
var st = sp*2
while(st <= bound){
set.set(st)
st += sp
}
st = sp+1
while(st < bound && set.get(st)) st += 1
if(st < bound) lst.add(st)
idx = st
}
lst.toArray
}
val primes = getPrimes(1000000)
val last = primes(primes.length-1)
var len = primes.length/100
var res = 0
do{
var start = 0
var sum = start.until(start+len).foldLeft(0L){(s,i) => s+primes(i) }
var idx = indexOf(primes,start+len,primes.length,sum.toInt)
if(idx >= 0) res = sum.toInt
while(start+len < primes.length && sum <= last && res ==0){
sum = sum +primes(start+len)-primes(start)
idx = indexOf(primes,start+len,primes.length,sum.toInt)
if(idx >= 0) res = sum.toInt
start += 1
}
len -= 1
}while(res == 0)
//var end = System.currentTimeMillis
println(res)
//println("Use time(ms): "+(end-start))
}
分享到:
相关推荐
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 Project Euler 问题的解决方案 ###Problem 1 - 3 和 5 的倍数### 如果我们列出所有 10 以下是 3 或 5 的倍数的自然数,我们得到 3、5、6 和 9。这些倍数的和是 23。求1000 以下所有 3 或 5 的倍数之...
project-euler:多种语言的projecteuler.net问题解决方案
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 问题 摘自网站: “欧拉计划是一系列具有挑战性的数学/计算机编程问题,需要的不仅仅是数学洞察力来解决。虽然数学可以帮助你找到优雅有效的方法,但解决大多数问题...