素因数分解、累乗数が好き！コミュの【ベースキャンプ１】素因数分解

「素因数をちょうど4個」が「4つの異なる素数の積」という意味ならば、
6の次は1092のようです。

6^6-1=5*7*31*43
7^6-1=2^4*3^2*19*43
420^6-1=13*151*419*421*1171*13537
462^6-1=373*409*461*463*523*571
882^6-1=19*337*881*883*2311*40897
1092^6-1=1091*1093*1191373*1193557
1428^6-1=883*1427*1429*2311*2037757
1943^6-1=2^4*3^6*7*181*241*971*2239*6949

「素因数が4種類」という意味ならば、
4,5,6,7,8,15,18,28,168,728,1092,…
のようになるようです。

↑ありがとうございます！

「素因数をちょうど4個」＝「4つの異なる素数の積」の意味です。

＞このあとは7、間が飛びますが、

などと書き込んだので、誤解を招きました。
この「7」は書いた覚えがなかったのですが、キーボード上で手が滑ったようです、申し訳ない。。



nは「初期を除き、一般には42の倍数」ということは、考えてわかったのですが。
いやあ、思ったよりもいろいろと割り切れちゃうものですね。


＞6^6-1=5*7*31*43
＞1092^6-1=1091*1093*1191373*1193557

恐縮ですが、3番目も出ますか？

10万までで以下の13個でした。

6^6-1=5*7*31*43
1092^6-1=1091*1093*1191373*1193557
1932^6-1=1931*1933*3730693*3734557
2730^6-1=2729*2731*7450171*7455631
4158^6-1=4157*4159*17284807*17293123
6552^6-1=6551*6553*42922153*42935257
11172^6-1=11171*11173*124802413*124824757
25998^6-1=25997*25999*675870007*675922003
30492^6-1=30491*30493*929731573*929792557
55440^6-1=55439*55441*3073538161*3073649041
76650^6-1=76649*76651*5875145851*5875299151
79632^6-1=79631*79633*6341175793*6341335057
85092^6-1=85091*85093*7240563373*7240733557

1000万までのリストです。

6,1092,1932,2730,4158,6552,11172,25998,30492,55440,76650,79632,85092,
102102,150990,152082,152418,166782,211218,235662,236208,248640,264600,
298410,300300,301182,317772,380310,387198,441798,476028,488418,527982,
540540,550662,569268,591318,672378,752682,778512,825552,880950,966210,
970788,991620,1053990,1062978,1081710,1082382,1110312,1115268,1203930,
1224888,1243578,1259538,1275540,1324680,1329762,1348872,1368528,1372980,
1378188,1423128,1505658,1541358,1600788,1686342,1699782,1727292,1750182,
1855518,1984458,2018898,2045610,2053422,2070180,2093700,2110290,2136288,
2167368,2200590,2242212,2285640,2321382,2326212,2332512,2387952,2433522,
2437638,2518068,2605848,2664690,2688420,2723910,2749362,2755032,2799132,
2906568,2937732,3089478,3103800,3129462,3142020,3165708,3176838,3198930,
3212118,3278982,3326568,3443622,3484572,3507042,3579870,3701628,3719982,
3743040,3774708,3829182,3840480,3841992,3911250,3924102,4025910,4031118,
4049430,4055898,4057872,4098570,4175472,4178328,4214280,4266528,4299960,
4325160,4338222,4342968,4369428,4379718,4463550,4478082,4515630,4762212,
4812192,4848228,4858560,4867338,4978428,5006610,5091660,5162220,5210772,
5368608,5406198,5553828,5652402,5745558,5769582,5840100,5856690,6026748,
6054930,6090000,6108942,6146532,6279462,6302142,6474930,6478500,6491730,
6518442,6561198,6570900,6572748,6585642,6770610,6781110,6801522,6916518,
6924582,7002450,7024542,7038192,7086618,7101738,7199262,7324380,7335972,
7355628,7412160,7440048,7448070,7456512,7487592,7710612,7721070,7746018,
7790622,7813512,7864122,7913430,8071518,8151150,8205078,8219778,8327382,
8329692,8355690,8358798,8364930,8368248,8385678,8411760,8445528,8576568,
8600592,8659098,8704122,8710422,8767920,8783040,8797488,8825460,8957130,
8961792,9014208,9064440,9125508,9184602,9262008,9344328,9392628,9435132,
9442230,9478308,9520308,9542988,9592380,9731568,9788898,9815232,9837282,
9919938

ありがとうございます！

やはり、飛ぶときは飛びますね。
こういう不規則な分布は、味わいがあってよいですね。

コメントNo.66で、もう1箇所間違えていました。

＞n=420,462,882,1092,1428,1943...となるのではないかと予想しています。

この「1943」は「1932」の間違いです。
よほど朦朧としていたようで、申し訳ないです。。

ともあれ、42*1から42*50までシンプルに検討して6個が残ったので、予想として出したのですが、2個が生き残りました。

No.66〜72の内容を、自分の日記で紹介しました
http://mixi.jp/view_diary.pl?id=1270253236&owner_id=5383118

もちろん、一般世間からはご理解いただけません。
私のマイミクさん方も、例外ではありません。

n^6-1の因数から、
オイラーの素数式
f(n)=n^2+n+41
を思い出しました。

この式は
f(n)=n(n+1)+41
と変形できるので、
n=40,41などは合成数になるけれど、
n=0〜39がすべて素数になるそうで、
素数生成確率の高い公式として有名ですが、
42=2*3*7から41が出てきたのだと
今回の議論を読んで思い当たりました。

＞42=2*3*7から41が出てきたのだと

ほほう。。
最初の3個の素数の積30は、なかなか味わい深い振舞いをするように思います。
42も、意外に活躍しているのかな？

西暦の年月日を8桁の数で表すとき、まれに回文数になります。
1000年〜9999年の9000年間で、331回のはず。

昨日は、そのうちのひとつでした；20100102。

この8桁回文数は、必ず11で割り切れます。

たとえば、20100102=2*3*11*37*8231ですね。

こんにちは、適当な素因数分解ソフトがないので、学生さんに
頼んで開発してもらいました。学部学生の小林正資君の開発ツ
ールです。Twitterで　@factrbot に向けて、素因数分解して
ほしい数を半角で入力すれば、素因数分解した結果を返しても
らえます。@factrbotをフォローしておいてください。なお、
サーバの処理能力の関係で、１０進数４０ケタ程度までの数で
あれば大概数十秒以内で素因数分解します。

開発途上ですので、予告なくシステムを停止する場合がありま
す。ご容赦ください。

また、mixiアプリでなくて、ごめんなさい。

【入力例文】
@factrbot お願いです、1234567890123456789012345678901234567
を素因数分解してください。

>76
偶数桁で回文数なら桁数によらず、常に１１で割り切れます。

>77
1234567890123456789012345678901234567
= 43 * 1283 * 2363743 * 27740913371 * 341270582221531

かつて、エクセルのシートとVBAで適当に作りかけた素因数分解プログラムを思い出しました。

素因数分解でよくある、
「筆算のわり算の記号をひっくり返したようなものを書いていく」
のを再現したもの。


これとは別に、小さい方から素数を見つけるたびにシートに書き出していくプログラムも作ったことがあり。

これを発展させて、次回の検索時にはそこにある素数を使って素数判定を行う、という素数判定・検索プログラムに変更して素数判定のスピードアップをはかる。


この２つのプログラムを組み合わせてあげると、最初は遅いけど、何回か素因数分解しているうちに、処理速度が向上していくような動きをするはず。


…とゆーところまで考えてから、まだ手をつけていません

こんにちは、

昨夜、ご紹介したTwでの素因数分解ツールですが、誰か感の良い人は
いくつかの実験から、どのようなアルゴリズムに基づいているかとい
うことを推定されると思っていました．

アルゴリズムはp-1法を実装しています、コアはGMPで作り、Rubyで
構築してます（構築と言うほどではないでしょうけど．．．たった
数十行ですから）。もちろん、前処理として、小さな素数で割って
みる試行割算法は取り入れています。

ですから、素因数分解する数で、その素因数のひとつpにおいて、
p-１が小さな素因数から構成されている場合は、高速で素因数分解
されます。なお、素数判定はラビンを使っています。p-１の最大素
因数がたかだか１０＾｛８｝以下ならば一瞬（数秒以内）で素因数
分解します（サーバの性能を言わなければ無意味ですが．．．普通
の低価格パソコンです）。つまり、どのような形の合成数だとして
も２０桁以下であれば一瞬で、３０桁以下であるならば、ほとんど
の合成数が、さらに４０桁以下でも高い確率で数秒以内で素因数分
解します。

意外に、一般的な数の素因数分解においては、p-1法は強力というこ
とですね。もちろん、数百桁という数の素因数分解には向いていませ
んが。

ちなみに、小さな素数で割る方法（ブルートフォース）であれば、
２０数桁程度がせいぜいでしょう。４０桁ぐらいになると、完全に
素因数分解するのはほとんど不可能になります、よほど小さな数の
素因数をもっている場合を除いては。

素数や素因数分解に興味を持っていた学生時代（２０数年前）、
GMPやPari?でp-１法や連分数法、さらに楕円曲線法、そして
二次ふるい法などを実装して、Cunningham Project に挑んでい
ました。当時は計算機センターや研究室の数十台のWSを使って
意味のある結果を残せたのですが、現在では個人ではこの手の
プロジェクトは無理になってきましたね。

整数Nがp-smoothである確率はpower(logN/logp,-logN/logp)といわれていますから、２０桁の素因数をPとしたとき、P-1は１割くらいで10^8以下の素因数しか持たないですね。10^10まで広げれば25%までその確率は上がります。
しかし、最悪のケース、N-1が2*素数だったら目も当てられませんが。

私もUBASICを使って、2^257-1がこの方法で大きな素因数をひとつ結構簡単に見つけられるとか、やったことがあります。

ところでmoriiさんもcunningham projectの結果を提出されたことがあるのは知りませんでした。陶山さん、木田さんの結果が多数提出されていたのと同年代でしょうか。
とはいえ、数十台のPC,WSが使えるのならば、ターゲットを上手く選定すれば今でも参加できそうなきもしなくもありませんが。数年前も個人で10^360+1を分解された方もいらっしゃいましたしね。確か４台くらいのPCで分解されたと思います。

きりんさん、ご無沙汰してます。

cunningham projectを知ったのは本業のほうの通信方式の研究
での拡散系列の生成において2^{m}-1の素因数分解の必要性か
らです。その前から木田先生らの上智大の講究録で円分数関係
の論文で彼らの素因数分解のアプローチには興味を持ってまし
た。学生時代の主研究テーマの一つが「有限体の演算構造」で
したのでその関係での興味です。

素因数分解への興味は、1980年代中頃の第一期で、素数の理論
関係とパソコン（PC88やPC98等）によるプログラミング中心、
1990年代中頃の第二期での素因数分解プログラム開発で、これ
以降は素数探索がメインになってしまいました。PC,WS数十台
による素数探索、および探索プログラム、システム開発、2000
年代前半の第三期では分散環境による素数探索です。約10年毎
に素数関係でのマイブームの到来ですが、次回はまだ来そうに
ありません。

> prof_moriiさん

本業が関係するだけ良いと思います。私はまったく関係が無くて、本当に趣味のレベルです。

Cunningham projectは今は過去の素因数分解の結果も見ることができますが…。
見落としがあるかもしれません。

Morii先生は今中断中のようなことを話していますが、カレン数の素数探索はしていたと思っていました。

こんにちは、講義が終わって一息ついている合間にお返事。
残念ながら「情報伝送?」という講義では素数は出てきま
せん。CDMA（符号分割多元接続）のところで若干、関係す
るので説明しても良いのですが．．．素数の活躍について^^;

余談でした。

カレン素数なのですが、1997年前後は盛んに探索していた
のですが．．．もちろん、本業ではありません。本業に
関係するとすれば分散環境構築の例として、です。幸運に
も恵まれたのか、当時の最大カレン素数が求められたわけ
です。

7年間、防衛しましたが^^;　2005年に知らないうちにタイ
トル返上させられてしまいました。
http://primes.utm.edu/top20/page.php?id=6
即、引退していたのですが、思い立ったように2008年、現
役復帰しようとしましたが、タイトルには遠く及びません。
（やはりPrimeGrid/Bonicに対抗するには新規にアルゴリズ
ム開発とシステム構築を行わなければ無理でしょう）半年も
経たないうちに再度引退、現在に至るです。
以下はその残骸です。
http://srv.prof-morii.net/~morii/PrimeGrid/PrimeGrid_index.html

現在趣味で素因数分解の研究している者です。

素数生成と素数判定について、以下の予想が得られたのでカキコしておきます。

?素数生成
　（２＾N＋１）/３　N：２を除く素数　は常に素数（N→∞については未証明）
　N：３　　→　３
　N：５　　→　１１
　N：７　　→　４３
　N：１１　→　６８３
　N：１３　→　２７３１
　N：１７　→　４３６９１
　・・・・

?素数判定
　１０＾（N−１）−１　（N：２と５を除く素数）はNで割り切れる（N→∞については未証明）
　N：３　　→　９９/３＝３３
　N：７　　→　９９９９９９/７＝１４２８５７
　N：１１　→　９９９９９９９９９９/１１＝９０９０９０９０９
　N：１３　→　９９９９９９９９９９９９/１３＝７６９２３０７６９２３
　N：１７　→　９９９９９９９９９９９９９９９９/１７＝５８８２３５２９４１１７６４７
　・・・・

予想ですので、本当に使えるかわかりませんが、これが正しいことを前提に
現在研究中です。

↑もんきちさん、予想の表明ありがとうございます。

せっかくですから、このコミュ名物（？）の、問題の一種としてあつかいましょう。
上の2つの命題の、いずれにつきましても；

○反証を思いつく方は、いま以降いつでも反証をコメントしてください。

○肯定的に証明できる方は、48時間ルールにて、12日11:44以降に証明をコメントしてください。

?
N:29 → 178956971 = 59 * 3033169
N:37 → 45812984491 = 1777 * 25781083
N:41 → 733007751851 = 83 * 8831418697
N:47 → 46912496118443 = 283 * 165768537521

?
フェルマーの小定理

らすかるさん

?への早速の反証、ありがとうございます。
意外と小さい数で反証できてしまったわけですね・・・（＾＾；
もうちょっと大きい数字まで検証してからカキコすればよかったと反省・・・orz

?は既に知られたものだったんですね
自分で気づいた時には小躍りしたものですが。。。（笑

さすがにレベルが高いですね＾＾
また新たな発見があればカキコしたいと思います。

もんきちさん

1.2.に関してはらすかるさんの書かれた通りですが、補足を。Nが大きくなると素数となる確率はどんどん下がります。

N=23以降、(2^N+1)/3が素数となるのは、Nが1200未満の場合、23, 31, 43, 61, 79, 101, 103, 127, 167, 191, 199, 313, 347, 701だけです。

2011年11月10日現在で知られている最大の(2^n+1)/3の形をした素数は2007年に発見された(2^42737+1)/3 で、1万2865桁の素数です。この形の厳密な素数判定は難しく、この程度の大きさが限界となっています。ただ、これより大きな数でほぼ間違いなく素数であるが、確定できない、というものがあります。

この形をした、ほぼ間違いなく素数であると知られている最大のものは(2^4031399+1)/3で、121万3572桁の整数です。桁数でいえば、100倍もの開きがありますね。

皆さん、さっそくにありがとうございます。

＞?は既に知られたものだったんですね

結果として定理そのものでしたから、シニア問題扱い（48時間ルール適用）は取り下げます。

このコミュではいつでも、予想の表明は歓迎です。
証明に定理が適用される場合でも、若干の論証を要するものは、いい問題になると思います。



さて、このコミュにふさわしいテーマとなりましたので。

簡単な形の素数形式が見つかった話を聞きませんので、「(2^N+1)/3が常に素数」ということはないだろうな、という感じはしました。
このことは、どの程度一般的に言えるのでしょうか。
たとえば、

○「a^N+b」（a,bは定数）という形が常に素数となる、ということはない。

と証明されているのでしょうか。
どなたか、ご存じでしたら教えてください。

>○「a^N+b」（a,bは定数）という形が常に素数となる、ということはない。
>
>と証明されているのでしょうか。
>どなたか、ご存じでしたら教えてください。

はい、そういうことは生じません。

あるNにおいて、a^N+bが素数であったとします。これをPとします。
ここで、a,bはNと互いに素であるとします。
（なお、a,b,Nが互いに素で無い場合は、その式が素数にならないことは示せますが、簡単なのでここでは割愛します。）

これを合同式を使うと、以下のようになります。
a^N+b ≡　0 (mod P)
a^N ≡ -b (mod P)

フェルマーの小定理より
a^(N+k(P-1)) ≡ -b (mod P)
であることが分かります。これは、a^N+bという式において、Nの値が少なくともP-1の周期で、Pで割り切れる場合が存在するということを示します。つまり、常に素数ということはa^N+bがNに関わらず常に一定になる場合だけということですが、それは無いので、そういう式は存在しないことが分かります。

なお、自然数Nが素数である確率は素数定理より、ほぼ1/log(N)であることが示されています。logNに反比例する、ということは、素数の確率はその数の桁数に反比例しているということです。

私は趣味でk*2^n+1 (ここでkは比較的小さな奇数、nは自然数）という形式をした素数を探していますが、経験的に素数が現れる頻度は、その桁数に反比例していることを確かめています。

ネットで検索すると、(2^n+1)/3の形式をした素数および素数候補の表があったので、紹介します。先の書き込みとも重複しますが、n>1200の場合、

n=1709, 2617, 3539, 5807, 10501, 10691, 11279, 12391, 14479, 42737は素数であることが確認されています。以降 83339, 95369, 117239, 127031, 138937, 141079, 267017, 269987, 374321, 986191, 4031399が素数ではないかと考えられています。これらはフェルマーテストなどで、素数である確率が非常に高い、と判定されているものです。特にn<400000以下においては、これ以外には素数および素数候補はありません。

>コメントNo.92、きりんさん

ようやく落ち着いて読むことができ、納得できました。

a^N ≡ -b (mod P) （式1）

またフェルマーの小定理により、この場合、
a^(P-1) ≡ 1(mod P) （式2）

左辺、右辺とも、式1に式2の値をk回掛け合わせると、
a^(N+k(P-1)) ≡ -b (mod P)

ということですね。
ありがとうございます。

binjiさん

どういたしまして。
補足として、a=1であれば成り立ちますが、それは求める式ではないですからね。

実は、この証明は私が思いついたものではなくて、ネットで回答みたいなものが無いか検索して、それを元に少しアレンジしたものです。もともとのねたは
整数の係数を持った多項式f(n)が全て素数を示すことがあるか？という反証を示すための証明があり、それをヒントに書きました。この反証も同じような方法で示すことができます。

つまり、オイラーの式のように、an^2+bn+cというような形式でも素数だけ登場する、ということはありえない、ということです。２次式に限らず、何次式でも同様です。

ところが、面白いのは、最近になってan+bという式において、連続する整数nを代入すれば、無限に長い素数列を作ることができるようなa,bが存在する、と証明されたことがニュースになったことです。

ぱっと見て、「えっ？それは矛盾するんじゃ？」と思わせるこれらがともに証明されている、というところがまた数学の奥深さではないかと私は考えています。
数学を専攻しているわけではないので、これ以上はご容赦を。

> 最近になってan+bという式において、連続する整数nを代入すれば、
> 無限に長い素数列を作ることができるようなa,bが存在する

「無限に長い素数列」ではなく「いくらでも長い等差素数列が存在する」ですよね？

らすかるさん

自分の勉強のための聞きたいのですが、その表現によって生じる違いは何でしょうか？それがよく理解できないのです。

「無限に長い素数列を作ることができる」だとすると、
あるa,bに対して（n≧1に対して）an+bがすべて素数になることになります。
「いくらでも長い等差素数列が存在する」だと、
「どんなに大きなNに対しても1≦n≦Nのときにan+bが素数になる」
という（Nに依存する）a,bが存在するという意味です。
「いくらでも長い」は、長さは有限であり、その有限の値を
いくらでも大きくできるということです。
「無限に長い」は長さが無限ですから意味が違いますね。

らすかるさん

返答ありがとうございます。
いくらでも長い、は有限、というのは理解が困難ですが、そういうものだと思っておきます。

「有限」という表現はわかりにくかったかも知れませんね。
「長さが無限」ではないと言いたかっただけです。
「いくらでも長い」は「どんな長さでもとれる」とか
「とれる長さに上限がない」という意味です。
いずれにしても「長さが無限」とは違いますね。

いや、やはり理解は難しい。
ただ、言いたいことをまったく理解していないわけではないですよ。いくらでも長く＝有限と理解すれば、私の示した事柄が矛盾無く言える訳ではないかと思います。その問題が解消できるのではないかと思います。

それに、ak+bにおいて、連続するk区間が素数となるなら、ここでaの値はa#の倍数であり、その値は最低でも荒い近似でexp(k)程度にまでなります。その値を差し置いて無限というのにも、自分で書いておいて何ですが何か引っかかるものがあるのも事実です。

具体的に言うと、
10項からなる等差素数列は存在する。
100項からなる等差素数列も存在する。
1000項からなる等差素数列も存在する。
10000項からなる等差素数列も存在する。
この先はいくらでも続けられるということが証明されたから、例えば
100000000000000000000000000000000000000項からなる等差素数列も存在する。
しかし
無限項の等差素数列は存在しない。
ということです。

やはり、難しいです。（笑）

無限に長い素数列が作れないのは明らかですよね。
an+b（a≧2,b≧1）において
b＞1 ならば n=bのときan+b=ab+b=b(a+1)となり素数でない。
b=1 かつ a=2 ならば、n=4のときan+b=9となり素数でない。
b=1 かつ a＞2 ならば、n=a-2のときan+b=a(a-2)+1=(a-1)^2 となり素数でない。
よって無限に長い素数列になることはなく、
どんなa,bを持ってきても必ず有限個で終わります。
その「有限個」の個数としてどんな大きな数を指定されても、
その長さの素数列を生み出すa,bが存在する、という定理ですね。

色々書いていただいて、努力されているとは思うところ、申し訳ないのですが

どの長さでも指定できる＝有限、ということですが、それが納得できるかというと、それが難しい。無限がありえないなら、どの長さでも指定できる、という言い分は破綻しているんじゃないか？というのが、私の正直な感覚です。
数学を専攻している人から見れば、それが息をするのと同じくらいに当たり前なのでしょうが、工学部出身のわたしからすれば理解が難しいところです。

なので、そういうものなんだな、と定義的に理解するのみです。

現在、実際知られている最長の等差素数列の長さがたったの２６個だってことは、ネットで検索するまでもなく知っているのですが...