2017年03月12日

TypeScriptでProject Euler #12 「高度整除三角数」

   このエントリーをはてなブックマークに追加 Clip to Evernote

問題

三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
となる.

最初の7項について, その約数を列挙すると, 以下のとおり.

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる.

では, 500個より多く約数をもつ最初の三角数はいくつか.

どうやって解くか

約数の個数を求めるときに、1から順に割り切れるかどうかを調べていくのはあまりにも効率悪いので、 素数で割っていくことにします。結果的には素因数分解しているのと同じになりますね。

例えば、28 の場合、22×71 となって、 約数は、(1,2,4)と(1,7)を掛け合わせた組み合わせになるので、

1×1
1×7
2×1
2×7
4×1
4×7

で、1,7,2,14,4,28 の6個となります。 つまり、指数の2と1にそれぞれ1を加え、(2+1)*(1+1) を計算すればよいですね。

1176 の場合は、23 ×31 ×72 となって、 約数は、(1,2,4,8)と(1,3)と(1,7,49)を掛け合わせた組み合わせになるので、約数の数は、(3+1)×(1+1)×(2+1)=24になります。

このような考えで書いたのが「最初に書いたバージョン」でしましたコードです。以前のPrimesNumber.tsを使っています。

最初のバージョン

import * as Utils from './utils';
import { PrimeNumber } from './math/primenumber';

class Solver {
    exec(num: number): number {
        let ans = this.TriangleNumbers(n => {
            return num > this.CountFactors(n);
        });
        return ans;
    }

    //  三角数を列挙する
    private TriangleNumbers(callback: (number) => boolean): number {
        let tri = 0;
        let i = 1;
        while (true) {
            tri += i;
            if (!callback(tri))
                break;
            i++;
        }
        return tri;
    }

    // 約数の個数をカウントする
    private CountFactors(num: number): number {
        let count = 1;
        for (let p of PrimeNumber.enumerate()) {
            if (num === 1)
                break;
            let a = 1;
            while (num % p === 0) {
                num = num / p;
                a++;
            }
            count *= a;
        }
        return count;
    }
}

class Application {
    static run(): void {
        let sw = Utils.Stopwatch.startNew();
        try {
            let p = new Solver();
            let n = p.exec(500);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        } 
    }
}

Application.run();

予想どおり遅いです。 素数で割っても、素数の列挙が効率悪すぎるからですね。

素数はエラトステネスの篩で求めておきたいのだけれど、いくつまでの素数が必要なのかが事前にわからないため、馬鹿正直に列挙するバージョンである PrimeNumber.ts を使ったのですが、やはりだめでした。

改良

しかたないので、Primes クラス(エラトステネスの篩バージョン)を改良し、上限を指定せずに、素数を列挙し続けるようにします。以前 C#で書いたコード「C#:エラトステネスの篩(ふるい)再び」をもとにしています。

export class Primes {
    private static primes = [ 2, 3 ];
    private static ix = 0;

    public static * enumerate(): IterableIterator<number> {
        // 2,3は既知の素数とする
        //let primes = [ 2, 3 ];
        for (let i = 0; i < Primes.primes.length; i++)
            yield Primes.primes[i];

        // 4以上の整数から素数を列挙する。int.MaxValueを超えたときには対処していない
        //let ix = 0;
        while (true) {
            let prime1st = Primes.primes[Primes.ix];
            let prime2nd = Primes.primes[++(Primes.ix)];
            // ふるい用の配列の下限、上限を求め、配列を確保する。
            let lower = prime1st * prime1st;
            let upper = prime2nd * prime2nd - 1;
            // ふるいは、[4:8], [9:24], [25:48], [49:120]... と変化する。
            // []内の数値は、配列の下限と上限
            let sieve = []; //new BoundedBoolArray(lower, upper);
            for (let index = lower; index <= upper; index++)
                sieve[index- lower] = false;

            // 求まっている素数を使い、ふるいに掛ける 
            for (let i = 0; i < Primes.ix; i++) {
                let prime = Primes.primes[i];
                let start = Math.ceil(lower / prime) * prime;
                for (let  index = start; index <= upper; index += prime)
                    sieve[index - lower] = true;
            }

            // ふるいに掛けられて残った値が素数。これを列挙する。
            // 併せて、求まった素数は、primesリストに記憶していく。
            // この素数が次のステップ以降で、ふるいに掛ける際に利用される。
            let newix = Primes.primes.length;
            for (let i = lower; i <= upper; i++) {
                if (sieve[i - lower] !== true) {
                    Primes.primes.push(i);
                }
            }
            for (let i = newix; i <= Primes.primes.length; i++) {
                yield Primes.primes[i];
            }
        }
    }
}

enumerateを複数回呼び出したときに、一から素数を求めなおすことにないように、staticメンバー primes配列に素数を記憶しておき、2回目以降はこの primes配列から素数を列挙するようにしています。この配列にある素数よりも大きい素数が必要な場合には、エラトステネスの篩を使い、素数を求めます。もちろんここで求めた素数は、primes配列に記憶しておきます。

この工夫がないと、最初のバージョンよりも数倍遅いという結果になってしまいました。C#だとそんなことはないと思うんだけどなー。

このprimes.tsを使い、Solverクラスを書き換えます。

import * as Utils from './utils'; 
import { Primes } from './math/primes';

class Solver { 
    exec(num: number): number { 
        for (let ans of this.TriangleNumbers()) {
            if (this.CountFactors(ans) > num) 
                return ans; 
        } 
        return -1; 
    }

    //  三角数を列挙する
    private * TriangleNumbers(): IterableIterator<number> {
        let tri = 0;
        let i = 1;
        while (true) {
            tri += i;
            yield tri;
            i++;
        }
    }

    // 約数の個数をカウントする
    private CountFactors(num: number): number {
        let count = 1;
        for (let p of Primes.enumerate()) {
            if (num === 1)
                break;
            let a = 1;
            while (num % p === 0) {
                num = num / p;
                a++;
            }
            count *= a;
        }
        return count;
    }
}

Applicationクラスは、そのまま変更ありません。これで、2倍ほど早くなりました。劇的な速度アップはなりませんでした。JavaScriptのyield文が遅いせいなのかな?


※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/52487151