数論

ここでは、「数論」 に関する記事を紹介しています。

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
ついに素数全書キター

表紙はこんな感じらしい:

スポンサーサイト
よく分からんが、「あなたの整数度をはかります」らしい

「整数検定パート1」


整数検定パート1 powerd by けんてーごっこ




いちおう全問正解してみる。が、問題がなんか自動生成っぽいなぁ。
合格したようなので、認定証がもらえた。









やった!!11

自分の整数度は高いらしいので、とりあえず安心してみる


よくわかんね
さっきの耐久数の続き

26888999でググってみた。

素数と合成数等に関する話題
なんか知らない言語だな、と思ったら APLだった!。びっくり。
耐久性の値ごとの頻度分布を求めていたりして面白い。自分はAPLが読めないので残念。あとで解読したい。ちなみに耐久性は英語でpersistenceといらしい。感謝。


耐久数を持続係数という流儀もあるらしい。
【問題80】「持続係数」とは
ここによると、

持続係数が6である最小数は6,788だそうです。
持続係数が7である最小数は68,889だそうです。
持続係数が8である最小数は2,677,889だそうです。
持続係数が9である最小数は26,888,999だそうです。
持続係数が10である最小数は3,778,888,999だそうです。
持続係数が11である最小数は277,777,788,888,899だそうです。
ガードナー数学マジック「超能力と確率」超能力と確率 (ガードナー数学マジック)より

とのこと。この本か?
超能力と確率 (ガードナー数学マジック)超能力と確率 (ガードナー数学マジック)
(1996/05)
マーチン ガードナー

詳細



『各位の数の積』解答
によると

例によって、On-Line Encyclopedia of Integer Sequences で検索してみました。
今回の問題と同値ではないですが、
Smallest number of persistence n over product-of-nonzero-digits function

上記の表題で数列がありました。
何度か改訂があったことが予想されます。
最新のものは以下の通りです。

0 0
1 10
2 25
3 39
4 77
5 679
6 6788
7 68889
8 2677889
9 26888999
10 3778888999
11 2677777778899
12 77777777788888888888899999

13番目まで記載がありました。
一般式がないところをみると、未解決の問題のようです。

ああそうか、On-Line Encyclopedia of Integer Sequencesを見るという手があるな。
A014120 Smallest number of persistence n over product-of-nonzero-digits function.
最新情報によると

0 0
1 10
2 25
3 39
4 77
5 679
6 6788
7 68889
8 2677889
9 26888999
10 3778888999
11 267777777889999
12 77777777788888888888899999
13 37777777777777777777777777778888889999999999999999999

らしい。あと似たようなのいくつか:
A003001 Smallest number of persistence n.
A046149 Smallest n-digit number with maximal multiplicative persistence A014553.
こりゃ総当りできる範囲を明らかに越えている。どんな工夫してんだろ。

リンク先見て吹いたw
また更新されている。鬼だ
# b014120.txt - Table of n, a(n) for n=0..14 - Ray Chandler (rayjchandler(AT)sbcglobal.net), Mar 18 2009

0 0
1 10
2 25
3 39
4 77
5 679
6 6788
7 68889
8 2677889
9 26888999
10 3778888999
11 267777777889999
12 77777777788888888888899999
13 37777777777777777777777777778888889999999999999999999
14 55555555555555555555555555555555555555555555555555555555555555555577777777777777777779999999999999999999999999999999999999

下位の桁は9が並びそうだけど、上位桁はよく分からんな。てかこれ最小性は本当に証明できているのか?




c_sharpの日記さんのところの
2009年04月19日(日)に耐久数っぽい話が。



MathWorldに記事発見:
Multiplicative Persistence
参考文献あった。引用する:

REFERENCES:

Beeler, M. Item 56 in Beeler, M.; Gosper, R. W.; and Schroeppel, R. HAKMEM. Cambridge, MA: MIT Artificial Intelligence Laboratory, Memo AIM-239, p. 22, Feb. 1972. http://www.inwap.com/pdp10/hbaker/hakmem/number.html#item56.

Carmody, P. "OEIS A003001, and a 'Zero-Length Message'." 23 Jul 2001. http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0107&L=NMBRTHRY&P=R1036&I=-3.

Gardner, M. Fractal Music, Hypercards, and More Mathematical Recreations from Scientific American Magazine. New York: W. H. Freeman, pp. 170 and 186, 1992.

Gottlieb, A. J. Problems 28-29 in "Bridge, Group Theory, and a Jigsaw Puzzle." Techn. Rev. 72, unpaginated, Dec. 1969.

Gottlieb, A. J. Problem 29 in "Integral Solutions, Ladders, and Pentagons." Techn. Rev. 72, unpaginated, Apr. 1970.

Guy, R. K. "The Persistence of a Number." §F25 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 262-263, 1994.

Pickover, C. A. "Persistence." Ch. 28 in Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning. Oxford, England: Oxford University Press, 2001.

Rivera, C. "Problems & Puzzles: Puzzle 022-Primes & Persistence." http://www.primepuzzles.net/puzzles/puzz_022.htm.

Schneider, W. "The Persistence of a Number." http://www.wschnei.de/digit-related-numbers/persistence.html.

Sloane, N. J. A. "The Persistence of a Number." J. Recr. Math. 6, 97-98, 1973.

Sloane, N. J. A. Sequences A003001/M4687, A014553, A031346, and A046500 in "The On-Line Encyclopedia of Integer Sequences."

Wells, D. The Penguin Dictionary of Curious and Interesting Numbers. Middlesex, England: Penguin Books, p. 78, 1986.



いまさらながらWikipediaから
Persistence of a number


ArXivにあった!と思ってみてみたら、題名でびっくりw
Eight Hateful Sequences
http://arxiv.org/abs/0805.2128
http://arxiv.org/PS_cache/arxiv/pdf/0805/0805.2128v1.pdf
参考文献を引用:

References
[1] D. L. Applegate, R. E. Bixby, V. Chvatal and W. J. Cook, The Traveling Salesman Problem: A
Computational Study, Princeton Univ. Press, 2007.
[2] D. L. Applegate and N. J. A. Sloane, ´ Eric Angelini’s “1995” puzzle sequence, Preprint, 2008.
[3] J. Beardwood, J. H. Halton and J. M. Hammersley, The shortest path through many points, Proc.
Cambridge Philos. Soc., 55 (1959), 299–327.
[4] F. J. van der Bult, D. C. Gijswijt, J. P. Lindeman, N. J. A. Sloane and A. R. Wilks, A slowgrowing
sequence defined by an unusual recurrence, J. Integer Sequences, 10 (2007), #07.1.2
[arXiv:math.NT/0602498].
[5] J. H. Conway and N. J. A. Sloane, Powertrains and other sequences, Preprint, 2008.
[6] S. R. Finch, Mathematical Constants, Cambridge Univ. Press, 2003.
[7] D. S. Johnson, Comparability, talk given at Workshop on Experimental Analysis of Algorithms:
Interfaces between the Statistical and Computational Sciences, Research Triangle Park, NC, March
6–7, 2008.
[8] J. C. Lagarias, An elementary problem equivalent to the Riemann hypothesis, Amer. Math.
Monthly, 109 (2002), 534–543 [arXiv:math.NT/0008177].
[9] J. C. Lagarias, E. M. Rains and N. J. A. Sloane, The EKG sequence, Experimental Math., 11
(2002), 437–446 [arXiv:math.NT/0204011]
[10] G. Robin, Grandes valeurs de la fonction somme des diviseurs et hypoth`ese de Riemann, J. Math.
Pures Appl., 63 (1984), 187–213.
[11] N. J. A. Sloane, The persistence of a number, J. Recreational Math., 6 (No. 2, 1973), 97–98.
[12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at
www.research.att.com/∼njas/sequences/, 1996–2008.
[13] N. J. A. Sloane, Seven staggering sequences, in Proceedings Seventh Gathering for Gardner, 2008.






GoogleBooksからも発掘
Unsolved problems in number theory 著者: Richard K. Guy
Unsolved Problems in Number Theory (Problem Books in Mathematics / Unsolved Problems in Intuitive Mathematics)



Elementary number theory in nine chapters 著者: James Joseph Tattersall
Elementary Number Theory in Nine ChaptersElementary Number Theory in Nine Chapters

(関連:耐久数続き



昔のCマガに、「耐久数」の話が載っていたことをふと思い出した。
たしか、「自然数の各桁の積をとる」という操作を繰り返して一桁になるまでがんばる。そのがんばった回数を耐久数、といったような気がした。

例:
1234
→1*2*3*4=24
→2*4=8
2回で1桁になったので、1234の耐久数は2。

12345
→1*2*3*4*5=120
→1*2*0=0
12345の耐久数は2

26888999
→2*6*8*8*8*9*9*9=4478976
→4*4*7*8*9*7*6=338688
→3*3*8*6*8*8=27648
→2*7*6*4*8=2688
→2*6*8*8=768
→7*6*8=336
→3*3*6=54
→5*4=20
→2*0=0
26888999の耐久数は9

明らかに、各桁の中に0が出たらその時点で終了なわけで、耐久数はなかなか伸びない。何も考えていないが、気分的には耐久数は有界じゃね?という気もするし、極端にまばらに点在しているような気もする。



たしかCマガでは、枝刈りか何かして、高速に探索するプログラムが書いてあったような気がした。
現状はどこまで計算されているんだろう。
耐久数の英語が分かればいろいろ調べられそうなきもするが、よく分からん。



「耐久数」でぐぐってみた
一応ググってみる:
Google検索 耐久数
約 3,240,000 件 (0.18 秒)かよ。
見てみたがノイズだらけでだめだこりゃ。

フレーズ検索してみる:
Google 検索 "耐久数"
約 3,700 件 (0.13 秒) まだ多いな。一眼レフカメラの耐久数の話が多い。

「整数」か「自然数」がキーワードとして出てくるはずなので
Google 検索 "耐久数" 自然数|整数
7 件 (0.23 秒)
それっぽいところが見つかった。


プログラミングの基礎Ⅱ
C プログラミング(基礎と応用)
だが今は見られないようなので、WebArchiveからサルベージしてみた:
(過去記事 「Web Archiveでそのページの過去を見るブックマークレット」参照)

プログラミングの基礎Ⅱ
C プログラミング(基礎と応用)

練習問題の題材として紹介されているみたい。
限界まで計算しているわけではない模様。



(関連:耐久数続き
一般数体篩法(GNFS)による素因数分解を実行するソフトウェア、GGNFSについて。

総本山(Chris Monico氏による)
GGNFS - A Number Field Sieve implementation

GGNFSの使い方 (只今名称未設定)
GGNFSの使い方 (Studio Kamada)
GGNFSを動かすにはGMPが必要になる。
とくにWindows上で動かすにはCygwinが必要。


Studia KamadaさんのところからGGNFSをググってみた。検索結果


■平成19年度 卒業論文に「素因数分解プログラムGGNFSの性能測定」という卒業論文の要旨がある。


認証や電子署名には公開鍵暗号が広く使われており,特にRSA暗号が主に用いられている.RSA暗号の安全性の根拠は巨大数の因数分解問題の困難さであるので,因数分解の高速化はRSA暗号の安全性の予測において重要な意味を持つ.

素因数分解には試し割り法, モンテカルロ法, 楕円曲線法, 二次篩法など多数のアルゴリズムが存在するが,その中でも一般数体篩法は100 桁以上の数を分解するには現在知られる最速のアルゴリズムである.2005年には 200桁の数(rsa200)が一般数体篩法で分解された.

本研究では,オープンソースの一般数体篩法ソフトウェアGGNFSについて,性能測定を行なう.




これからしばらく、多倍長演算とか素数判定とか素因数分解とかのネタをぼちぼちメモすることにした。

大雑把な予定:
日本語のものを中心に。
記事を埋め次第、ここからリンクを飛ばす。
疲れたり飽きたりしたら止める。
あくまでぼちぼち、テキトー
  • 多倍長演算関係:
    • 解説サイト
    • 多倍長演算ルーチンやライブラリ
  • 素数判定関係:
    • 全体像の解説記事
    • 一般の整数に対する判定法:APR-CL、ECPP、AKSなどの解説、プログラム。
    • 特殊な整数に対する判定法:PRP、glucasなどの解説、プログラム。
    • これらの判定方法が実装されているソフトウェアを見つけたらそれもメモ。
  • 素因数分解関係:
    • 全体像の解説記事
    • ECM等の素因子の大きさに依存するもの
    • MPQS、NFS等の対象となる数の大きさに依存するもの


まぁこんな感じで。
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。