欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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
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))
}