・緊急の因数分解                        GAI 氏

 ある会議中、あなたはどうしても「123456789」の数字の因数分解を知る必要に迫られた。
あいにく計算機付アイフォンは会議室に持ち込んでおらず、使えるのはペンと紙のみ。一時
間内にその結果を知る方法は見つかるか?


 DD++さんからのコメントです。(平成27年3月9日付け)

 確か、「3^2×3607×3803」だったはずなので、紙とペンを使って掛け算の筆算で確認。も
し、「123456789」にならなかったら、多分4桁どっちか記憶違いなので、3607か3803で割り算
してみれば、多分見つかるでしょう。あくまで「私の脳内にある情報は何でも使ってよい」なら、
ですが。

 これとか、「1111111=239×4649」とか、そういうのはなぜか覚えています。


 S(H)さんからのコメントです。(平成27年3月9日付け)

 会議を抜け出し、脳内に何もなくズルしかなく、数式ソフトを利用。


 GAI さんからのコメントです。(平成27年3月9日付け)

 うへェ〜、DD++さん、覚えてらっしゃる!!ガウスやオイラーみたいですね。よほど幼少の
頃から数字でお遊びされたんですねェ〜。一般の人達にも通じる方法を教えて下さい。


(コメント) 手計算では、123456789=32×13717421 までが限界ですね!あとは、
      13717421が素数なのか、合成数なのかの判断待ちです。


 GAI さんからのコメントです。(平成27年3月11日付け)

 自然数nが2つの平方数の差で構成できる条件を調査してみた。

  n=x2-y2=(x+y)(x-y)=pq (x、yは、x>yの自然数、p、qは素数)

の形をとれる割合を調べてみると、1≦n≦100 の範囲では、n=pq と2つの素数の積で構成
されているパターンが30通りで、この中で、x2-y2で書き直せるものが16通り存在した。
(なお、x-y≠1)
 1≦n≦1000の範囲では、288通り中196194通りが、n=pq=x2-y2 への書き直しが可能
であった。

 したがって、その割合は196/288=0.6805・・・・。194/288=0.6736・・・・。約67%の高い割合で
平方差の姿であることが起こる。

 そこで、123456789=9*13717421の n=13717421に対し、13717421=n=x2-y2 なる自然数x、y
(x>y、x-y≠1)が存在しているかを探す。

 ここに、フェルマーが編み出した方法があり、もし、y=0 なら n=x2 よって、x=√(n)

しかし、当然、y≧1で、xは自然数より、xが取り得る値は、x=floor(√(n))+1 以上

 この時、y=floor(√(x2-n))

ここで、w=abs(x2-y2-n)なる2つの差にあたる値をチェックする。

(w=0ならピタリx、yが求める自然数、そうでなかったらx=x+1で再びチェックする)

これを、n=13717421で実行すると、

x=floor(sqrt(13717421))+1=3703+1=3704 (3703^2=13712209,3704^2=13719616より)

このとき、

y=floor(√(x2-n))=floor(√(3704^2-13717421))=floor(√(2195))=46 (46^2=2116,47^2=2209より)

この組では、 w=abs(x2-y2-n)=abs(3704^2-46^2-13717421)=abs(79)=79

そこで、x=3704+1=3705

 y=floor(sqrt(3705^2-13717421))=floor(sqrt(9604))=floor(98)=98

今度は、w=abs(3705^2-98^2-13717421)=abs(0)=0 !!!

これは、13717421=3705^2-98^2 が起こっていることを示す。そこで

  (3705+98)*(3705-98)=3803*3607

の分解にできる。(勿論3803,3607が素数であることを確認すべきだが時間がない!)

 なお、これは、後で計算機で調べたら、123456789が幸運であったに過ぎず、例えば、
n=126619 なら、x=356、y=10 からスタートしてxを一つずつ増やしていき、207回目で、x=562、
y=435になったとき、やっと、 126619=562^2-435^2=(562+435)*(562-435)=997*127 が見つ
かる。

 こたつに入って読書していた時、ふと123456789の素因数分解が知りたくなった。こたつを
出て、机の上のコンピュータまで行けばすぐに知れるのだが寒くて億劫だったので、何とか
素因数分解を探してみようと挑戦していたが、なかなか難しくして、どうしたらいいのかさえ手
懸かりが掴めなかった。

 こうしてみると、同じような疑問を抱いたであろうフェルマー氏はなんと見事にこの手懸かり
の手綱に手を伸ばし手に入れたのであろうと感心する。拍手、拍手、拍手。

 でも計算ソフトの中ではどんなアルゴリズムで効率よく素因数分解をやっているんだろう?
たとえ、どんな大きな数でも、たちどころに結果が返ってくるけれども・・・。


 DD++さんからのコメントです。(平成27年3月12日付け)

 これもまだまだ幸運な例でしょう。最悪なのは選んだ数字が実は素数だったとき。この方法
は結局のところ、素因数分解の総当りのやり方を変えているだけなので、「123456789は割っ
てみる素数として3600から始めると3607がすぐ見つかるから早い」というのと同じレベルの主
張でしかないように思いますが……。


 らすかるさんからのコメントです。(平成27年3月12日付け)

 書き直しが出来ないものって、2×素数の場合だけですよね。だから、最初から奇数なら
「書き直しが出来ない場合」はありませんので考えなくてもよいと思います。

 それで、n≦100の場合は、

2×(3〜47)が14個、3×(5〜31)が9個、5×(7〜19)が5個、7×(11,13)が2個、14+9+5+2=30個

うち14個は2×素数なので残りの16個がx^2-y^2の形にできる。これは一致しています。

n≦1000の場合は、

2×(3〜499)が94個 、3×(5〜331)が65個 、5×(7〜199)が43個 、7×(11〜139)が30個
11×(13〜89)が19個 、13×(17〜73)が15個 、17×(19〜53)が9個 、19×(23〜47)が7個
23×(29〜43)が5個 、29×31が1個   計288個

 ここから2×素数の94個を引くと194個なので、x2-y2の形に出来るのは194個ではないで
しょうか。


 GAI さんからのコメントです。(平成27年3月12日付け)

 メモに書いていた、平方差で表せない候補を目で数えていたため、94個あるのを92個と
数えてしまっていました。(メモは正しかった。)らすかるさんの指摘どうり、288-94=194個が
n=pq=x2-y2 型へできました。(→ 一覧

 どうもまだ手作業の割合が多く、間違いを生じる部分が多発する。作業をコンピュータにま
かせる努力をしよう。もっと範囲を広げたら何割ぐらいが平方差で表せますか?

 プログラムの練習で、nの範囲を広げて2つの異なる素数の積であるものの内で、2つの
平方数の差に書き直せる(奇数グループ)の割合を自動で求めてみました。どなたか検証
願います。これを手計算で確かめていたら一生かけても手に入れられないですよね。

n≦100 16/30=8/15≒0.53333・・・
n≦1000 194/288=97/144≒0.6736・・・
n≦10^4 1932/2600=483/650≒0.7430・・・
n≦10^5 18181/23313≒0.77986・・・
n≦10^6 168330/209867≒0.8020・・・
n≦10^7 1555366/1903878=777683/951939≒0.8169・・・
n≦10^8 14424896/17426029≒0.8277・・・


 らすかるさんからのコメントです。(平成27年3月12日付け)

 全部合ってました。その先は1に収束しそうな雰囲気なので、それを示してみようかと思い
ましたが、結構難しいですね。

                                             投稿一覧に戻る