Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

 | 

2010-04-19

Project Euler #63

| 00:10 | Project Euler #63 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #63 - nitoyon.dispatchEvent(null)

5桁の数 16807 = 7^5は自然数を5乗した数である. 同様に9桁の数 134217728 = 8^9も自然数を9乗した数である.

自然数をn乗して得られるn桁の正整数は何個あるか?

Problem 63 - PukiWiki

特に工夫もなく 1乗から100乗ぐらいまで求めてみた。101乗以上にはないことは、10^n は n 桁を越えるし、9^n が n 桁より小さくなる閾値を越えたら、それ以上は見つからないはずなので証明できるだろう。結局、最大の n は 21 だった。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem63 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem63(){
        var n:int = 1;
        var result:Array = [];

        for (var i:int = 0; i < 100; i++) {
            var m:int = 1;
            while (true) {
                var num:Num = new Num(1);
                for (var j:int = 0; j < n; j++) { num.mul(m); }
                if (num.toString().length == n) {
                    result.push(m + "^" + n);
                } else if (num.toString().length > n) {
                    break;
                }
                m++;
            }
            n++;
        }

        t.text = result.length + "";
    }
}
}

class Num{
    private var digits:Array = [];
    private static const N:int = 5;
    
    public function Num(a:int){
        digits[0] = a;
        carry();
    }

    public function mul(a:int):Num{
        for(var i:int = 0; i < digits.length; i++){
            digits[i] *= a;
        }
        carry();
        return this;
    }

    private function carry():void{
        for(var i:int = 0; i < digits.length; i++){
            if(digits[i] >= Math.pow(10, N)){
                if(digits.length <= i + 1) digits[i + 1] = 0;
                digits[i + 1] += Math.floor(digits[i] / Math.pow(10, N));
                digits[i] %= Math.pow(10, N);
            }
        }
    }

    public function toString():String {
        var ret:String = "";
        for (var i:int = 0; i < digits.length - 1; i++) {
            var tmp:String = digits[i];
            while (tmp.length < N) tmp = "0" + tmp;
            ret = tmp + ret;
        }
        ret = digits[digits.length - 1].toString() + ret;
        return ret;
    }
}

Project Euler #92

| 23:06 | Project Euler #92 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #92 - nitoyon.dispatchEvent(null)

各桁の数を2乗して足し合わせて新たな数を作ることによって、作られる数字の列を考える。

例えば

  • 44 → 32 → 13 → 10 → 1 → 1
  • 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

のような列である。結果として1か89で無限ループに陥っている。

ここで、ある数から始めた列は1か89に到達することが分かっている。

では、10,000,000より小さい数で89に到達する数はいくつあるか。

Problem 92 - PukiWiki

何も考えずに1000万回ループするだけ。いちおうメモ化してみてけど、しなくてもあまり速度には影響でないと思う。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem92 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem92(){
        var n:int = 1;
        var result:int = 0;
        var cache:Object = {
            89: 1,
            1: -1
        };
        var a:Array = [];

        setTimeout(function():void {
            for (var i:int = 0; i < 5000; i++) {
                if (n >= 10000000) {
                    t.text = result.toString();
                    return;
                }

                var m:int = n;
                do {
                    if (cache[m] > 0) { result++; }
                    if (cache[m] != null) {
                        cache[n] = cache[m];
                        break;
                    }

                    m = getNext(m);
                } while (true);
                n++;
            }

            t.text = result + "/" + n;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function getNext(i:int):int {
        var ret:int = 0;
        while (i > 0) {
            ret += Math.pow(i % 10, 2);
            i /= 10;
        }
        return ret;
    }
}
}
 |