Project Euler解题汇总 023 ~ 030

　　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){ _+_ }