整数問題を解くJSコード: 2^n−1が31で割り切れるようなケースを列挙する


JavaScriptで整数問題を解き,自然数を探索してみよう。

 

問題:

2^n - 1 が31で割り切れるのは,どのような場合か?

出典:

【シンプル整数難問】ある数で割りきれる条件 - 短くて面白い数学の問題コレクション 〜シンプルな難問〜
http://d.hatena.ne.jp/Sugaku+Simple-Short-Problems/20141220/p1

  • 2^n - 1 が31で割りきれる条件は?


この問題を解くためのJSコード:

<input type="button" value="計算開始" onclick="calc()"><br>

<textarea id="d" cols="80" rows="20"></textarea>


<script>

function calc(){
	clear_log();

	// 自然数を見つけよ
	find_natural_that( function( n ){ return (
		
		// この条件を満たすものを
		( Math.pow( 2, n ) - 1 ) % 31 == 0
		
	);})
	
	// 結果を表示せよ
	.display()
	;

}



// 以下ライブラリ


// 探索範囲の上限
var TEST_MAX = 50;


// ある自然数を見つけよ(条件は関数で渡す)
function find_natural_that( func ){
	return (
		new IntArr()
			.generate_by_step( 1, TEST_MAX, 1 )
			.filter( func )
	);
}


// 配列中で条件にマッチするものだけを残す
Array.prototype.filter = function( func ){
	var new_arr = [];
	this.each(function(){
		if( func( this ) ){
			new_arr.push( this );
		}
	});
	return new_arr;
};

// 配列のイテレータ
Array.prototype.each = function( func ){
	for( var i = 0; i < this.length; i ++ ){
		func.call( this[ i ], i );
	}
};


// 整数の配列のラッパ
var IntArr = function(){};
IntArr.prototype = {
	
	// 配列を内部に保持
	_arr : []
	,
	
	item : function( i ){
		return this._arr[ i ];
	}
	,

	// ステップ刻みで配列を生成
	generate_by_step : function( i_start, i_end, i_step ){
		this._arr = [];
		for( var i = i_start; i <= i_end; i += i_step ){
			//log( "generate_by_step : " + i );
			
			this._arr.push( i );
		}
		return this;
	}
	,
	
	// 条件で絞込み
	filter : function( func ){
		this._arr = this._arr.filter( func );
		return this;
	}
	,
	
	// 保持している配列の内容を表示
	display : function(){
		var tmp = [];
		for( var i = 0; i < this._arr.length; i++ ){
			tmp.push( /* i + ":" + */ this.item( i ) );
		}
		log( "[ " + tmp.join(", ") + " ]" );
	}

};


// 結果表示用

function log( s ){
	$("d").value = s + "\n" + $("d").value;
}

function clear_log( s ){
	$("d").value = "";
}


function $( dom_id ){
	return document.getElementById( dom_id );
}


</script>

実行結果

出力:

[ 5, 10, 15, 20, 25, 30, 35, 40, 45, 50 ]

つまり,nが5の倍数であるようなケースが列挙されている。

工夫したところ

問題の要となる部分を,できるだけ数学の言葉に近く記述するようなDSLを意識した。

そのようなDSLの最小の形態が,find〜thatの部分でとりあえず実現できていると思う。

仕様

nは1から50までの範囲内で探索している。

これは,JavaScriptの仕様に基づく制限だ。

JavaScriptで扱える最大の整数は,2の53乗ぐらい。

====

つまり10の15乗ぐらいであり,100兆ぐらいだ。

JavaScriptで巨大整数演算 - faireal.net
http://deztec.jp/x/05/faireal/25-index.html

  • この制限は、JavaScriptで「ふつう」に扱える整数が 253 までなので生じた


多倍長浮動小数演算スクリプト SLiMPNC4J | 松下響の天輪返し
http://h2s.roheisen.net/blog/archives/1657.html

  • JavaScriptの仕様上の限界である15桁と言えば100兆くらいです

この制限を回避するために,自前で多倍長計算ライブラリを作って,任意の大きな桁数の整数演算を可能にすると言う取りくみもある。

Archives program 巨大数演算
http://www.usamimi.info/~geko/arch_pro/0x003_calculation/

  • 電卓では計算しきれない桁数の数字をJavaScriptで計算するプロジェクト。


高度な JavaScript 技集
http://www.onicos.com/staff/iz/amuse/javascript/expert/

  • BigInt.js (整数の多倍長計算ライブラリ)


404 Blog Not Found:javascript - Math.BigInt で多倍長整数演算
http://blog.livedoor.jp/dankogai/archives/51516961.html

今後の改良案

多倍長ライブラリを導入して,15桁を超えるような整数について探索を実行したい。

また,出力結果には配列の要素がそのままダンプされているが,ここで出力された値が与えられた条件を満たしていることを個々のケースについて検算し,その検算の過程を自動的に出力結果に含めたい。

さらに展望としては,数学の問題を解くライブラリを充実させていって,「どんな素数pに対してもある平方数aが存在し・・・」のような文を自然に記述できるようにしたい。