ScalaでProject Euler（50） - inamori’s diary

単純に考えると99×99通りのべき乗があるのですが、重複があるのでそれより少ない数になります。どれだけ重複があるのかを考えるとこの問題は速く解けます。
例を考えましょう。

2⁸ = 4⁴ = 16²

ここでダブってカウントしないように、大きい底から小さい底に移行できる数がいくつあるかを数えましょう（例えば上の例で、16²→4⁴ 4⁴→2⁸ということです）。まず、N = 20で考えてみます。上で分かるように、底がべき乗になっている数に小さい底に移行できる可能性があります。20までのべき乗数は、4, 8, 9, 16です。4の場合、

4² = 2⁴, 4³ = 2⁶, ... , 4¹⁰ = 2²⁰

だから、重複は9個あります。
次に9ですが、

9² = 3⁴, 9³ = 3⁶, ... , 9¹⁰ = 3²⁰

4とまったく同じです。要するに、指数のみで個数が決まるということです。
8は、

8² = 2⁶ = 4³, 8³ = 2⁹, 8⁴ = 2¹2 = 4⁸, ...

ちょっと難しいですね。しかし、配列を作ってどの指数は重複しているか数えれば簡単です。
今度はN = 100で考えてみましょう。最も大きい指数は、64 = 2⁶で6乗です。6乗について考えると重複するのは、

64² = 2¹², 64³ = 2¹⁸, 64⁴ = 2²⁴, ... , 64¹⁶ = 2⁹⁶
64² = 4⁶, 64³ = 4⁹, 64⁴ = 4¹², ... , 64³³ = 4⁹⁹
64² = 8⁴, 64³ = 8⁶, 64⁴ = 8⁸, ... , 64⁵⁰ = 8¹⁰⁰
64² = 16³, 64⁴ = 16⁶, 64⁶ = 16⁹, ... , 64⁶⁶ = 16⁹⁹
64⁵ = 32⁶, 64¹⁰ = 32¹², 64¹⁵ = 32¹⁸, ... , 64⁸⁰ = 32⁹⁶

まず、2と4は考えなくてもいいことがわかりますね。16を考えるとよくわかります。16と64の指数で分数を作ると、4 / 6 = 2 / 3となり、64の指数は分子の2が公差で2/3*100=66までの等差数列になることがわかります。そうすると、底2は1/6、底4は1/3、底8は1/2とすべて公差が1で、範囲の広い底8だけが有効になります。

toMapでキーが重複するとき

println (List((2, 3), (2, 2), (2, 1)).toMap)

Map(2 -> 1)

最後の値が使われるようです。単に上書きするんでしょうね。

さて、下のコードでN = 10⁸まで答えが出ました。約60秒、メモリもギリギリです。

import scala.math
import scala.testing.Benchmark

def gcd(n :Int, m :Int) :Int =
    if(m == 0) n else gcd(m, n % m)

def pow(n :Int, e :Int) :Int =
    if(e == 0)
        1
    else {
        val m = pow(n, e / 2)
        if(e % 2 == 1)
            m * m * n
        else
            m * m
    }

// [n^(1/e)]
def int_root(n :Int, e :Int) = {
    def dec(m :Int) :Int =
        if(pow(m - 1, e) < n) m else dec(m - 1)
    
    def inc(m :Int) :Int =
        if(pow(m + 1, e) > n) m else inc(m + 1)
    
    val m = math.pow(n, 1. / e).toInt
    if(pow(m, e) > n) dec(m) else inc(m)
}

def divs(n :Int) =
    Iterator.range(1, n).filter(n % _ == 0)

def num_pows() = {
    val a = Iterator.from(2).map(int_root(N, _) - 1).takeWhile(0 <).toArray
    for(e <- Iterator.range(a.size + 1, 3, -1); e2 <- divs(e).drop(1))
        a(e2 - 2) -= a(e - 2)
    Iterator.range(0, a.size).map(a(_))
}

def fraction(num :Int, den :Int) = {
    val d = gcd(num, den)
    (num / d, den / d)
}

def count_overlap(e :Int) = {
    val a = new Array[Boolean](N + 1)
    val fs = List.range(1, e).map(fraction(_, e)).toMap.toList
    for((n, d) <- fs; k <- Iterator.range(n, N / d * n + 1, n))
        a(k) = true
    Iterator.range(2, N + 1).count(k => a(k))
}

val N = 1e8.toInt
def solve() = {
    val a = num_pows()
    val it = a.zip(Iterator.from(2).map(count_overlap))
    println ((N.toLong - 1) * (N - 1) - it.map(x => x._1.toLong * x._2).sum)
}

object Test extends Benchmark {
    def run() = solve
}

println (Test.runBenchmark(10))