Project Euler解题汇总 061 ~ 070
程序员文章站
2022-03-13 19:21:59
...
问题61:Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.
问题62:Find the smallest cube for which exactly five permutations of its digits are cube.
问题63:How many n-digit positive integers exist which are also an nth power?
问题64:How many continued fractions for N ≤ 10000 have an odd period?
问题65:
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.
问题66:
Investigate the Diophantine equation x^2 − D*y^2 = 1.
问题67:
Using an efficient algorithm find the maximal sum in the triangle?
问题68:What is the maximum 16-digit string for a "magic" 5-gon ring?
问题69:Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
问题70:Investigate values of n for which φ(n) is a permutation of n.
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) }
上一篇: phpmyadmin怎么安装