ピタゴラス数をなんと 〜荒らされたので立て直しました〜 [無断転載禁止]©2ch.net
■ このスレッドは過去ログ倉庫に格納されています
自分で作ったプログラムでa^2+b^2のaが35万以上計算しました。
100万以上に向けて頑張りたいと思いますので
応援お願いいたします。
プログラムにバグがあった場合抜けている数があると思うので
その点には留意いたしたいと思う次第であります。 ごめんなさい。
>>119
> 三つ目のプログラムは、原始ピタゴラス数を、(奇数項,偶数項,斜辺項) の
> 順番に与えなければなりません。
{3, 4, 5} が最小だから、この順番が基本だよね? >>133 では
逆にしてました。(奇数項, 偶数項, 斜辺項)というスタイル以外に、
(短辺、長辺、斜辺)というスタイルもあるので混乱していました。
UDA 行列も、縦ベクトルに向かって右から行列を掛ける
スタンダードな方法と、横ベクトルに向かって左から行列を掛ける
「海軍式」というのがあるそうですので、たぶん形も二種類あることに
なります。
> 本来ならば、この辺の融通が利く形でアップすればいいのでしょうが、
> 面倒なので省略しました。ご了承ください。
「面倒臭がり(怠惰)」は、プログラマの三大美徳のうちの一つ(Larry Wall)だ
そうですから、よろしいんじゃないですか(笑)。(残りの二つは「短気」と
「傲慢」だそうです)
私も暇をみて改修してみようかと思っています(とはいえ言語は Java ですが)。 >>134
ピタゴラス数、あるいは、原始ピタゴラス数から新しい(原始)ピタゴラス数を生成する
という目的においては、UDA 行列のどれを用いても、かまわないと思います。
ただ、「ナンバリング」を行う上では、「U行列を用いた場合の番号変換はこれ、D行列を用いた場合の
番号変換はこれ、...」などと、ルールを固定しなければなりません。
同時に、生成されたピタゴラス数に対しても、aなのか、bなのか、見極める手段が必要となります。
この意味において、短辺か長辺かという視点は適切ではありませんでした。
しかし、第一項(=a)を奇数項、第二項(=b)を偶数項、そして、変換式を
(a,b,c)→(a~,b~,c~)=(-a-2b+2c,-2a-b+2c,-2a-2b+3c)
及び、これのa,bの符号を反転したものに固定すれば、この性質が維持されることが、
上の式を見ていただければ、判ると思います。それ故、ナンバリングを行う際には、この方法を採用しました。
もちろん、(a,b,c)→(a~,b~,c~)=(-2a-b+2c,-a-2b+2c,-2a-2b+3c) という変換式を採用することも可能でした。
その場合、世代の偶奇で、a,bの偶奇が入れ替わるようになってしまいます。
あと、Plimpton322の話は初めて見ました。ちょっと眺めてみましたが、メソポタミア流の
タンジェントの数表なのではと思いました。
そして、その値を定めるのに参考にした直角三角形のデータが添えられているだけなのではと。
そう考えると、ピタゴラス数に関連する値が出てくるのは、至極当然な事となります。 >>135
> あと、Plimpton322の話は初めて見ました。ちょっと眺めてみましたが、
> メソポタミア流のタンジェントの数表なのではと思いました。
『「まぁ待つさ」と、僕は答えた。』
ファインマン『ご冗談でしょう、ファインマンさん II ― ノーベル賞
物理学者の自伝』p.144 申し訳ございません m(_ _)m
>>124
(都市文化発祥の地であると謂われている)古代メソポタミアは、
(ユークリッド幾何学が成立した、「公準」「公理」「定理」の
ような)「証明」「論証」のシステムは成立していなかったであろう、
という話が前提にあって、「数学的な扱いやすさ」と「数学教育的な
観点」の間のギャップについての配慮が足りなかった、という点に
ついてはお詫びします。ごめんなさいm(_ _)m
そもそもが、>>124 で「長方形」という言葉を出し忘れていたのが
問題であったと思います。
「短辺と長辺と対角線の比が、自然数の比で表される長方形」と、
はっきり言明しなければならなかったと思います。
「正方形はどうなるんだ」という意見もあると思うんですが、
その時点で「正方形の対角線は、辺長との比は無理数である」と
いうのが明らかになって以降の概念、と考えていますので、お赦しを。 すみません。あとひとつだけコメントを。
ピタゴラス数(あるいは、ピタゴラス数による三角形
または長方形)を、有理数の上で(直観的に分かりやすい
形で)整列するのは、かなりややこしい話になると思いますよ?
>>127 で述べたように、q/p で考えると、わりと綺麗に
整列ができると思います。
そのとき、「正方形にいちばん近い p と q の比はどこに
あるのか?」という話になって、連分数表示だと、そこに
黄金数 φ が顔を出す、というのがまた面白いんですが。 >>127
>> このとき、二つの奇数 p と q を考えたときに、長方形 p × q を
>> 考えて、「面積が同じであるときに、正方形に近いのはどっちか?」を考えると、順序付けが可能です。
第一キーが面積の小さい順、第二キーが正方形に近い順、のような方法で、
整列するということでしょうか。そのようなアプ□−チ法もありますね。
私が、思いついていたのはもっぱら 分数の整列 を介しての方法です。
第一象限 の y<x 領域の格子点を原点に近い順に並べる。ただし、(x,y)に対し、分数y/xを与え、同じ値のものは除外とか、
Farey分数を利用するのも、ありかと考えました。
しかし、これらいずれも、番号→分数、あるいは、分数→番号 を得る手順が美しくありません。
二つの奇数p,qを用いての方法を用いた場合も、番号を与えてそれに対応する原始ピタゴラス数を答える、
あるいは、逆に原始ピタゴラス数を与えて、それが何番かを答えるという関数を作るとすると、
オイラーのφ関数の積算か、それに準ずる計算が必要となるのではないでしょうか
>>119の方法は三分木構造に沿って生成されるものなので、番号から原始ピタゴラス数を求める時も、
原始ピタゴラス数から番号を求める時も、単純な計算を、log[3](n) 回ほど繰り返すことで求めることができます。
いずれも大きなところでの計算時間は、この方法の方が早いのではと思います。
p.s.通常の書き方の「アプ□−チ」がなぜかNGワードのようで、投稿ができませんでした。遅れて申し訳ありません。 >>139
> 逆に原始ピタゴラス数を与えて、それが何番かを答えるという関数を
> 作るとすると、オイラーのφ関数の積算か、それに準ずる計算が
> 必要となるのではないでしょうか
本当にそうです (T_T)。
すべての自然数とすべての(正の)有理数は、
ともにアレフ・ゼロ(可算無限個)なので一対一の対応づけが可能だ、
ということは理論上は確かなんですが、その順序性を保持したまま
対応づけをしてしまうと、自然数を与えたところで有理数は「実質ゼロ」に
なってしまい、有理数を与えると自然数は「実質、無限大」という話に
なってしまいます。
そういう面倒臭いところが、無限の無限たるゆえんというか、めんどうくさい
部分なんですよ。ゲオルグ・カントールが「われ見るも、われ信ぜず」と
告白したというのも頷けます。
いまのところ、「UDAで一意に表せるんだから、三進数で表現するのが、
いちばん素直なんじゃねぇの?」という投げやりな意見が、我々の いちおうの
公式見解ということになっています。
だけど、それをすると大小の比較関係が単順序構造じゃなくて
半順序構造になってしまう(実際には、半順序構造が成立すると考えると
「木構造」ではなく「束(そく)」になってしまうので、また扱いが異なって
しまうんですが)んですよね。
それが、Barning=Hall=亀井の定理の逆問題を半世紀以上“未解決”にしていた
原因なのではないか、と思ったりはしています。
ですから、任意の原始ピタゴラス数の比較関係としては「共通の根が、
どこにあるか」で判断するしかないと考えています。 そうそう。そのあたりのアプローチとしては、細矢治夫先生が、
トポロジカル・インデックス(有機物のような、分子量が大きく
複雑な構造をもつ分子を、どのように検索・比較するかという指標)
によって評価しようとしていらっしゃいました。
数学的な考察に役立つかどうかはわかりませんが、ご参考までに。 >>140
> 「UDAで一意に表せるんだから、三進数で表現するのが、
> いちばん素直なんじゃねぇの?」
ということで、Java による逆ルートの探索プログラム(Java 版)の
ソースおよび解説は、「BackLog 四角い三角形」で検索すると
すぐ見つかるはずです。(引用およびソースの再利用は歓迎します)。 >>139
> p.s.通常の書き方の「アプ□−チ」がなぜかNGワードのようで、
> 投稿ができませんでした。遅れて申し訳ありません。
>>141
> そのあたりのアプローチとしては
たぶん、お使いのプロバイダを利用しているユーザの
環境に、分散型の、Dos アタックを仕掛けるマルウェアが
巣食っていたのだと思います。
しばらく(三十分以上)放っといて再アクセスすると、
だいたいなんとかなるようですよ (^_-)b~☆。 「長方形から正方形二つを取り除く」のような操作が、どうしてUDA行列の
話と直結するのか、不明瞭でしたが、紹介されたところを見回って、見えてきました。
UDA行列や、(-a-2b+2c)^2 + (-2a-b+2c)^2 = (-2a-2b+3c)^2 等の話は、
原始ピタゴラス三角形の辺長 a,b,c (a^2+b^2=c^2)の値そのものの話であり、操作です。
この、a,b,c が変化する様子を、a=m^2-n^2、b=2m*n、c=m^2+n^2(あるいはその半分?)
を満たす、m,n の世界で眺めたとき、m*nの長方形において、二つの正方形を取り除いたり、
追加したりする操作に対応すると言うことだったんですね。すっきりしました。
全ての原始ピタゴラス数は、単位円上の一つの有理点に対応します。
そしてこの有理点は、一つの有理数に対応可能です。
(変換方法はいくつも考えられますが、最も一般的な方法は、((1-t^2)/(1+t^2),2t/(1+t^2))を利用するもの。)
従って、全ての有理数を、何らかの有理変換を、何度か経て、1/2 or 2 (原始ピタゴラス数{3,4,5}に対応する有理数)
に到達でき、また、その逆も可能なら、それらの有理変換は、原始ピタゴラス数を整理する道具に使えると言うことですね。 >>144
私の思うところのものを正当に理解して下さっていることを
感謝します。m(_ _)m
数学の初心者に対して(「あなたが数学の初心者」であるという意味ではありません。
あなたは、おそらくは数学を教える立場に立つことに向いていると、私は考えます)、
より分かりやすい形でいうと
> 従って、全ての有理数を、何らかの有理変換を、何度か経て、
> 1/2 or 2 (原始ピタゴラス数{3,4,5}に対応する有理数)
> に到達でき、また、その逆も可能なら、それらの有理変換は、
> 原始ピタゴラス数を整理する道具に使えると言うことですね。
における「有理数」が、「すべての既約分数」と同義である、
ということに対して言及(つーか、念押しというか注意喚起っつーか)
して下さると、嬉しく思います。 >>144
『Ikuro's Home Page』(ttp://www.geocities.jp/ikuro_kotaro/)の
『今月のコラム(閑話休題)』のなかの、『エジプト三角形の作図』や
『ピタゴラスの小石?』なんかは、このスレと関連して
面白いかと思います。お勧めです。 そうそう。小学校の算数の授業では、「分数の約分」は
教わるんですけど、「分子と分母に対する共役数を
求める方法」は現在の教育では、教えていないんですよ。
「なんで互除法を教えないのかなぁ? 分子分母の
最大公約数を求めて、それで分子と分母を割ればいい
だけじゃないの?」と思うんですが、「最大公約数」とか
「ユークリッドの互除法」を、「小学生にもわかるように
説明する」ためのノウハウが、小学校で算数を教えている先生に
伝わっていないのではないか、と思います。
(正方格子空間における)「長方形」をベースにした互除法の説明は、
たぶん小学生にも通じると思うのですが、いかがでしょうか。 「ユークリッドの互除法」「連分数」
「黄金比」「白銀比」は、実用的な観点からも
教育的な観点からも、セットで教えたほうが
いいように思います。
小学校高学年から中学校にかけての年齢だったら、
充分に理解できる概念のように思うんですが、
さいきん「中高一貫教育」というのが流行りなので、
「小学校で教えられていないものを、中学校の
受験問題に出題するのは、いかがなものか?」みたいな
配慮があるのかもしれません。
その結果、「受験で出ないものは出さない」ことになり、
学ぶ機会を失っているのかもしれません。
だったら「約分・通分」と一緒に、「因数分解」「素数」
について、じっくり教えたほうがいいと思うんですけどねぇ。 『Ikuro's Home Page』さんには、よくお邪魔してます。大変参考にさせていただいています。
最大公約数の話ですが、「ユークリッドの互除法」と名付けられている方法があることを、
おそらく私は高校1年で習いました。ただ、a と b の公約数は、a と a-b の公約数でも
あることを、どこで教わることもなく、体得していたため、当然のことと受け止めたことを覚えています。
小学生相手には「ユークリッドの互除法」ではなく、(a と b の公約数)=(a と a-b の公約数)
を教えるだけで、ほぼ十分なのではないかと思います。これを繰り返していけば、
自動的にユークリッドの互除法にたどり着きますし。
「連分数」 、「黄金比」、「白銀比」、などを、小中学生に面白く教えることができれば、
数学好きな児童・生徒を増やせそうですよね。あと、フィボナッチ数列なんかも。
でもこれらは、学校の算数/数学の授業にはそぐわないと考えられているのではないでしょうか。
特別授業とか、地域住人参加可能な公開授業なんかの方が相性がよいと思います。
144に関連し、何か面白い有理数→有理数→有理数→...の様な変換はないかと思っていたんですが、
思いがけず、Farey分数がそのまま使えることに気づきました。
Farey分数は二分木構造そのものですから、原始ピタゴラス数を二分木構造に埋め込むことが可能です。
例の三分木構造は、一つのピタゴラス数から、一人の親と三人の子を直接見つけることができますが、
この二分木構造は、親子関係を確定させるためには、ある程度の近親者情報が必要となります。
そのため、あまり面白くはありません。 ユーックリッドの互除法自体は、大学生になってから
知ったのですが、「格子点を持つ長方形」の性質に
ついては、小学生のときに気づいていました。
小学生のときには病気がちで、和室に布団を敷いて
寝かされていたのですが、そのとき障子が目に入るんですよ。
で、角のところから45°の角度で格子点を辿ってゆく
(辺のところでは“反射”する)と、mとn が互いに素であるとき、
すべての升目を一度づつ通って別の数に至ることに気づきました。
このとき、辺に着いたら、隅からその点を対角線として持つ正方形
になるわけで、後にフィボナッチ螺旋を見て「あぁ、そういうことか」と
納得しました。
ですから、私にとっては「ユークリッドの互除法」と「連分数」は、
同じコインの両面、というイメージがあります。 >149
>>(a と b の公約数)=(a と a-b の公約数)
と約分については、a と b のそれぞれを素因数分解して
重複している素因数の積、という頭があるので、
たとえば分子分母の大きいほうから小さいほうを
取り除いていって、「上下が同じになる」か「上下が 0 」になる
というリクツがいまいち腑に落ちません。
小学校で、「約数をすべて求めよ」という場合は因数分解してから
組合せを作るというのもなかなか大変だし、そもそも「素因数分解の
一意性」だってギリシャ時代には「経験的に明らか」とされていましたが、
厳密な証明はガウスを待たなければなりません。また、「素因数分解を
行なう効率のよいプログラムは発見されていない」とかいった話も
ありますし。
このあたりのギクシャクした話が、算数嫌いの子供を生み出しているかも
しれない、とは思います。 そうそう。私は「ユークリッドの互除法」を「二つの実数の比を
有理数で近似する方法」として知ったのが先で、「自然数で表される
長方形から正方形を取り除く方法」だと知ったのはその後です。
遠山啓先生と銀林浩先生の子供向けの本に、「二人の承認が「異なった
長さの布の値段を決める」ために、短いほうで長い方の布を取りつくし、
残った半端な部分でもう一つの布を取りつくし …… とやっていって
連分数表示を求め、そこから元の比を計算する」という話が出てきました。
古代メソポタミアでは、同じような方法で、長方形の土地の形状比を
もとめていたのではないか、と私は考えています。 コンピュータを用いてユークリッドの互除法を行なうには二種類あって、
わりあいに一般的なのが「繰り返しによる方法」で、ちょっとトリッキーな
感じがするけれど慣れると自然、というのが「再帰呼び出し(リカーシブ)を
使う方法」です。私はリカーシブ派なのですが、「ベズーの公式を互除法を
使って解く」という話があり、それをプログラムで書いてみようとしたところ、
どうもリカーシブで書くとややこしいことになりそうだ、ということになって
しまいました。
実際のプログラムは、『BackLog』の『ベズーの公式。』
(2015/12/18)に掲載。関連エントリは、ちょっと前にいくつかあります。
Java がある程度読めないと while(true) みたいな制禦構造が出てきたり
インデントが変だったり(loop - until - do - repeat 構造、別名を
「n + 1 / 2」ループ」といいます)して読みにくいし、動かそうと
思うと Eclipse のような IDE があったほうがいいので面倒臭いですが、
いちおうご参考までに。 >149
> 「連分数」 、「黄金比」、「白銀比」、などを、小中学生に面白く教えることができれば、
> 数学好きな児童・生徒を増やせそうですよね。あと、フィボナッチ数列なんかも。
> でもこれらは、学校の算数/数学の授業にはそぐわないと考えられているのでは
> ないでしょうか。
遠山啓(とおやま・ひらく)さんという「数楽者」(「すーらくもん」と読みます。
『数学セミナー』の創刊者です)の方が、「『ひと』熟」という子供のための
キャンプのようなものをやってらっしゃって、小学生にも中学生にも、普通に
理解できたようですよ? 通称を「水道方式」といいまずが、実際の広い概念は
教具や基本思想を含めると、もうちょっと広い。ただ、遠山 啓(とおやま・けい)
という方が水理学の方がいらっしゃって、『下水道』という本を出していたのを
見て大いに気に入った、というエピソードがあります。 遠山さんは、「子供を教えたい」というので東工大のお辞めに
なって児童教育のほうに進まれました(たしか「山びこ学校」かな?)。
「授業が終わってから、子供たちに『これは、勉強か、遊びか?』と
訊いたら、『面白かったから、あそびだ』と答えてくれた」といって
ニコニコされていたそうです。また、「子供という、こんなに面白い
オモチャを貸してもらえないて、しかも給料まで貰えるんだから、こんなに
いい商売はない」とも。森毅センセが遠山さんにお会いしたとき「大学を
辞めるとおもしろいぞ! 森クン、キミも早く辞めたまえ」と肩を掴まれた
そうです。「まだ助教授なんで勘弁してください(T_T)」と頭を下げたとか。 Farey分数を順番(※)に表示する関数、分数から(※)で定義した順番を返す関数、
順番からFarey分数を返す関数を作ってみました。
分数からピタゴラス数へ変換可能なので、それも併記してあります。
単位円上の2点(3/5,4/5)と(4/5,3/5)に対応する既約分数が異なるため、
同型のピタゴラス数が二つづつ登場してます。
「分母分子とも奇数」型か、「どちらかが偶数」型で分離できるようですが、
あえて、{3,4,5}と{4,3,5}を別々に扱うこととしたピタゴラス数のナンバリングが
完成できたと思います。
ttp://codepad.org/NkJaTo4f >>156
本当に余計なお節介だというのは重々承知しているし、
数学関係の専門書に出てくるプログラムがああいう感じの
C のプログラムだというのもよく知っている(数学者の
先生は、ソフトウェア開発が専門ではないので、とりあえず
動いてロジックに問題がなければ御の字、と考えていらっしゃるのは
頷ける)のだが、
K&R のスタイルは、そんなにガチガチに遵守しなくていいんだぞ?
適当な統合開発環境(IDE)があったら、乗り換えたほうが楽だ。
私はそれで Eclipse と Java に移行した。Eclipse の前身は
VisualAge C/C++ という C/C++ の IDE だったから、
たぶん C でもなんとかなると思う。 >>156
ついながら、「配列」は “arey” ではなくて “array” 、な。 失敬。Faray は人名のほうだったか。「なんちゃらかんちゃら配列」
かと思っていた。
私は原始ピタゴラス数のことを、Babylonian Rectangle と呼んで、
そういう名前のオブジェクトを定義し、
Java の ArrayList に突っ込む、という形でプログラムを
書いていたので「この配列はなんだ?」とか考えこんでいた。(-_-!) WikiPedia によると、ファレイ数列は連分数と関連があると
書いてある。プリンプトン322を解読していたときに、
「古代バビロニア人は 180 以下の(分子分母がともに
基数の)既約分数をどうやって網羅したんだろう、と
首を捻っていた(もちろん「根性で」という可能性も
高いんだが)のだが、黄金数 φ を連分数表示すると
[1; 1, 1, 1, 1, …] で1+√2が[2; 2, 2, 2, 2, …]
というのを見ると、「ワシらは三千年以上も前の
連中の後追いをしていたのか?」と気弱になってくる。orz 自分でよく使っている環境は別にあります。
そこで作成したものを、codepadに移植する際に、クラシカルなものになってしまっているのだと思います。
以前、別の言語で実行させたとき、原因不明のエラーが出て、対処に困りました。
そのとき、このスタイルで実行させたところ、うまく走ってくれたので、
ここに投稿するときにはこのスタイルを取ることにしてます。
もし、字下げや、関数の呼び出しのようなスタイルに対するものでしたら、染みついたものですから、しょうが無いですね。
それと、私は低級側好みます。
例えば、next_permutationという関数があります。次々に新しい順列を返してくれるものです。
使う側としては便利なのですが、どのようなアルゴリズムでやっているのか気になって調べたら、
「無駄」があることが判りました。数度だけ利用するなら、全然問題にならないレベルですが、
全ての順列を発生させる場合には、無駄な処理を繰り返すことになっています。
ということで、順列を発生させるような場合も、自分で発生させています。
このように、内部で何をやっているかよく分からず、かつ、自分で作成できるような場合は
自作することが多いです。私にはC++が馴染んていると思うのですが、この辺に理由があるんだと思います。
「Farey分数」は、wikiには「ファレイ数列」として載っていますね。確かに人名由来の名称のようです。
>>139では、分数と番号の変換が美しくないと書きましたが、ファレイ分数を、「値」を実態とするところの有理数
と考えるのではなく、「範囲」に対する名称と認識することで、変換を低コストで実現可能であることに気づき、
今回、実際にコード化を試しました。昨夜のプログラムの出力に、「範囲」を載せている所以です。 >>161
低級レベルの記述をしようと思うんなら、確かに C(あるいはC++)は
よい選択だと思う。おれも元々は数値計算屋で、大規模問題を
貧弱なコンピュータ環境で解く、というのに血道を上げていたので、
そのあたりの感性はよく理解できる。
初等関数の数値計算を行うときに、“CORDIC”という手法があって、
ほぼ乗算程度の計算量で初等関数が最後の桁まで求まる
(必要なのは、 arctan() の数表だけ)んだ。
そういうのが好きだったら、一松 信先生の『初等関数の数値計算』とか
面白いと思うぞ?
あとは森口繁一先生の『数値計算夜話』とか、一松先生の『教室に電卓を!』とか。
おれはプロとしてチーム開発を長年してきたので、「速くする前にわかりやすくしよう」
という観点から、C から Java へ移行したという経緯がある。C のような低レベル
言語だと、「見立て」というか、「こういうことを言いたいんですよ」というのが、
(実行速度との絡みで)伝えにくいという意識がある。
昨今は CPU は速いしメモリ空間もでかいので、「こういうことを
言いたいんですよ」というのがざっくり説明しやすい Java に興味を
持っている。
それに、Java はけっこう C の流儀を引きずっているので、
年寄りとしては、なんとなく安心するところがある。 >>161
あと、「入山のアルゴリズム」でググッてみると、
面白いかもしれないと思う。 >>161
> もし、字下げや、関数の呼び出しのようなスタイルに対するものでしたら、
> 染みついたものですから、しょうが無いですね。
いや、インデントに関しては、個人の趣味の問題なので「好きにしろ」
という立場なんだが、「変数を頭のところで宣言する」というのが
わりと古いスタイルの C に影響されているかもな、と思った。
CPU のレジスタ構成とかを考えると、昔は高速化に貢献していた
部分はあるのだが、昨今のコンパイラの最適化は信用していいと
思う(不安だったら、C のコンパイラはアセンブラのソースを
吐くので、それを読んでみたら安心できると思う)ので、
変数のスコープを明確に示して、人間側のエラーを減らしたほうが、
(あくまで職業的なプログラマの立場から言うのであって、個人が
書くプログラムに関しては、ぶっちゃけ趣味の問題でしかないが)
たぶん長期的にみると効率がいいと思う。
プログラマは「三日前の自分は他人だ」と云うしな。 あと、これは数学板で言うこっちゃないと思うが
(つーても FORTRAN は「数式変換(FORmula TRAMsratpr)」の
略だし、「ALGOL」は、アルゴリズム記述用の言語として定義された
経緯はあるのだが)、
変数名として i, j, k を使うのは、i, j, k, l, m, n(たぶん integer から
natural までだと思う)で始まる変数は、定義されていなくても整数型の
変数だ、という FORTRAN 60 の処理系依存のルールが起源だと思う。
昨今は「局所変数は、使うスコープの中で定義する」というスタイルが
一般的になっていると思う。
このあたり、哲学(論理学)における、自由変項(グローバル変数)と
束縛変項(局所変数。関数引数と、関数内の作業領域が、この代表)に
対応しているので、興味があったらこれらの言葉をキーワードとして
関連図書を漁ってみると楽しいかもしれない。 >>161
いきなり思い出したので書いておくと、
大田区の区議会選挙の話でシャープレイ=シュービック指数を
計算するときに、すべての組合せを生成する(もうちょっと
効率のいい計算法があるはずなんだが、考えるより動かしたほうが
早そうだった)ルーチンが必要になり、その昔書いた「動的ちり集め」の
ロジックをひねくって実装した記憶があった。
ところが、Java には明示的なポインタがない(「参照」は実質的には
ポインタなんだが)ので、swap ができなくてギブアップした経験がある。
そんなわけで、「とりあえず、整列やらなんやらはライブラリに任せて、
中身に関しては(よっぽど遅くなかったら)考えないことにする」と
居直った。
だから、昔の関数電卓を使うと、初等計算の計算より階乗の計算のほうが
あからさまに遅いのを見ると、なんとなく諦念が浮かんでくる。 色々と面白いお話ありがとうございます。本論からは外れてしまいますが、少しコメント
させてもらうと、FORTRAN、暗黙の宣言文ときたら、私はルンゲクッタ法を思い出してしまいます。
表記の異なる4つの式を、暗黙の宣言文を利用(悪用)して、1ステップの式で表し、
こっそりループに閉じ込めました。そして初見の人に、「これ、ルンゲクッタ法使ってるの?」と
言わしめる悪戯をしていたのを思い出します。
投票力指数については初めて目にしました。順列生成は、覆面算とかのパズル系でよくつかいますが、
このような実用的なところでも利用されていたんですね。勉強になりました。
>> プログラマは「三日前の自分は他人だ」と云うしな。
呂蒙のお話かと思ったけど、「自分が書いたはずの三日前のコードの意図が分からない」的なことですよね。 >>168
> そして初見の人に、「これ、ルンゲクッタ法使ってるの?」と
> 言わしめる悪戯をしていたのを思い出します。
N88-BASIC には GOTO と GOSUB というコマンドがあって、
飛び先が両方ともラベルだった。
で、「八人の女王」のプログラムで GOTO と GOSUB と RETURN を
ごっちゃに使って「追っているとだんだん意味不明になって頭を抱える」
というのを書いたことがある。 >>168
呂蒙って知らなかった。『男子、三日会わざれば刮目(かつもく)して見よ』
みたいな話じゃなくて、「喉元過ぎれば熱さを忘れる」とか「ニワトリは
三歩歩くと忘れる」程度の話。
ちなみに、ナメクジは思い出した瞬間に冷やすと忘れる、という話が
あるので、「トラウマとかがあった場合、思い出した瞬間に冷やしたら
どうだろう?」みたいな話が昔あった。 >>170
日経サイエンス、一九九〇年七月号、P.82、
『冷やすと消えるナメクジの記憶』。 なんかこのスレも決着がついちゃった感があるので、
残りを埋める意味で Java のソースでも貼っとくか。
「原始ピタゴラス数」という名前ではなく、
「縦横と対角線の長さが自然数で表される長方形」を
「バビロニア長方形」と呼んでいる。
クラス定義と、縦横の比のコンパレータ。コンテナに突っ込んで
ソートすると、縦横比で整列される。 public class BabylonianRectangle {
private int p;
private int q;
private int m;
private int n;
private int odd_side; // 奇数辺
private int even_side; // 偶数辺
private int short_side; // 短辺
private int long_side; // 長辺
private int diagonal; // 対角線
private int magnitude; // 倍率
private double aspect_ratio; // 形状比 /*
* コンストラクタ
* @param a
* @param b
*/
public BabylonianRectangle( int a, int b ) {
this.magnitude = Secretary.gcf(a, b);
a /= magnitude;
b /= magnitude;
if ((a % 2 == 1) && ( b % 2 == 1)) {
this.m = a;
this.n = b;
this.p = (n - m) / 2;
this.q = (n + m) / 2;
/*
* Euclid の公式
* {(q^2 - p^2) / 2, p * q, (p^2 + q^2) / 2)}
* ただし、p, q は互いに素であり、ともに奇数.。
*/
this.even_side = (( this.n * this.n ) - ( this.m * this.m )) / 2;
this.odd_side = this.m * this.n;
this.diagonal = (( this.m * this.m ) + ( this.n * this.n )) / 2;
} else {
this.p = a;
this.q = b;
this.m = q - p;
this.n = q + p;
/*
* Brahmagupta の公式
* {n^2 - m^2, 2 * m * n, m^2 + n^2}
* ただし、m, n は 0 < m < n かつ
* 互いに素であり、偶奇が異なる.
*
*/
this.odd_side = (q * q) - (p * p);
this.even_side = 2 * p * q;
this.diagonal = (p * p) + (q * q);
}
// 短辺と長辺の長さを求める。
this.short_side = (odd_side < even_side) ? odd_side : even_side;
this.long_side = (odd_side < even_side) ? even_side : odd_side;
this.aspect_ratio = (double)long_side / (double)short_side;
} /*
* getter. 原則的に setter はない.
*/
// Euclid の公式
public int getM() {
return this.m;
}
public int getN() {
return this.n;
}
// Brahmagupta の公式
public int getP() {
return this.p;
}
public int getQ() {
return this.q;
}
// 奇数辺の長さ
public int getOddLeg() {
return this.odd_side;
}
// 偶数辺の長さ
public int getEvenLeg() {
return this.even_side;
}
// 短辺の長さ
public int getShortSide() {
return this.short_side;
}
// 長辺の長さ
public int getLongSide() {
return this.long_side;
}
// 対角線の長さ
public int getDiagonal() {
return this.diagonal;
}
// 形状比
public double getAspectRatio() {
return this.aspect_ratio;
} /*
* 扱いが かなり面倒臭い. setter が必要.
*/
public int getMagniTude() {
return this.magnitude;
}
@Override
public String toString() {
int x = this.getShortSide();
int y = this.getLongSide();
int z = this.getDiagonal();
float sort_key = (float)( z * z )/(float)( y * y );
String ret =
"{" +
Integer.toString(this.getShortSide()) + ", " +
Integer.toString(this.getLongSide()) + ", " +
Integer.toString(this.getDiagonal()) + "}:" +
sort_key;
return ret;
}
public String toString2() {
String ret =
"( p = " + this.getP() + ", q = " + this.getQ() + "):" +
"( m = " + this.getM() + ", n = " + this.getN() + "):" +
"{" +
Integer.toString(this.getShortSide()) + ", " +
Integer.toString(this.getLongSide()) + ", " +
Integer.toString(this.getDiagonal()) + "}:" +
this.getAspectRatio();
return ret;
}
} import java.util.Comparator;
public class BabylonianRectangleComparator implements Comparator<BabylonianRectangle> {
public int compare( BabylonianRectangle a, BabylonianRectangle b ) {
if (a.getAspectRatio() == b.getAspectRatio()) return 0;
if (a.getAspectRatio() > b.getAspectRatio()) return 1;
return -1;
}
} >>128 以降の、プリンプトン322の話は以下のような
感じで確認できる。 import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import toybox.Abaci;
public class P322_05 {
// static final double phi = 1.732d;;
static final double phi = (1.0d + Math.sqrt(5.0d)) / 2.0d;
static final int UPPER_LIMIT = 180;
public static void main( String [] args ) {
_main();
}
private static void _main() {
ArrayList <BabylonianRectangle> BRs = new ArrayList<BabylonianRectangle>();
byEuclid(BRs);
// byBrahmagupta(BRs);
Collections.sort(BRs, new BabylonianRectangleComparator());
print(BRs);
print2(BRs);
}
// ユークリッドの公式
static void byEuclid(ArrayList <BabylonianRectangle> brs) {
for (int m = 1; m < UPPER_LIMIT; m += 2) {
for (int n = m + 2; n <= UPPER_LIMIT; n += 2) {
if (Secretary.gcf(m, n) != 1) continue;
BabylonianRectangle br = new BabylonianRectangle(m, n);
if ((1.0d < br.getAspectRatio()) && (br.getAspectRatio() < phi)) {
if (Secretary.isHarmonic(br.getLongSide())) {
brs.add(br);
}
}
}
}
} // ブラーマグプタの公式
static void byBrahmagupta(ArrayList <BabylonianRectangle> brs) {
for (int p = 1; p < UPPER_LIMIT; p += 1) {
for (int q = p + 1; q <= UPPER_LIMIT; q += 2) {
if (Secretary.gcf(p, q) != 1) continue;
/*
if (!Secretary.isHarmonic(p)) continue;
if (!Secretary.isHarmonic(q)) continue;
*/
BabylonianRectangle br = new BabylonianRectangle(p, q);
if ((1.0d < br.getAspectRatio()) && (br.getAspectRatio() < phi)) {
if (Secretary.isHarmonic(br.getLongSide())) {
brs.add(br);
}
}
}
}
}
static void print( ArrayList <BabylonianRectangle> BRs ) {
int n = 0;
Iterator <BabylonianRectangle> iter = BRs.iterator();
while ( iter.hasNext()) {
BabylonianRectangle br = iter.next();
System.out.println(++n + " : " + br.toString());
System.out.println( Abaci.regulerNumberToString(br.getLongSide()));
}
}
static void print2( ArrayList <BabylonianRectangle> BRs ) {
int size = BRs.size();
if (size < 1) return;
int index = 0;
BabylonianRectangle work = BRs.get(index);
float arx = (float) work.getAspectRatio();
for (index = 1; index < size; index += 1) {
work = BRs.get(index);
float ary = (float) work.getAspectRatio();
System.out.println(index + ":" + (ary - arx) * 100);
arx = ary;
}
}
} いくらか足らんところもあるけど、
なんかレスがついたら返事する予定。
でもって適当に age てみる。 参考までに、プリンプトン322に書かれている値を載せておこう。
夏休みの自由研究的なナニカだと思ってくれ。
番号 : {短辺, 長辺, 斜辺} : 六十進表記の斜辺の平方と長辺平方の比(同、十進表記)
1 : {119, (120,) 169} : 01;59:00:15(≒ 1.9834027)
2 : {3367, (3456,) 4825} : 01;56:56:58:14:50:06:15(≒ 1.9491584)
3 : {4601, (4800,) 6649} : 01;55:07:41:15:33:45(≒ 1.9188021)
4 : {12709, (13500,) 18541} : 01;53:10:29:32:52:16(≒ 1.8862479)
5 : {65, (72,) 97} : 01;48:54:01:40(≒ 1.8150077)
6 : {319, (360,) 481} : 01;47:06:41:40(≒ 1.7851928)
7 : {2291, (2700,) 3541} : 01;43:11:56:28:26:40(≒ 1.7199837)
8 : {799, (960,) 1249} : 01;41:33:45:14:03:45(≒ 1.6927094)
9 : {481, (600,) 769} : 01;38:33:36:36(≒ 1.6426694)
10 : {4961, (6480,) 8161} : 01;35:10:02:28:27:24:26:40(≒ 1.5861225)
11 : {45, (60,) 75} : 01;33:45(≒ 1.5625)
12 : {1679, (2400,) 2929} : 01;29:21:54:02:15(≒ 1.4894168)
13 : {161, (240,) 289} : 01;27:00:03:45(≒ 1.4500173)
14 : {1771, (2700,) 3229} : 01;25:48:51:35:06:40(≒ 1.4302388)
15 : {56, (90,) 106} : 01;23:13:46:40(≒ 1.3871605) >>182
120 / 119 = 1.008(1)
90 / 56 = 1.607(15)
φ = 1.618
なんで、1 と 黄金比の間だって気がつかなかったのか、
そっちの方が不思議に思うんだがなぁ。 前にも書いたけど、
「11 番と 15 番が、なぜ原始ピタゴラス数ではないのか?」
っちゅーあたりを考えると、古代バビロニア人の
「美学」みたいなものに行き当たるので、
けっこう面白い。 …… というような話を、きょう
室井和男著/中村滋コーディネートの
『シュメール人の数学 ― 粘土板に刻まれた古の数学』
(共立出版。スマート・セレクション)の感想として
送っておいた。
反応が楽しみなんだが、結果は どうだろう。 思考停止の総当たり
#include<stdio.h>
#include<stdlib.h>
int pit(int A,int B, int C){
int a,b,c; int pit=0;
for(a=1;a<=A;a++){
for(b=a;b<=B;b++){
for(c=b;c<=C;c++){
if((a<b) && (a*a+b*b==c*c)) {
++pit;
printf("%d : %d * %d + %d * %d = %d * %d\n",pit,a,a,b,b,c,c);
}
}
}
}
return 0;
}
int main( int argc, char *argv[] ){
int a,b,c;
a = atoi(argv[1]);
b = atoi(argv[2]);
c = atoi(argv[3]);
pit(a,b,c);
return 0;
} >>187
おれも同じことをやったが、
演算子 ++ は、「構造体とかのサイズのあるものに
対するポインタに対して、sizeof() 分だけインクリメント
するのが本来の使い方」なんで、ポインタじゃない
整数値に対しては ++ じゃなくて +=1 を使うのが
礼儀正しい C プログラミングのありかただと思われ。 >>187
あと、これはまったく余計な話だが、
main() の戻り値は、昨今は void に
しとくのが流行らしい。
どうせレジスタに残ってる値を使うか使わないかの
話なんで、「どうでもいいや」っちゅー話はあるんだけどね。 プリンプトン322が45° から30° までの表だとすると、
{175, 288, 337}:1.369225
が入って 16 行になんないとおかしいと思うんだが、
どうだろう。
288 / 175 < √3 = 1/tan(30°)
だよなぁ? すまん。別スレの話題なんだが、そっちの方では
スレ違いなんで、「ピタゴラス数つながり」で、
このスレの残りを有効利用させてもらいたい。
m(_ _)m
まず、「ユークリッドの公式」(つーても、ユークリッドが
生まれる千五百年前には発見されていたのだが)という
ものがある。
【ユークリッドによる、原始ピタゴラス数の公式】
「互いに素な奇数 p, q (ただし、0 < p < q)から、一意に
原始ピタゴラス数を求める式がある。すなわち、
{X, Y, Z} = {(q^2 - p^2}/2, p×q, p^2 + q^2}
である。」 つぎに、Barning = Hall = 亀井の定理について説明する。
互いに素な奇数 {p, q} (ただし、0 < p < q)があったとき、
以下の三つの奇数の組 は、互いに素であり、すべて異なる。
1){p, q + 2p}
2){q, p + 2q}
3){2q - p, q}
【Barning = Hall = 亀井の定理】
すべての原始ピタゴラス数は、三分木によって、一意に表される。 【Barning = Hall = 亀井の定理の逆問題】
任意の原始ピタゴラス数から、最小の原始ピタゴラス数に
至る経路を求めるアルゴリズムを示せ。
【解】
前期(1)(2)(3)は、逆操作として、
0 < p < q のとき、
{p', q'} = {p, |q - 2q|} として表される。
ただし、p = 1, q = 3 のとき、
p' = q' = 1 となり、「0 < p < q 」の条件を満たさないため、
逆操作は行えない。このとき、
f(1, 3) = {3, 4, 5}
であり、Barning = Hall = 亀井の定理の示すところと
一致する。 この分野はよく知らないが、HallはMath GazzetteのClassroom Notesに
Barningはオランダ語のレポートと、主流の結果でもない
最近の論文見ると
http://nntdm.net/volume-18-2012/number-1/49-57/
みたいなのに掲載されてる。
あとは日本国内の研究者でBarning-Hallに興味持っている研究者を
調べて、そこの欧文紀要があれば掲載を頼む
英語で数学論文を書いた経験があまりないのなら
誰かに論文見てもらって直してもらわないと、論文の体裁をなしてないという理由で
rejectくらっても仕方ないよ
へぼい国内紀要でもそういう論文は結構投稿されていて門前払いを食らう
論文の校正まで編集部やrefereeはやってられないからね >>194
ありがとう。
「やべぇ! 後追いだったか?」と思って ちょっとビビったけど、
このレベルだったら細矢先生のほうが先に行ってる。
つーか出たのが二〇一四年の十月だったら、おれらがもう
逆問題を解いた後だ。
やっぱ、行列式使って解こうとすると、逆行列を考えたところで
行き詰まっちゃうんだろうな。おれらは そっちへ行ってないから、
どこで行き詰まるのか自体がよく解らんけど。
ついでに指摘しておくと、結城浩さんや紹介してくれた論文で
使ってる公式(こっちの方が有名だ)は、インドのプラーマグプタ
(0の発見者として有名)が書き残してるもので、
時代的にはユークリッドの式よりも何百年か遅いはず。
>>191 以降の議論は、そっちの式を使っても、同じ結論に
なる。p, q と m, n は、たしか和差の関係になるはず。
おれがプラーマグプタの式を使わなかった理由は、数式を
図で描こうと思うとダサいからだ(笑)
ユークリッドの式は、長方形の中に三角形一つと長方形
一つで描ける(なんせ、古代バビロニアには数式がねぇ!)
ので、壁に貼っておきたくなるようなシロモノだ。 (1)『すべての原始ピタゴラス数は、{3, 4, 5} に
U/D/A という三次の行列を掛けることで、一意に表される』
という性質を既知とする。
e=(3 4 5)とする(横表記だけど縦ベクトルのつもり)。
v=(x y z)を原始ピタゴラス数とする。
(1)によれば、eにU/A/Dを掛け算していくことでvが得られるので、
U^{-1}v, A^{-1}v, D^{-1}v のうち、原始ピタゴラス数が少なくとも1つはある。 >>195
おぉ、ありがとう。
とりあえず敷居が高いというのは理解したので、
小冊子を自費で出版して(マンガ同人誌と
おんなじようなモンだし)、心当たりに
片っ端から配って回る、とかいうのが
いちばん手っ取り早いかもしらんな。 ここで、U^{-1}vとA^{-1}vがともに原始ピタゴラス数になることはない。
なぜなら、もしこの2つが原始ピタゴラス数なら、
U^{-1}vとA^{-1}vそれぞれに(1)を適用して、
eにU/A/Dを掛け算していくことでU^{-1}vが得られる
eにU/A/Dを掛け算していくことでA^{-1}vが得られる
ので、
eにU/A/Dを掛け算してU^{-1}vを得たのちに、さらにUを掛ければ v が得られる
eにU/A/Dを掛け算してA^{-1}vを得たのちに、さらにAを掛ければ v が得られる
となり、eからvへの経路が2つあることになって、(1)の一意性に矛盾する。 同じようにして、U^{-1}vとD^{-1}vがともに原始ピタゴラス数になることはないし、
A^{-1}vとD^{-1}vがともに原始ピタゴラス数になることはない。
要するに、U^{-1}v, A^{-1}v, D^{-1}v のうち、原始ピタゴラス数は1つしかない。
よって、以下のアルゴリズムで、vからeへのルートが出力できる。
v=(x y z)を原始ピタゴラス数とする。U^{-1}v, A^{-1}v, D^{-1}v を計算する。
この中に、原始ピタゴラス数がちょうど1つだけあるので、それに対して同じ作業を繰り返す。
有限回の作業でeに辿り着くので、ここまでの経路を出力すればよい。 eに合計でm個のU/A/Dを掛け算してvに辿り着くなら、>>200のアルゴリズムでは
行列の積の計算が3m回必要になる。また、(x y z)が原始ピタゴラス数であるかどうかの判定には、
「x,y,zが負になってないか」「x,y,zに共通の因数がないか」を判定しなければならない。
前者は簡単に判定できる。後者はユークリッドの互除法で判定すれば高速に終わる。
(あるいは、U^{-1},A^{-1},D^{-1}の性質上、前者しか起きないのかも?)
全体としては、このようなアルゴリズムだけでも普通に速いんじゃないかという気がする。
たぶん、この分野ではもっと凄まじいアルゴリズムが希望されているのだろう。 次に、>>191-193のやり方だが、記述を端折りすぎていてよく分からない。
エスパーすると、たぶんこういうことを言いたいのだと思う。
v=(x y z)を原始ピタゴラス数とする。
x=(t^2 - s^2)/2, y=s×t, z=s^2 + t^2 となるような、
互いに素な奇数0<s<tを求める。いつでもこのようにすると、
原始ピタゴラス数は「互いに素な奇数0<s<t」に対応することになる。
すると、>>191-193によれば、U^{-1}v, A^{-1}v, D^{-1}v を計算することは、
互いに素な奇数0<s<tを用いて
(1) 0<s<t−2s
(2) 0<t−2s<s
(3) 0<2s−t<s
を計算することと同じことになるらしい(この順番で対応しているかは知らないが)。 sを基準にして書き換えると、(1),(2),(3)は
s∈(0,t/3)
s∈(t/3,t/2)
s∈(t/2,t)
と同じになる。最初に与えられているのは0<s<tつまりs∈(0,t)だから、
上の3つのうち2つ以上が同時に起きることはない。また、3つそれぞれが
U^{-1}v, A^{-1}v, D^{-1}v のどれかに対応している(らしい)。 よって、>>191-193のアルゴリズムは、たぶん次のようになるのだろう。
v=(x y z)を原始ピタゴラス数とする。
x=(t^2 - s^2)/2, y=s×t, z=s^2 + t^2 となるような、
互いに素な奇数0<s<tを求めておく。このとき、
(1) 0<s<t−2s
(2) 0<t−2s<s
(3) 0<2s−t<s
のうち2つ以上が成り立つことはないので、成り立つものは高々1つである。
もし成り立つものがあったら、それを 0<s'<t' として、今までの操作を繰り返す。
(1)〜(3)のどれもが成り立たなくなったら、その時点で e=(3 4 5) に対応しているので、
そこでやめる。ここまでの過程で、(1)〜(3)のうちどれが成り立ってきたのかという履歴が
U^{-1},A^{-1},D^{-1}の経路にきれいに対応している(らしい)ので、この履歴を出力すればいい。
これでいいのかは知らないが、もしこれでいいなら、
>>191-193のアルゴリズムはとても速いし、面白いと思う。 で、速いし面白いことは大体わかったが、
・ この程度なら、この界隈の人がとっくに見つけてたのではないか?
・ たとえば、>>194の論文で全く同じことやってないか?
という疑問点が生じる。 >>196
方法論として優れているのだろうと思うが
逆問題自体が解決されているとしたら、自分たちの手法の
どこが優れているか明確に書かないといけない
学術論文を書く基本的な訓練を受けてないように感じる
>>198
普通ならarXivに載せておくと良いでしょう
後から誰かとかち合っても記録に残る 次は、「番号」、「原始ピタゴラス数」、「p,q値」を列挙するプログラムです。
http://codepad.org/UhYptqy2
「番号」というのは、私が、原始ピタゴラス数の整理に便利だと考え、勝手につけた通し番号です。
(>>119でアップした、http://codepad.org/VKGibeHo にちょっと手を加えただけのものです)
この「番号」は、三分木構造のどの位置にあるのかを知るのに、便利な指標となっています。
番号に1を加え、3で割って切り捨てすれば、親の番号が判ります。
番号に1を加え、3で割った余りを求めれば、子の枝順位、つまり、長男(=0)、次男(=1)、三男(=2)を判定できます。
簡単に説明すると、番号1が始祖です。その子供が、2,3,4で、2の子供が5,6,7、3の子供が8,9,10、
4の子供が11,12,13、5の子供が、14,15,16、...となっています。
1が第一世代、2,3,4が第二世代、5〜13が第三世代で、14〜40が第4世代、、、(3^(n-1)+1)/2〜(3^n-1)/2 が第n世代 です。
簡単な構造なので、このような樹形図を初めて扱う方でも、各原始ピタゴラス数が、三分木構造のどこに配置されているか
簡単に図示できるでしょう。
この原始ピタゴラス数樹形図を、(p,q)の視点で眺めると、親を(p,q)としたとき、(p,2p+q)が長男、(q,2q-p)が次男、
(q,2q+p)が三男に相当しているようですね。 親のpq値(p',q')から、三人の子のpq値(p,q)を求める方法は、
(p,q)=(p',2p'+q'),(q',-p'+2q'),(q',p'+2q')
それぞれ、長男、次男、三男に相当
子供のpq値(p,q)から、親のpq値(p',q')を求める方法は
(p',q') =(p,q-2p) (3p<q の時;長男→親の変換に相当)
=(2p-q,p) (p<q<2p の時;次男→親の変換に相当)
=(-2p+q,p) (2p<q<3p の時;三男→親の変換に相当)
ですね。 >>193 では
>> {p', q'} = {p, |q - 2q|} として表される。
のようにされていますが、この場合、変換時、p',q'の大小をチェックして、
小さい方をp'、大きい方をq'としなければなりません。
しかし、変換式をここで書いたように固定すると、
p<q ⇔ p'<q'
が成立しますよ。 >>202 >>203 >>204
問題の本質を理解してくださってありがたいが、
そんなに難しいことは言ってないんだ (^_^!)
二つの互いに素な奇数 p, q (0 < p < q)があるとすると、
そこから原始ピタゴラス数 { x, y, z } が求まる。x と y が
決まれば z も決まるので、本質は x, y。
で、奇数のほうが pq、偶数のほうが (q^2 - p^2) /2 だから、
{x, y} から p, q が求まる。
ここで、p × q の長方形を考えて、そこから p × p の正方形を
二個取り去る(面積が 1 になったらそこで終わり。マイナスに
なった場合は「面積の絶対値」を取る)と、p' と q' が出て、
そこから原始ピタゴラス数を計算すると、それが「親」にあたる
原始ピタゴラス数になる。
ピタゴラス数を、「直角三角形の三辺」と考えるより、
「縦横と対角線の長さが自然数の比で表される長方形」
と考えたほうが素朴だろう(だいたい、日常で直角三角形と
いうのはほとんど見ないし)、というのが出発点。 あとは、「互除法と連分数は、同じ概念の二つの側面」
であって、1 + √2 = [2; 2, 2, 2, 2, …]、
φ = [1; 1, 1, 1, 1, …] なんで、
プリンプトン322が計算しているのはこのあたり、
みたいな話につながってく。 >>207
見てますよー。
連分数にしろ図的解法にしろ、あまり一般的な
手法とはいえないので、現在広く使われている
基本の手法とか考え方とかとの相性がよいと
思います。数学をちゃんとやってる人に
してみたら、「こっちの方がわかりやすい」
と思うんじゃないかな。 >>205
じつは、そのあたりはあんまり気にしてないんだ (^_^)
もともと、本筋は「プリンプトン322の解読」のほうなので、
「ひょっとしたら、三千八百年くらい前に、バーニングとホールの
定理を見つけてたんじゃないか?」と思ってる。
だけど、室井和男さんという「塾講師(数学)でシュメール学者」
の方が「プリンプトン322を完全解読!」と宣言して
いらっしゃったのね。で、「くそぅ、先を越されたか!」と
思ってたんだけど、最近になって、その室井さんの解読結果に
穴があったと知ってしまったので、「よし、勝ったぜ!」と
思ったのよ。
だけど、どこに発表したらいいのか分からんのよ。『数学セミナー』?
『日経サイエンス』?『子供の科学』?『ムー』? で、いま
途方に暮れているところ。 >>205
> この程度なら、この界隈の人がとっくに見つけてたのではないか?
おれもそう思ったんだが、ラプラス変換みたいに「いっぺん別の
世界に行って、また戻ってくる」というラプラス変換みたいな
やり口は、物理屋や工学屋のやりそうな手法で、昨今の数学屋さんには
不得手なんじゃないか?と思った。だから、そっち方面で独立に
見つけてる人は たぶんいる。
> たとえば、>>194 の論文で全く同じことやってないか?
・偶数辺と奇数辺があり、斜辺(対角線)は奇数
・偶数辺は4の倍数
・斜辺は ≡ 1(mod 4)
・偶数辺×奇数辺×斜辺は 60 の倍数
あたりで手詰まりになってる。自分でも引っかかったので、
英語だけど風情はよくわかる。
「奇素数が出るとするなら、どこに出るか?」とか
「(m, n で表したときに)奇数辺が平方数の和差になってる
ところから、何か掴めないか?」とかスケベったらしい
コトを考えると、だいたい捕まるというのが体験的に
謂える。
まぁ、原始ピタゴラス数のことだけを考えると簡単なんだが、
「平方数の和差と素因数分解の関係」とか考えると、
そっちの方へ行きたくなる気持はよくわかる。 >>191-193について。
互いに素な奇数0<s<tを任意に取る。
v_{s,t}=( (t^2 - s^2)/2, st, (s^2 + t^2)/2 ) (横表記だけど縦ベクトルのつもり)
と置くと、v_{s,t}は必ず原始ピタゴラス数である。逆に、(x y z)を原始ピタゴラス数とする。
このとき、(x y z)=v_{s,t}となるような、互いに素な奇数0<s<tが一意的に存在する。 Barning-HallのU/A/Dとv_{s,t}の関係について。
互いに素な奇数0<s<tに対して、s∈(0,t)が成り立つので、
s∈(0,t/3)またはs=t/3またはs∈(t/3,t/2)またはs=t/2またはs∈(t/2,t)
のいずれかが成り立つ。すなわち、
(1) 0<2s−t<s
(2) 0<t−2s<s
(3) 0<s<t−2s
(4) s=t/3またはs=t/2
のうち、1つだけが成り立つ。 (1)のとき、0<2s−t<sは互いに素な奇数である。
(2)のとき、0<t−2s<sは互いに素な奇数である。
(3)のとき、0<s<t−2sは互いに素な奇数である。
(1)が成り立つとき、U^{-1}v_{s,t}=v_{2s-t,s} が成り立つ(左辺を計算するだけ)。
(2)が成り立つとき、A^{-1}v_{s,t}=v_{t-2s,s} が成り立つ(同上)。
(3)が成り立つとき、D^{-1}v_{s,t}=v_{s,t−2s} が成り立つ(同上)。
(4)が成り立つとき、もしs=t/2なら、2s=tとなるので、tが奇数であることに矛盾する。
よって、s=t/3となる。このとき3s=tなので、s,tが互いに素であることから、
s=1となり、よってt=3となる。このとき、v_{s,t}=(4 3 5) となり、
これは最小の原始ピタゴラス数である。 >>216-218を踏まえると、こちらがエスパーした>>204のアルゴリズムは、
実際にこのアルゴリズムで正しいことが分かる。
そして、このアルゴリズムは確かに高速だ。行列の積を計算しなくても、
U^{-1}v_{s,t}=v_{2s-t,s}
A^{-1}v_{s,t}=v_{t-2s,s}
D^{-1}v_{s,t}=v_{s,t−2s}
によって、vの添え字s,tの単純計算だけで済んでしまう。とても面白い。 だが、s,tの単純計算の計算量を行列の積の場合と比べてみると、
パラメータの桁数に関するオーダーとしては、定数倍の差しかないことが
分かった(次からのレスで書くが)。なので、オーダーの観点からは、
行列の積を計算してもs,tで計算しても同じオーダーになってしまう。 まず、>>200のアルゴリズムの効率について。当初の>>201では
>(あるいは、U^{-1},A^{-1},D^{-1}の性質上、前者しか起きないのかも?)
と書いたが、2s-tやt-2sが負の場合も含めて
U^{-1}v_{s,t}=v_{2s-t,s}
A^{-1}v_{s,t}=v_{t-2s,s}
D^{-1}v_{s,t}=v_{s,t−2s}
を考察すると、実際に前者しか起きないことが分かる。
なので、>>200のアルゴリズムの効率は、>>201から次のように改良できる。
eに合計でm個のU/A/Dを掛け算してvに辿り着くなら、>>200のアルゴリズムでは
行列の積の計算が3m回必要になる。また、(x y z)が原始ピタゴラス数であるか
どうかの判定には、「x,y,zが負になってないか」を判定するだけでよい。 では、行列の積の計算1回にかかる計算量と、
x,y,zが負になってないか判定するのにかかる計算量は、
それぞれどうなっているか。
v=(x y z)を原始ピタゴラス数とする。x,y,zそれぞれを2進法で表したときの桁数のうち
最大のものをn_{x,y,z}と表す。zの桁数が一番大きいので、実際にはzの桁数がn_{x,y,z}である。
次に、U^{-1},A^{-1},D^{-1}の成分は±1,±2,±3しかないので、(x y z)にU^{-1},A^{-1},D^{-1}を
掛け算すると、n_{x,y,z}の定数倍の計算量にしかならない。
よって、行列の積1回の計算で、n_{x,y,z}の定数倍の計算量にしかならない。
また、「x,y,zが負になってないか」の判定は上位1ビットを見ればいい(そこが符号の役目を
している処理系なら)ので、これは定数時間で終わる。よって、>>200のアルゴリズムを
1操作分やると、n_{x,y,z}の定数倍の計算量にしかならない。
よって、>>200のような普通のアルゴリズムの時点で、かなり効率がよいと言える。 次に、>>204のアルゴリズムの効率について。
(x y z)=v_{s,t}と表して、s,tに対して操作を行うのだから、
n_{s,t}に対する計算量を考えればよい。
(1) 0<s<t−2s
(2) 0<t−2s<s
(3) 0<2s−t<s
しかないので、実質的にはt−2sだけ計算すればよい、これはn_{s,t}の定数倍の計算量で終わる。
n_{s,t}は、sとtの桁数のうち最大のものを表しているが、s<tだから、実際にはtの桁数がn_{s,t}である。
また、x=(t^2−s^2)/2, y=st, z=(s^2+t^2)/2 なので、t^2/2<z<t^2 が成り立つ。
よって、2n_{s,t}−2≦n_{x,y,z}≦2n_{s,t}となることが分かる。
よって、n_{s,t}=n_{x,y,z}/2, n_{x,y,z}/2−1 である。
よって、n_{x,y,z}を基準にしても、t−2sの計算はn_{x,y,z}の定数倍の計算量で終わる。 >>200では、(x y z)→(x' y' z')→(x'' y'' z'')→…
という形でピタゴラス数そのものを変形していくが、
>>204では、v_{s,t}→v_{s',t'}→v_{s'',t''}→…
としてs,tの方を変形していく。
一番最初は、v_{s,t}=(x y z)という関係がある。操作1回のあとの
(x' y' z')とv_{s',t'}については、v_{s',t'}=(x' y' z')という関係がある。
操作1回のあとの(x'' y'' z'')とv_{s'',t''}については 、
v_{s'',t''}=(x'' y'' z'')という関係がある。・・・
このように、>>200と>>204では、各ステップで同じ対象について計算が進んでいて、
各ステップで ”n_{s,t}=n_{x,y,z}/2, n_{x,y,z}/2−1”の関係式が成り立つ。 よって、>>200と>>204は、処理全体が終わるまで見ても
定数倍の違いしかないことになるので、オーダーとしては同じになってしまう。
もちろん、定数倍の部分は>>204の方がずっと小さいので性能が良いと言えるが、
オーダーの観点からは定数倍の差でしかない。 当初の話は、
「行列の積で逆問題を考えると有効な手立てがなくて
未解決問題だったが、連分数や図形で考えると効率よく解決する」
という話だったはず。しかし、行列の積で逆問題をやってる>>200でも、
v_{s,t}のs,tに対する単純計算だけで終わっている>>204でも、定数倍の違いしか
効率が変わらないので、行列の積で不満があるなら>>204でも不満があるはずだし、
逆に>>204で満足なら行列の積の>>200でも満足のはず。 「>>200では不満だが>>204なら満足」という立場を維持するには、
定数倍の部分がとても小さいから>>204で満足、と考えるしかない。
実務で使いたい人ならそういう立場でもいいのだが、
あくまでも理論的な未解決問題として考えたときには、
定数倍の違いしかないアルゴリズムを未解決問題だったとは普通は言わないので、
結局、この手の話で何かが未解決だったというのは考えにくい。
今も未解決のまま残っている問題は実際に存在するのかもしれないが、
少なくともこの話が未解決だったわけではないと思う。 そろそろ連投規制に引っかかる予感。
次に、v_{s,t}ではなく、別の公式を使った場合の>>204について。
互いに素かつ偶奇の異なる正整数0<s<tに対して
w_{s,t}=( t^2 - s^2, 2st, s^2 + t^2 )
と置くと、w_{s,t}は必ず原始ピタゴラス数である。逆に、(x y z)を原始ピタゴラス数とする。
このとき、(x y z)=w_{s,t}となるような、互いに素かつ偶奇の異なる正整数0<s<tが一意的に存在する。
v_{s,t}よりもこっちの方が有名な気がする。 Barning-HallのU/A/Dとw_{s,t}の関係について。
互いに素かつ偶奇の異なる正整数0<s<tに対して、s∈(0,t)が成り立つので、
s∈(0,t/3)またはs=t/3またはs∈(t/3,t/2)またはs=t/2またはs∈(t/2,t)
のいずれかが成り立つ。つまり、
(1) 0<2s−t<s
(2) 0<t−2s<s
(3) 0<s<t−2s
(4) s=t/3またはs=t/2
のうち、1つだけが成り立つ。 (1)のとき、0<2s−t<sは互いに素かつ偶奇の異なる正整数である。
(2)のとき、0<t−2s<sは互いに素かつ偶奇の異なる正整数である。
(3)のとき、0<s<t−2sは互いに素かつ偶奇の異なる正整数である。
(1)が成り立つとき、U^{-1}w_{s,t}=w_{2s-t,s} が成り立つ(左辺を計算するだけ)。
(2)が成り立つとき、A^{-1}w_{s,t}=w_{t-2s,s} が成り立つ(同上)。
(3)が成り立つとき、D^{-1}w_{s,t}=w_{s,t−2s} が成り立つ(同上)。
(4)が成り立つとき、もしs=t/3なら、3s=tとなるので、s,tの偶奇が一致してしまい、矛盾する。
よって、s=t/2となる。このとき2s=tなので、s,tが互いに素であることから、s=1となり、
よってt=2となる。このとき、w_{s,t}=(3 4 5) となり、これは最小の原始ピタゴラス数である。 よって、w_{s,t}を使っても、>>204と同じアルゴリズムが成り立つ。
計算した感触からすると、原始ピタゴラス数を2つの変数で表す公式が得られるたびに、
その公式に対応した>>204のアルゴリズムが必ずあるような予感がする。 >>144 にて私は、全てのピタゴラス数は、単位円上の一つの有理点に対応し、その有理点は
一つの有理数に対応可能だと言うことを指摘しました。
ピタゴラス数を探すと言うことは、有理数を探すことと同値です。
また、偶然にも私は、>>149 にて、「ユークリッドの互除法」は、
「(a と b の公約数)=(a と a-b の公約数) の積み重ねだ」とも指摘しました。
通常ユークリッドの互除法は最大公約数を見つける方法と認識されますが、最大公約数が1
だということになれば、「互いに素」であることを示す道具にもなります。
Mr.Motoさんの
>>{p', q'} = {p, |q - 2q|}
という変換は、pとqの最大公約数を求めるための、途中計算と考えることができます。
その際利用しているのは、「(a と b の公約数)=(a と a-b の公約数)」という内容。
ただし、これを、一歩ずつではなく二歩ずつ行っていると、考えるのです。
このようにして、(1,3)へ到達したならば、元々の奇数の組み合わせ(p,q)は、互いに素だったことを意味し、
同時にそれに対応する原始ピタゴラス数を表す有理数、指標となります。
このチェックの際辿った、(p,q)の変換経路は、ピタゴラス数を三分木構造に当てはめたときの、
樹形図上の経路そのものです。 親の方へ向かう変換は、最大公約数の計算or互いに素かどうかのチェックであり、
子の方へ向かう変換は、有理数の探索 or 作成に相当します。
ただ、2段飛びなので、全ての有理数を網羅することはできません。
分母分子とも奇数の場合しか回れませんから。
しかし、「ピタゴラス数の探索」という意味では、(奇数、奇数)の組み合わせだけで必要十分です。
一組のピタゴラス数に対応する単位円上の有理点は実は二つあります。(例:(5/13,12/13)と(12/13,5/13))
その有理点に対応する有理数は、一方は分母分子が両方とも奇数だし、もう一方は分母分子が、
偶数奇数混合型だからです。(先ほどの例では、1/5と2/3が対応)
(3,4,5)にUAD行列を施して制作される原始ピタゴラス数樹形図は、
(1,3)に>>209で記した変換公式を施して制作する有理数樹形図と同一で、お互いに変換可能です。
同様に、(1,2)に>>209で記した変換公式を施しても有理数樹形図ができますが、これらも、お互いに変換可能です。
そして、下二つの有理数樹形図で、全ての有理数を過不足無く網羅します。
UAD行列を使う場合も、(p,q)変換公式を使う場合も、プログラム的にはほとんど差はありません。
前者は同時に三数を扱う一方、後者は二数だけなので、この分高速になります。
ただし、「原始ピタゴラス数を順に表示する」というのが目的であった場合は、変換コストを払う必要があるため、
前者の方が速いかもしれません。特定の場合だけ表示するのであれば、後者の方が高速でしょう。 ■ このスレッドは過去ログ倉庫に格納されています