Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

|

2010-04-18

Project Euler #43

| 01:09 | Project Euler #43 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #43 - nitoyon.dispatchEvent(null)

数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分語が面白い性質を持っている.

d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.

  • d2d3d4=406は2で割り切れる
  • d3d4d5=063は3で割り切れる
  • d4d5d6=635は5で割り切れる
  • d5d6d7=357は7で割り切れる
  • d6d7d8=572は11で割り切れる
  • d7d8d9=728は13で割り切れる
  • d8d9d10=289は17で割り切れる

このような性質をもつ0から9のPandigital数の総和を求めよ.

Problem 43 - PukiWiki

next_permutation を使って 10! 通りの全てに対して検証するだけ。和は32bitで収まらない点に注意。

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

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

    public function Problem43(){
        var n:Array = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
        var p:Array = [2, 3, 5, 7, 11, 13, 17];
        var sum:Number = 0;
        var result:Array = [];

        setTimeout(function():void {
            for (var j:int = 0; j < 10000; j++) {
                for (var i:int = 0; i < p.length; i++) {
                    if (parseInt(n.slice(i + 1, i + 4).join(""), 10) % p[i] != 0) break;
                }
                if (i == p.length) {
                    sum += parseFloat(n.join(""));
                    result.push(n.join(""));
                }

                if (!next_permutation(n)) {
                    t.text = sum.toString();
                    return;
                }
            }

            t.text = "calc... " + n.join("") + "\ncur sum: " + sum.toString() + "\n" + result.join("\n");
            setTimeout(arguments.callee, 10);
        }, 0);
    }
}
}

function next_permutation(arr:Array):Boolean {
    var len:int = arr.length;
    if (len <= 1) return false;

    var swap:Function = function(arr:Array, i1:int, i2:int):void {
        var tmp:int = arr[i1];
        arr[i1] = arr[i2];
        arr[i2] = tmp;
    };

    for (var i:int = len - 2; i >= 0; i--) {
        if (arr[i] < arr[i + 1]) {
            for (var j:int = len - 1; j > i; j--) {
                if (arr[i] < arr[j]) break;
            }

            swap(arr, i, j);

            for (j = 1; ; j++) {
                if (i + j >= len - j) break;
                swap(arr, i + j, len - j);
            }
            return true;
        }
    }
    return false;
}

Project Euler #46

| 01:44 | Project Euler #46 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #46 - nitoyon.dispatchEvent(null)

Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.

  • 9 = 7 + 2×1^2
  • 15 = 7 + 2×2^2
  • 21 = 3 + 2×3^2
  • 25 = 7 + 2×3^2
  • 27 = 19 + 2×2^2
  • 33 = 31 + 2×1^2

後に, この予想は誤りであることが分かった.

平方数の2倍と素数の和で表せない最小の奇合成数を答えよ.

Problem 46 - PukiWiki

素数でない奇数 n を順番に確認していく。n より小さい奇数素数で引いて、2で割って、平方根とったものが整数であれば表せる数となる。つまり n より小さい全ての奇数素数で引いて、2で割って、平方根とったものが整数にならなくなる最初の n を求めればよい。

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

public class Problem46 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const N:int = 1000000;
    private var primes:Array;
    private var _isPrime:Object;

    public function Problem46(){
        enumPrime();
    }

    private function doit():void {
        var n:int = 1;
        setTimeout(function():void {
            for (var i:int = 0; i < 100; i++) {
                n += 2;
                if (isPrime(n)) continue;

                if (isNg(n)) {
                    t.text = n + ""; return;
                }
            }

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

    private function isNg(n:int):Boolean {
        if (isPrime(n)) return false;
        for (var i:int = 1; i < primes.length; i++) {
            if (n < primes[i]) return true;
            var nn:Number = Math.sqrt((n - primes[i]) / 2);
            if (nn == int(nn)) return false;
        }
        throw new Error("overflow");
    }

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        _isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    _isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }

    private function isPrime(n:int):Boolean {
        if (n < N) return _isPrime[n];
        
        t.text = "overflow";
        throw new Error("overflow");
    }
}
}

2010-04-17

Project Euler #79

| 18:34 | Project Euler #79 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #79 - nitoyon.dispatchEvent(null)

オンラインバンクで通常使われるsecurity methodは, パスコードからランダムに選んだ3文字をユーザーに要求するものである.

たとえば, パスコードが531278のとき, 2番目, 3番目, 5番目の文字を要求されるかもしれない. このとき, 期待される答えは: 317 である.

テキストファイルkeylog.txtには, ログインに成功した50回の試行が記録されている.

3つの文字が常に順番通りに要求されるとするとき, ファイルを分析して, 可能なパスコードのなかでもっとも短いものを見つけよ.

Problem 79 - PukiWiki

プログラムじゃなく、脳内で解いてしまった。公式スレッドでも手で解いた人が多いようだ。パスコードに同じ数字が2つ以上含まれない前提ならコードにもしやすいが、そうじゃない場合だったとしたら悩ましい問題だ。

Project Euler #33

| 19:15 | Project Euler #33 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #33 - nitoyon.dispatchEvent(null)

49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.

我々は 30/50 = 3/5 のようなタイプ自明な例だとする.

1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある.

その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

Problem 33 - PukiWiki

分母・分子ともに2桁の数なので、10/11~98/99 を全て試せばOK。答えが少し意表をつく値だったので何かミスしたかと思ったが正解だった。不思議だ。

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

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

    public function Problem33(){
        var n:Array = [];
        var d:Array = [];
        for (var i:int = 10; i < 99; i++) {
            for (var j:int = i + 1; j < 100; j++) {
                if (i % 10 == 0 && j % 10 == 0) break;
                if (isOk(i, j)) {
                    n.push(i);
                    d.push(j);
                }
            }
        }

        var nn:int = 1, dd:int = 1;
        for (i = 0; i < 4; i++) {
            nn *= n[i];
            dd *= d[i];
        }
        var g:int = gcm(nn, dd);

        t.text = (dd / g) + "\n" + nn + "/" + dd + "\n" + n.join(",") + "\n" + d.join(",");
    }

    private function gcm(a:int, b:int):int {
        if (a < b) return gcm(b, a);
        if (a % b == 0) return b;
        return gcm(a - b, b);
    }

    private function isOk(i:int , j:int):Boolean {
        var arri:Array = [i % 10, int(i / 10)];
        var arrj:Array = [j % 10, int(j / 10)];
        for (var ii:int = 0; ii < 2; ii++) {
            for (var jj:int = 0; jj < 2; jj++) {
                if (arri[ii] == arrj[jj] && i / j == arri[1 - ii] / arrj[1 - jj]) {
                    return true;
                }
            }
        }
        return false;
    }
}
}

Project Euler #38

| 19:52 | Project Euler #38 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #38 - nitoyon.dispatchEvent(null)

192を1, 2, 3で掛けてみよう.

   192 × 1 = 192
   192 × 2 = 384
   192 × 3 = 576

積を連結することで1から9のPandigital数 192384576 が得られる. 192384576を 192と(1,2,3)の連結積と呼ぶ.

同じようにして, 9を1,2,3,4,5と掛け連結することでPandigital数918273645が得られる. これは9と(1,2,3,4,5)との連結積である.

整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ.

Problem 38 - PukiWiki

n > 1 ということなので、少なくとも 1 と 2 をかけなければいけない。つまり、10000 以上の数に 1, 2 の積を連結すると10桁を越えちゃうので、ありえない。そんなこんなで、1~9999 について調べるだけでよい。

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

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

    public function Problem38(){
        var n:int = 1;
        var result:int = 0;

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

                var s:String = "";
                for (var j:int = 1; j < 4; j++) {
                    s += n * j;
                    if (s.length >= 9) break;
                }

                if (s.length == 9 && s.split("").sort().join("") == "123456789") {
                    if (result < parseInt(s)) {
                        result = parseInt(s);
                    }
                }

                n++;
            }

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

2010-04-15

Project Euler #32

| 02:40 | Project Euler #32 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #32 - nitoyon.dispatchEvent(null)

7254は面白い性質を持っている. 39 × 186 = 7254と書け, 掛けられる数/掛ける数/積に1から9の数が1回ずつ出現する.

掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ.

HINT: いくつかの積は, 1通り以上の掛けられる数/掛ける数/積の組み合わせを持つが1回だけ数え上げよ.

Problem 32 - PukiWiki

1~9までの全順列について、a×b=c となるような分割が存在するかを調べている。

1つの並びについてa×b=c となるような分割が存在するかを調べるのは高々100回程度。これを 9! 回行うだけなので、計算時間もさほど多くはない。

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

public class Problem32 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private var products:Object = {};

    public function Problem32(){
        var arr:Array = [1, 2, 3, 4, 5, 6, 7, 8, 9];

        setTimeout(function():void {
            for (var i:int = 0; i < 5000; i++) {
                findProduct(arr.join(""));

                if (!next_permutation(arr)) {
                    var res:int = 0;
                    for (var n:String in products) {
                        res += parseInt(n);
                    }
                    t.text = res.toString();
                    return;
                }
            }

            t.text = "calc " + arr.join("");
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function findProduct(n:String):void {
        for (var i:int = 1; i < 9; i++) {
            for (var j:int = i + 1; j < 10; j++) {
                var a:int = parseInt(n.substr(0, i));
                var b:int = parseInt(n.substr(i, j - i));
                var c:int = parseInt(n.substr(j));
                if (a * b == c) products[c] = 1;
            }
        }
    }

    private function next_permutation(arr:Array):Boolean {
        var len:int = arr.length;
        if (len <= 1) return false;

        var swap:Function = function(arr:Array, i1:int, i2:int):void {
            var tmp:int = arr[i1];
            arr[i1] = arr[i2];
            arr[i2] = tmp;
        };

        for (var i:int = len - 2; i >= 0; i--) {
            if (arr[i] < arr[i + 1]) {
                for (var j:int = len - 1; j > i; j--) {
                    if (arr[i] < arr[j]) break;
                }

                swap(arr, i, j);

                for (j = 1; ; j++) {
                    if (i + j >= len - j) break;
                    swap(arr, i + j, len - j);
                }
                return true;
            }
        }
        return false;
    }
}
}

2010-04-14

Project Euler #23

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

ずっと放置していた問題。素直に書けばいいだけだった。

28123 以下の abundant number を求めて、任意の2個を足した集合を作って、1~28123 から引いて残った数を足し合わせるだけ。

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

public class Problem23 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
	private var N:int = 28123;

    public function Problem23(){
		var abundant:Array = [];
		for (var i:int = 1; i < N; i++ ) {
			if (isAbundant(i)) {
				abundant.push(i);
			}
		}

		var sum:Object = {};
		for (i = 0; i < abundant.length; i++) {
			for (var j:int = i; j < abundant.length; j++) {
				sum[abundant[i] + abundant[j]] = true;
			}
		}

		var result:int = 0;
		for (i = 1; i < N; i++) {
			if (!sum[i]) result += i;
		}

        t.text = result.toString();
    }

    private function isAbundant(n:int):Boolean {
    	var sum:int = 1;
    	for (var i:int = 2; i <= Math.sqrt(n); i++) {
    		if (n % i == 0) {
    			sum += i;
    			if (i != n / i) sum += n / i;
    		}
    	}

    	return sum > n;
    }
}
}

Project Euler #27

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

n² + an + b (|a|<1000, |b|<1000) のうち、n = 0, n = 1, n = 2... が素数となるもののうち、最長のものを与える a, b を求めよ、という問題。

素数を列挙して、全ての a, b の組み合わせについて、n = 0 から素数となるかどうか確認していくだけ。

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

public class Problem27 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const N:int = 1000000;
    private var primes:Array;
    private var _isPrime:Object;

    public function Problem27(){
        enumPrime();
    }

    private function doit():void {
        var a:int = -999, b:int = -999;
        var maxn:int = 0;
        var product:int = 0;

        setTimeout(function():void {
            for (var i:int = 0; i < 10000; i++) {
                if (a == 1000) {
                    t.text = product.toString();
                    return;
                }

                var n:int = 0;
                while (isPrime(n * n + a * n + b)) { n++; }
                if (n > maxn) {
                    maxn = n;
                    product = a * b;
                }

                b++;
                if (b == 1000) {
                    a++;
                    b = -999;
                }
            }
            t.text = "calc " + a + "," + b + "\n" + maxn;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        _isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    _isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }

    private function isPrime(n:int):Boolean {
        if (n < N) return _isPrime[n];
        
        t.text = "overflow";
        throw new Error("overflow");
    }
}
}

Project Euler #41

| 02:13 | Project Euler #41 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #41 - nitoyon.dispatchEvent(null)

n桁の数がPandigitalであるとは, 1からnまでの数を各桁に1つずつもつことである. 例えば2143は4桁のPandigital数であり, かつ素数である.

n桁のPandigitalな素数の中で最大の数を答えよ.

Problem 41 - PukiWiki

まず、Pandigital の定義を勘違いしていて、0~9 までが重複しない最大の素数を求めようとしていた。そうなると 32bit int の範囲に収まらないので、Number でやったりして 987654103 を求めた。次に、0 が含まれないことに気づいて答えを出したがそれでもダメ。

けっきょく、1~n までの数のみで構成される素数を求める、ということに最後まで気づかずに苦戦してしまった。間違えに気づいてしまえば、散々悩んだのですぐに答えは出た。

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

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

    private const N:int = 100000;
    private var primes:Array = [];
    private var _isPrime:Object = {};

    public function Problem41(){
		enumPrime();
    }

	private function prev_permutation(arr:Array):Boolean {
		var len:int = arr.length;
		if (len <= 1) return false;

		for (var i:int = len - 2; i >= 0; i--) {
			if (arr[i] > arr[i + 1]) {
				for (var j:int = len - 1; j > i; j--) {
					if (arr[i] > arr[j]) break;
				}

				var tmp:int = arr[j];
				arr[j] = arr[i];
				arr[i] = tmp;

				for (j = 1; ; j++) {
					if (i + j >= len - j) break;
					tmp = arr[i + j];
					arr[i + j] = arr[len - j];
					arr[len - j] = tmp;
				}
				return true;
			}
		}
		return false;
	}

    private function doit():void {
    	var numbers:Array = [9, 8, 7, 6, 5, 4, 3, 2, 1];

    	var result:int = 0;

    	setTimeout(function():void {
    		for (var j:int = 0; j < 10000; j++) {
				var n:int = parseInt(numbers.join(""));
	    		if (isPrime(n)) {
			    	t.text = n.toString();
	    			return;
				}

				if (!prev_permutation(numbers)) {
					var len:int = numbers.length;
					numbers = [];
					for (var i:int = len - 1; i > 0; i--) {
						numbers.push(i);
					}
				}
			}

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

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        _isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    _isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }

    private function isPrime(n:Number):Boolean {
        if (n < N) return _isPrime[n] == true;

        for each (var prime:int in primes) {
            if (n % prime == 0) {
            	return false;
            }
        }
        return true;
    }
}
}

2010-04-13

Project Euler #97

| 09:38 | Project Euler #97 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #97 - nitoyon.dispatchEvent(null)

28433×2^(7830457)+1 の下10桁を求めろ、という問題。

(A×Bの下10桁) == (Aの下10桁)×(Bの下10桁) であるので、演算のたびに下10桁のみに制限して計算量を抑えた。

そして、ついにオレオレ多倍長ライブラリに多倍長同士の掛け算機能を実装した。

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

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

    public function Problem97(){
        var result:Num = new Num(1);

        var n:Num = new Num(2);
        var a:int = 7830457;
        while (a > 0) {
            if (a % 2 == 1) result.mulNum(n).right(10);
            a /= 2;
            n.mulNum(n).right(10);
        }

        result.mul(28433).add(1).right(10);
        t.text = s.toString();
    }
}
}

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

    public function add(a:int):Num{
        digits[0] += a;
        carry();
        return this;
    }

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

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

    public function mulNum(a:Num):Num{
        var res:Num = new Num(0);
        for (var i:int = 0; i < digits.length; i++) {
            for (var j:int = 0; j < a.digits.length; j++) {
                if (isNaN(res.digits[i + j])) res.digits[i + j] = 0;
                res.digits[i + j] += digits[i] * a.digits[j];
            }
        }
        res.carry();
        digits = res.digits;
        return this;
    }

    public function right(i:int):Num{
        var s:String = toString();
        digits = parseString(s.substr(Math.max(0, s.length - i))).digits;
        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 static function parseString(s:String):Num {
        var n:Num = new Num(0);
        n.digits = [];
        while (s.length) {
            var pos:int = Math.max(0, s.length - N);
            n.digits.push(parseInt(s.substr(pos), 10));
            s = s.substr(0, pos);
        }
        return 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;
    }
}
|