Project Euler解题汇总 041 ~ 050 博客分类: 数学&编程 PHPScala.netF#J#
程序员文章站
2024-02-16 21:39:34
...
问题41: 解答见按字典顺序生成所有的排列,此处不再重复。
问题42:How many triangle words does the list of common English words contain?
答 案:162
问题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
问题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
问题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
问题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
问题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
问题48:Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.
题目简介:求1^1 + 2^2 + ... + 1000^1000末尾10位数字。
答 案:9110846700
问题49:
Find arithmetic sequences, made of prime terms, whose four digits are permutations of each other.
题目简介:数1487, 4817, 8147有以下性质:
1.它们都是素数
2.这三个数成等差数列
3.除了位置不同,组成它们的数字一样。
求出四位数中满足上述条件的另三个数,按从小到大连着输出。
答 案:296962999629
问题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
问题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)) }
推荐阅读
-
Project Euler解题汇总 001 ~ 012 博客分类: 数学&编程 ScalaHaskellPHPMatlab.net
-
Project Euler解题汇总 041 ~ 050 博客分类: 数学&编程 PHPScala.netF#J#
-
Euler Project解题汇总 031 ~ 040 博客分类: 数学&编程 ScalaPHPCC++C#
-
Project Euler解题汇总 051 ~ 060 博客分类: 数学&编程 PHPScala.netCC++
-
Euler Project解题汇总 031 ~ 040 博客分类: 数学&编程 ScalaPHPCC++C#
-
Project Euler解题汇总 023 ~ 030 博客分类: 数学&编程 ScalaPHP.netF#C
-
Project Euler解题汇总 001 ~ 012 博客分类: 数学&编程 ScalaHaskellPHPMatlab.net
-
Project Euler解题汇总 013 ~ 022 博客分类: 数学&编程 ScalaPHP.net编程算法
-
Project Euler解题汇总 023 ~ 030 博客分类: 数学&编程 ScalaPHP.netF#C
-
Project Euler解题汇总 041 ~ 050 博客分类: 数学&编程 PHPScala.netF#J#