Project Euler解题汇总 061 ~ 070

问题61：Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.

object Euler061 extends Application {
    val fun = Array( (n:Int) => n*(n+1)/2,
                     (n:Int) => n*n,
                     (n:Int) => n*(3*n-1)/2,
                     (n:Int) => n*(2*n-1),
                     (n:Int) => n*(5*n-3)/2,
                     (n:Int) => n*(3*n-2)
                   )
    def getNum(i:Int):Seq[(Int,Int)] = {
        val st = Stream.from(1).map{ n => (fun(i)(n),i) }
        st.dropWhile{ _._1 < 1000 }.takeWhile{ _._1 < 10000 }
    }
     
    val num = (0 until 6).flatMap(getNum).toArray
    val lst = new Array[List[Int]](num.size)
    for(i <- 0 until num.size){
        val tail = num(i)._1%100
        val idx  = num(i)._2
        var xs:List[Int] = Nil
        for(j <- 0 until num.size){
            val it = num(j)
            if(idx != it._2 && tail == it._1/100) xs = j::xs
        }
        lst(i) = xs
    }
    
    def sum(n:Int):Int = {
        def sum0(t:Int,d:Int,xs:List[Int]):Int = {
            if(d == 6) return if(t==n) 0 else -1
            else{
                if(xs.contains(num(t)._2)) return -1
                val ys = num(t)._2::xs
                if(lst(t).exists{ sum0(_,d+1,ys) >=0 }){
                    num(t)._1 + lst(t).map{ sum0(_,d+1,ys) }.find{ _ >=0 }.get
                }
                else -1
            }
        }
        sum0(n,0,Nil)
    }
    
    println(Stream.from(0).map(sum).find{ _>=0 }.get)
}

问题62：Find the smallest cube for which exactly five permutations of its digits are cube.

import java.util.Arrays.sort
import java.lang.Math.cbrt

object Euler062 extends Application {
    val MAX = 5
    var res = 345L
    var cnt = 0
    do{
        res += 1
        val cube = res*res*res
        val list = cube.toString.toArray
        sort(list)
        val uper = cbrt(list.foldRight(0L){ (c,s) => 10*s+c-'0' }).toLong
        cnt = 1
        var n = res + 1
        while(n <= uper){
            val array = (n*n*n).toString.toArray
            sort(array)
            if(list sameElements array) cnt += 1
            n += 1
        }
    }while(cnt != MAX)
    println(res*res*res)
}

问题63：How many n-digit positive integers exist which are also an nth power?

import scala.Math._

object Euler063 extends Application {
    val MAX = (log(10)/(log(10)-log(9))).intValue
    var cnt = 0
    for(p <- 1 to MAX;n <- 1 to 9){
        val b = n:BigInt
        if(b.pow(p).toString.size == p) cnt += 1
    }
    println(cnt)
}

问题64：How many continued fractions for N ≤ 10000 have an odd period?

import eastsun.math.Util._
object Euler064 extends Application {

    val res = 1.to(10000).filter{ continuedFractionOfSqrt(_,null) % 2 ==1 }.length
    println(res)
}

问题65：
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

object Euler065 extends Application {
    def a(n:Int) = 
        if(n == 1) 2
        else if(n%3 == 0) 2*n/3
        else 1
    
    def b(n:Int):(BigInt,BigInt) = {
        var num:BigInt = a(n)
        var den:BigInt = 1
        for(i <- 1 until n){
            var t = num*a(n-i) + den
            den = num
            num = t
        }
        (num,den)
    }
     
    var (x,y) = b(100)
    var res = x.toString.map{ _-'0' }.foldLeft(0){ _+_ }
    println(res)
}

问题66：
Investigate the Diophantine equation x^2 − D*y^2 = 1.

import eastsun.math.Util._
object Euler066 extends Application {
    val buf = new Array[Int](1000)
    var (res,max,d) = (2,3:BigInt,1)
    while(d <= 1000){
        val pd = continuedFractionOfSqrt(d,buf)
        if(pd > 0){
            val sq = Math.sqrt(d)
            var (x0,y0) = (sq:BigInt,1:BigInt)
            var (x1,y1) = ((buf(0)*sq+1):BigInt,buf(0):BigInt)
            val cnt = if(pd%2 == 1) 2*pd-1 else pd-1
            var idx = 1
            while(idx < cnt){
                var t = x1
                var a = buf(idx%pd)
                x1 = x1*a + x0
                x0 = t
                t  = y1
                y1 = y1*a + y0
                y0 = t
                idx += 1
            }
            if(x1 > max){
                max = x1
                res = d
            }
        }
        d += 1
    }
    println(res)
}

问题67：
Using an efficient algorithm find the maximal sum in the triangle?

import scala.io.Source._

object Euler067 extends Application {
    val num = fromFile("triangle.txt").getLines.map{ line =>
                   line.split("\\s+").map{ _.toInt }
              }.toList.toArray
    val path = new Array[Array[Int]](num.length)
    
    for(i <- 0 until path.length) path(i) = new Array[Int](i+1)
    
    for(i <- 0 until path.length) path(num.length-1)(i) = num(num.length-1)(i)
    
    for{row <- (path.length - 2) to 0 by -1;
        col <- 0 to row 
    } path(row)(col) = num(row)(col) +path(row+1)(col).max(path(row+1)(col+1))
    
    println(path(0)(0))
}

问题68：What is the maximum 16-digit string for a "magic" 5-gon ring?

import eastsun.math.Util._

object Euler068 extends Application {
    val its = Array.range(1,10)
    val buf = new Array[Int](10)
    buf(0) = 10
    do{
        Array.copy(its,0,buf,1,9)
        val sum = buf(8)+buf(9)+buf(1)
        val tag = 0.until(8,2).forall{i => buf(i)+buf(i+1)+buf(i+3) == sum}
        if(tag){
            val idx = 0.until(10,2).foldLeft(0){ (i,j) => if(buf(i)<buf(j)) i else j }
            val num = idx.until(idx+10,2).map{ i =>
                          buf(i%10)+""+buf((i+1)%10)+""+buf((i+3)%10)
                      }.mkString("")
            println(num)
        }
    }while(nextPermutation(its))
}

问题69：Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.

import eastsun.math.Util._
object Euler069 extends Application {
    var res = getPrimes(1000).foldLeft(1){(s,p) => if(s*p <= 1000000) s*p else s}
    println(res)
}

问题70：Investigate values of n for which φ(n) is a permutation of n.

import eastsun.math.Util._
import java.util.Arrays.binarySearch
import scala.util.Sorting._

object Euler070 extends Application {
    val MAX = 10000000
    val primes = getPrimes(MAX)
    def isPrime(n:Int) = binarySearch(primes,n) >= 0
    val phi = new Array[Int](MAX)
    phi(1) = 1
    var n = 2
    var rate = 0.0
    var res = 0
    while(n < MAX){
        if(isPrime(n)) phi(n) = n - 1
        else{
            var idx = 0
            while(n%primes(idx) != 0) idx += 1
            val p = primes(idx)
            val s = n/p
            phi(n) = if(s%p == 0) phi(s)*p else phi(s)*(p-1)
        }
        if(phi(n) > n*rate){
            val pa = phi(n).toString.toArray
            val pn = n.toString.toArray
            quickSort(pa)
            quickSort(pn)
            if(pa sameElements pn){
                rate = phi(n).floatValue/n
                res = n
            }
        }
        n += 1
    }
    println(res)
}