うえぽんSW局

古いタイプの日記ブログです。気まぐれに更新してます。

タグ:数学

 今回も旧ブログに書いていたネタのサルベージです。
 頭の体操などにありがちな天秤問題です。

【問題1(12個問題)】
 12個のオモリがある。そのうち1個だけ重さが違うそうだ。
 さて、天秤を3回だけ使って誤りの1個を特定するにはどうすれば良いだろうか?
 さらに、誤ったオモリは正しいものより重いのか軽いのかも当てよ


【問題2(13個問題)】
 今度は13個のオモリがある。これにも1個だけ重さが違うものが混じっている。
 今回も天秤を3回だけ使って誤りの1個を特定するにはどうすれば良いだろうか?
 ただし、今回は誤ったオモリが重いか軽いか当てなくとも良い。


 12個の場合は誤りの1個が重い軽いまで完全に求められますが、13個の場合は完全には無理なのでそこまでは求めません。
 オモリはコインとか金貨とか玉とかと色々のバリエーションがありますが、どれでも同じです。

 以下は、自分が見つけたやり方です。

続きを読む
このエントリーをはてなブックマークに追加

 旧ブログに以前ちょこっと書いていたネタのサルベージです。

 『アシモフの雑学コレクション』(星新一編訳)にこんな雑学があります。

「37」という数は、それと1以外に約数を持たない。つまり素数。
しかし、次の数を割り切れる。
111、222、333、444、555、666、777、888、999。


 一瞬へーと思う雑学だが、実は大したことは言ってない。
 111を割り切れるということは、倍数である222、333、……も割り切れて当然だ。
 37という数字も素数である以外は特に意味のあるものではない。
 大したことでなくても書き方次第でへーと思わせるものなんだなと思ったりする。

 さて、この雑学はもう少し手を加えて改良できそうなのでやってみた。

「4649」という数は「ヨロシク」の語呂合わせができるだけではない。
1以外の約数を持たない数、つまり素数である。
そして次の数を割り切ることができる。
1111111、2222222、3333333、4444444、5555555、6666666、7777777、8888888、9999999。


 4649でヨロシクの語呂合わせをできるのは日本語ぐらいなので、日本限定の雑学かもしれません。
 ツイッターあたりを「4649 1111111」で検索してみると同様の雑学を披露している人が多いようです。

アシモフの雑学コレクション (新潮文庫)
アイザック アシモフ
新潮社
1986-07-29

このエントリーをはてなブックマークに追加

 大変珍しい連続素数日が訪れたので、さぼっていたブログを久々に更新です。

 日付をyyyymmdd形式の8桁の値とみなしたとき、その数が素数となるのを素数日と呼んでいますが、今日と明日は20201231と20210101となりそれぞれ素数となります。
 連続で素数日となるのは大変珍しいです。なにせddの部分は奇数と偶数(2の倍数)が続くことが多いからです。連続するためには31日と翌月1日のパターンとなります(あと、これは忘れやすいですが、うるう年で2月が29日あるときも連続素数日になる可能性があります)。
 さらにそれが年末年始の年またぎとなるともっと珍しくなります。

 そんな珍しい連続素数日ですが、何かあるわけでもなく「だから何?」と言われればそれまでです…。

 ちなみに次回の連続素数日は2028年の2月。
 今回同様の年末年始の連続素数日となると2029年の大みそかとなります(これは意外と早くに来る?)。

 連続する素数日については数年前のエントリーに書いているのでそちらを参照。
 20世紀と21世紀の素数日を再掲すると以下の通り。

 20世紀
 19130731, 19130801
 19210531, 19210601
 19240229, 19240301
 19250131, 19250201
 19301231, 19310101
 19500331, 19500401
 19721231, 19730101
 19781231, 19790101
 19790131, 19790201
 19830331, 19830401
 19871231, 19880101
 19900831, 19900901
 19971031, 19971101

 21世紀
 20020531, 20020601
 20170831, 20170901
 20180731, 20180801
 20201231, 20210101
 20280229, 20280301
 20291231, 20300101
 20361031, 20361101
 20640331, 20640401
 20680831, 20680901
 20750131, 20750201
 20800229, 20800301
 20800531, 20800601
 20811031, 20811101
 20930731, 20930801

 では、よいお年を。
このエントリーをはてなブックマークに追加

 ふと小改良を思いついたのでやってみた。
 断っておくと改良でなく改良なのであしからず。

 本題の前にまず通常のやり方を簡単に説明。
 まず1×1の正方形内にランダムに点を打つ。点の総数はN。
 下の図のような円の内側に入った点の数をカウントする。そのカウントをPとする。
 monte_pi_01
 正方形の面積は1、1/4円の面積はπ/4。
 点の数NとPの比率も面積の比率に近似するはずなので、そのことからπの近似値が以下のように求まる。
 π≒4P/N

 以上が通常のやり方だ。

 そして今回思いついた小改良は上図の円の部分を、下図のような扇形を二つ重ねた図形に置き換えるというものだ。
 monte_pi_img02
 この図形は小・中学校の算数や数学でよく見かけるやつで面積はπ/2-1となる。
 そしてπの近似計算は、
 π≒2(P/N+1)
 ということになる。

 さて、この小改良の結果はというと、
 3回中2回は通常のやり方よりも若干高い精度になった。
 しかし、残りの1回は通常のやり方の方が良い結果となってしまった。

 点の総数を増やせばもっと傾向が変わるのではないかと1万点、1億点と増やしていったが、不思議とその傾向は変わらなかった。
 3回中2回は良い結果、残り1回は悪い結果という具合だ。
 どうやら乱数を使ったアルゴリズムのゆえか、運の良い場合と、運の悪いランダムで訪れるらしい。

 こんなものを改良と言うのはおこがましいかもしれない。改良と言ったところだろう。

 ついでに下の図のようにしたらどうなるのかも検証してみたが、これは通常のやり方に対して完敗だった。
 monte_pi_img03

 ちなみに、Pythonを使って検証したが、10億点以上ともなるとかなりの計算時間となる(うちのしょぼPCでは1時間近くかかった)。
 10億点やっても円周率の精度は3.141までは一致するが、それ以降の桁はプログラム実行のたびに一致したりしなかったりと心許ない感じ。
 モンテカルロ法で高い精度の円周率を求めるのはあまりお勧めしない。その計算時間で他のやり方を試した方が良い。
このエントリーをはてなブックマークに追加

 今日2002年2月2日は8桁の数字で表すと20200202で上から見ても下から見ても同じになる回文になっていたりする。

 それならばと他にも同様の回文になる日付はないかと調べてみた。

 まず未来方向へは、
 20211202
 20300302
 20400402
 20500502
 20600602
 20700702
 20800802
 20900902
 21011012
 21100112
 21111112
 :
 :
 となっている。
 次回は来年の2021年12月2日で、その次以降は約10年ごとに出現する。

 今度は過去の方向へ調べてみると、
 20111102
 20100102
 20011002
 13800831
 13700731
 13500531
 :
 :
 となっている。
 前回は2011年11月2日は良いとして、2001年以前は1380年まで遡らないと存在しない。
 なんと日付の回文は21世紀になって7世紀ぶりに復活したことになる!
 地味にすごい。


■メッセージへの返事
 ついでになりますが、ブログ横の投稿フォーム(PC版の表示だと存在する)から送られて来たメッセージへの返事です。
 ブログ横にあるホームページのリンクが間違っていたのを修正しました。
 ご指摘ありがとうございます。
このエントリーをはてなブックマークに追加

 今年もいつのまにか大晦日になっていました。
 ブログの更新を怠っていたので、おっとり刀で数学の雑学を披露しようかと思います。
 この雑学はネット検索してもあまり見受けられないので、あまり知られてないのかもしれません。


         343 = 7 * 49
        33433 = 67 * 499
       3334333 = 667 * 4999
      333343333 = 6667 * 49999
     33333433333 = 66667 * 499999
    3333334333333 = 666667 * 4999999
   333333343333333 = 6666667 * 49999999
  33333333433333333 = 66666667 * 499999999
 3333333334333333333 = 666666667 * 4999999999
333333333343333333333 = 6666666667 * 49999999999
          :
          :
          :

         323 = 17 * 19
        33233 = 167 * 199
       3332333 = 1667 * 1999
      333323333 = 16667 * 19999
     33333233333 = 166667 * 199999
    3333332333333 = 1666667 * 1999999
   333333323333333 = 16666667 * 19999999
  33333333233333333 = 166666667 * 199999999
 3333333332333333333 = 1666666667 * 1999999999
333333333323333333333 = 16666666667 * 19999999999
          :
          :
          :

         101 = 1 * 101
        11011 = 11 * 1001
       1110111 = 111 * 10001
      111101111 = 1111 * 100001
     11111011111 = 11111 * 1000001
    1111110111111 = 111111 * 10000001
   111111101111111 = 1111111 * 100000001
  11111111011111111 = 11111111 * 1000000001
 1111111110111111111 = 111111111 * 10000000001
111111111101111111111 = 1111111111 * 100000000001
          :
          :
          :

         121 = 11 * 11
        11211 = 111 * 101
       1112111 = 1111 * 1001
      111121111 = 11111 * 10001
     11111211111 = 111111 * 100001
    1111112111111 = 1111111 * 1000001
   111111121111111 = 11111111 * 10000001
  11111111211111111 = 111111111 * 100000001
 1111111112111111111 = 1111111111 * 1000000001
111111111121111111111 = 11111111111 * 10000000001
          :
          :
          :

 出典及び参考にしたのは以下のページです。
 Puzzle 197. Always composite numbers?

 こうなることの数学的証明は私にはちょっと無理です……。

 少し応用するとこんな雑学になります。

 666667は素数
 4999999も素数
 2つをかけると回文数3333334333333になる

 それでは良いお年を。
このエントリーをはてなブックマークに追加

 今日の日付20170831は素数日です。
 そして明日の日付20170901も素数日です。
 このように2日連続で素数日になるのは珍しく、前回は20020531と20020601だったので15年ぶりとなります。
 ちなみに、次回はおよそ1年後の20180731と20180801なります。2日連続する素数日が1年以内に2回もあるというのはそれはまた珍しいかもしれません。

 (このエントリーは1年前の今日に予約投稿したものです。詳しくはちょうど一年前の今日のエントリーをご覧ください)
このエントリーをはてなブックマークに追加

 ここ一ヶ月ブログを更新していませんでしたが実はパソコンが壊れてました。
 結局新しいパソコンを買うことになりましたが、さて、新マシンになったらまずすることといえば処理に時間の掛かりそうな計算プログラムの実行です。以前よりも速くなったことを確認します。
 そんなわけで素数を探すプログラムを組んでみたわけですが、以下のような3249桁の回文素数を発見しました(分かりやすく57桁ごとに改行してます)。

111111111111111111111111111111111111111111111111111111111
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000303000000000000000000000000001
100000000000000000000000000030000000000000000000000000001
100000000000000000000000000303000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
100000000000000000000000000000000000000000000000000000001
111111111111111111111111111111111111111111111111111111111


 表示ズレしている環境もあるかもしれないので画像にもしてみました(ついでに色も付けてます)。
 ただの回文素数ではなく、57x57の正方形にすると左右や上下にも対称という面白い形になっていることが分かります(残念ながらすべての行と列も素数とまではなっていません)。

prime57x57


 ただし、この素数の判定に用いたのはpythonの拡張モジュールgmpy2にあるis_prime関数(中身はGMPのmpz_probab_prime_p関数)のため、確率的素数ということになります。
 とはいえ乱数で8192回のテストにパスしているのでほぼ間違いなく素数だと思いますが……。
このエントリーをはてなブックマークに追加

 年末年始のことになりますが、次のような記事を見つけたので、素数遊びをしてみました。

 年末年始は難解な素数と遊ぼう 回文素数、レピュニット素数、数素 | JBpress(日本ビジネスプレス)
 (現在、この記事の2ページ目以降は会員登録していないとみられないようです)

 上のページによると、ホネカーという人によって次のような回文素数のピラミッドが発見されているとのこと。

2
30203
133020331
1713302033171
12171330203317121
151217133020331712151
1815121713302033171215181
16181512171330203317121518161
331618151217133020331712151816133
9333161815121713302033171215181613339
11933316181512171330203317121518161333911


 これに興味をそそられたので、これより大きなピラミッドがないかと自分も探してみることにした。
 プログラムを組んで探すだけなので手軽なものだと思っていたが、しかし、最初に見つけた回文素数ピラミッドは次のようなものだった。

2
929
39293
3392933
733929337


 ホネカーのものよりも小さなピラミッドになってしまった。
 自分が組んだプログラムにミスがあったのだろうか? と一瞬思ったものの、ホネカーのピラミッドを見返してみると、ホネカーのものは1段ごとに左右2桁ずつ(合計4桁ずつ)増えていることに気付いた。
 自分が探していたのは左右1桁ずつだった。
 左右1桁ずつだとこの程度の高さのピラミッドにしかならないらしい。

 気を取り直して左右2桁ずつ増えるようにして探索。
 すると次のような回文素数のピラミッドを発見した。これはホネカーのものよりずっと大きい。

5
97579
389757983
3138975798313
15313897579831351
741531389757983135147
9074153138975798313514709
73907415313897579831351470937
907390741531389757983135147093709
3690739074153138975798313514709370963
38369073907415313897579831351470937096383
393836907390741531389757983135147093709638393
7039383690739074153138975798313514709370963839307
71703938369073907415313897579831351470937096383930717
347170393836907390741531389757983135147093709638393071743
9534717039383690739074153138975798313514709370963839307174359
93953471703938369073907415313897579831351470937096383930717435939
799395347170393836907390741531389757983135147093709638393071743593997
3679939534717039383690739074153138975798313514709370963839307174359399763
14367993953471703938369073907415313897579831351470937096383930717435939976341
761436799395347170393836907390741531389757983135147093709638393071743593997634167
1776143679939534717039383690739074153138975798313514709370963839307174359399763416771
70177614367993953471703938369073907415313897579831351470937096383930717435939976341677107
787017761436799395347170393836907390741531389757983135147093709638393071743593997634167710787
3878701776143679939534717039383690739074153138975798313514709370963839307174359399763416771078783
94387870177614367993953471703938369073907415313897579831351470937096383930717435939976341677107878349
149438787017761436799395347170393836907390741531389757983135147093709638393071743593997634167710787834941
3314943878701776143679939534717039383690739074153138975798313514709370963839307174359399763416771078783494133
99331494387870177614367993953471703938369073907415313897579831351470937096383930717435939976341677107878349413399


 当ブログの横幅の関係でうまく表示できていないかもしれないので、画像にしたものも用意してみました。クリックすると見られます。
 回文素数のピラミッド

 同じものを発見した人がいないかとGoogle検索してみたところ、次の2件だけ発見。

 ・number theory - Origins of the conjecture on the existence of infinitely many palindromic primes - Mathematics Stack Exchange
 ・burde_27_analytic_nt_course.pdf(PDF注意)

 このどちらもが自分が発見したものより少し低いピラミッドとなっている。最後の6段ほどがない。
 これは最後まで探索できなかったのか、それとも自分の方が間違っている可能性がある。
 しかし自分のはGNU Multi-Precision Library(GMP)の関数mpz_probab_prime_p()で65536回ものミラーラビン素数判定をパスしているから、間違いということはないと思うのであるが……。
このエントリーをはてなブックマークに追加

 2016年も最後となってしまったので、以前書いた「素数探しの旅」がその後がどうなったか書いておこうと思います。

 まず探していた素数というのは以下のように1234567890123…と続く数列で素数となるものです。
 1
 12
 123
 1234
 12345
 123456
 1234567
 12345678
 123456789
 1234567890
 12345678901
 123456789012
 1234567890123
 :
 :

 以前の記事では以下の桁数において素数(もしくは確率的素数)となることを発見しました。
 171桁
 277桁
 367桁
 561桁
 567桁
 18881桁

 ではこれ以上の桁数で素数は存在するのだろうか?
 というわけで、あれからチマチマと素数を探し続けていました。
 そうして半年かかって21万1761桁までテストしましたが、発見できませんでした
 (もしかしたら自分がミスして見逃している可能性があるかもしれませんので、他の方の検証も欲しい所です)

 長らくチマチマと探していましたが、2016年が終わるのを目途として素数の探索はをこれにて打ち切りにしたいと思います。この挑戦はかなり無茶だったかもしれません。


 以下はもしかしたら素数探索の手助けになるかもしれないメモです。

●一般項
 次の式で求められる(^は乗数、[]は小数点以下切り捨てを意味する)。
 [10^k*1234567890/9999999999]
 for文を使うより一般項で普通に計算した方が速い。

●末尾が1と7だけ探索すれば良い
 2と5の倍数を除外すると末尾が1、3、7、9の4つを探せば良いことが分かるが、3と9も除外することができる。なぜなら各桁の数を合計すると必ず3の倍数になるため(3の倍数を求める方法)。

●最大公約数を求めることでさらに除外
 素因数分解や素数判定は時間がかかるが、最大公約数の計算は比較的高速に求めることができる。
 例えば下の2つの数の最大公約数を求めるとその数は7となり、両方とも素数でないことが分かる。
 123456789012345678901234567890(30桁)
 12345678901234567(17桁)
 この例では桁数が30*k+17の形のときは7の倍数になる(つまり素数ではない)ことを意味するので、その形になるものを素数判定の対象から除外することができる。
 他にも、110*k+87桁、110*k+21桁などが素数の判定から除外できる。
 こういうのをたくさん探しておくことで、素数判定の対象を減らせる。

●素数判定の前に軽く素因数分解した方が速いことも
 桁数が大きくなるとミラー・ラビン素数判定法でもかなりの時間を要する。
 そこで素数判定の前に“軽く”素因数分解をやるやり方も有効になってくる。
 自分はポラード・ロー素因数分解法を使った。


 というわけで2016年はこれでお終いです。
 良いお年を。
このエントリーをはてなブックマークに追加

↑このページのトップヘ