Mad-P音ゲー日記 2001年10月中旬

←前 2001年10月上旬 ↑index 2001年10月下旬次→

★ 2001/10/11 犬トンズラ

■ 昨日夜7時ごろ、犬が家出。眠れぬ夜。

★ 2001/10/12 DM5th

■ 犬帰宅せず。本格的に迷子になったかなあ。

■ 昨日はSATYで5DM。
　DMN: Popularity/B(B)
　DM: Stop This Train(S) → Bobby Sue(×)
　DM: Earth(A) → Bobby Sue(C) → 正論(×)
　DM: 天体観測/E(A) → Plastic(S) → Brazilian(A)
　DM: Sunflower(S)[Full] → Boy Friend/E(S) → ありがとね(S) → Fireball(A)[55]
インターネットランキングは登録するだけで全員に参加賞としてCDプレゼントってホントかなあ。 Bobby Sueで落ちたり正論で落ちたり、 BrazilianでAが取れたり、 Sunflowerでフルコンボだったりした。

★ 2001/10/15 DM5th/お祭り/CD-R < FDD/おもしろ問題

■ 犬はまだ帰ってこない……。ごはんはちゃんと食べているんだろうか。老体なので心配。

■ 金曜日は南行徳で5DM。
　DMN: Yully/B(S)
　DM: Bad Name/E(S) → Wake Me Up(S) → Balalaika(S)[17] → Fireball(A)[48]
　DMB: Triathlon(B)
　DM: Feel The Earth(S) → Midnight Sun(B) → 正論(×)
　DMB: Some Hard Reactions(S)[38]
Adv. Triathlon完走は初かな? 正論は足がついて来ない。頭では譜面がわかってるつもりなんだけども。

■ 週末は地元でお祭りがあって、家の前の道路は路線バス以外通行止。バスが来るたびに御神輿がよけて待っている。とはいえ御神輿というくらいで神様の乗物、のりとをあげている間はバスの方が待つ。

■ 実家の父PCがこわれたと言うので出張修理。
　「WindowsMeだったはずが95に先祖帰りしちゃったんだよ」
そんなバカな。って、単にメインのHDDがこわれて、前のマシンから持ってきたスレーブHDDからブートしちゃっただけのこと。
　新しいHDDを買ってきてリカバリCDからOSを入れておしまい。こんなご時世なのですぐさまWindows Updateしようと思ったら、モデムが遅いので待ち切れず中止。 344Kバイトを10分かかっても落とせないってどゆこと!? 以前はNetscape4.xを使わせていたんだが、インストールする時間がないのでIE5.5+Outlook Expressという最凶な設定のまま放置。次に来たときにNetscape6を入れよう。

■ 　そういえば、3.5インチフロッピー10枚よりも、 CD-Rメディア10枚の方が安かった。いつのまにか逆転していたらしい。
　帰宅後、ヨメPCから必要最低限のバックアップを取った。

■ Kamadaさんの問題、 2の1000乗ってのがつらいです。これが2の500乗だったら40分くらいで解が得られたのですが。現在2の800乗付近を挑戦中で、あと5時間くらいはかかりそうです。 PerlのMath::BigIntを使ってるので、pure perlで計算してるのも遅い原因ですが。
　とはいえ使ってるアルゴリズムはnに関する十分条件でしかない可能性があるので、「最小のn」が求まるとは限らないところも痛いです。これで求まるものが最小であるとか証明できればいいんだけど、難しそう。
　ちなみに、500乗だとこんなの。
3**28132992892644314921361757608797896973122607455970075929045041004457053699945409484088722092176406035977149285616034072697168552766194646808135220491 + 5 ≡ 0 (mod 2**500)
これで合っているのかとか、これが本当に最小なのかとかの検査はしてません。
　念のため追記。「40分」ってのはプログラムの実行時間であって、プログラミングや考える時間は含みません。どっちが長いかは内緒。現在頭から3時間50分くらいかかって845まで来てます。 1コ進むのに約1分なので、後ろへ行くほど遅くなる分も考慮すると、あと3時間半くらいはかかりそうです (こう書くと、3**n + 5 ≡ 0 (mod 2**k)においてk-1の結果を使って kの結果を求める方針なのがバレてしまいます(笑))。

★ 2001/10/16 DM5th/おもしろ問題の解

■ 昨日はSATYで2DM。
　DM: Power Of Love/E(S) → Mister Magic(A) → 正論(×)
　DM: E-Mail(S) → Blind(S) → Sunflower(S) → Fireball(A)[34]
正論はまたダメだったよ。Fireballは少しずつ上達してるか?

■ あー、1024bit整数固定長演算ルーチンをCで書きました。そしたらなんと、3秒で答が出ましたです。301桁の数になりました。

5 + 3 ** 2_65771_19241_69142_79143_32447_89222
          _49114_36149_43127_38595_85138_62637
          _21264_02928_96087_09373_37206_17238
          _48120_88454_22920_41439_91739_58261
          _34678_98227_32504_48372_63429_38016
          _43617_97263_85541_36462_47061_48751
          _37126_26641_94386_37694_37556_35666
          _15723_79770_94718_81689_21921_68332
          _65896_38786_41770_46676_57302_73339
          _96176_02351_38224_23645_69970_43467
  == 0 (modulo 2**1000)

これが最小だっていう証明らしきものも思いつきました~~が、ここには書ききれません~~。なんか、バシッとわかるような方法はあるんでしょうか? 2**1000を法とした3の逆数ってわけでもないしなあ。
　などと書いてる間にPerl版も遅れて解に到達。所要時間約7時間20分。手元の(Perl5.00503付属の)Math::BigIntはXSを使ってなくて、いちいち内部形式(100000を底とした配列)と外部形式(文字列)との変換をしたり、 grepの結果を捨てたりしていて効率が悪いようだ。と思って調べると、Perl5.7.2のMath::BigIntはずっと効率が良さそうだ。でも今回みたいに「なんだ、1024bit整数で固定長演算すりゃいいんじゃん」って早く気づくことの方がより重要。

■ うむー、このUBASICのプログラム、私のアルゴリズムと同じです。こんなに簡潔に書けるのカー。
　私のプログラムは(論理的には)こうなってます。

　 n = 1
　 for k (3 .. 1000)
　　 unless (3**n mod 2**k) == (-5 mod 2**k)
　　    n += 2**(k-3)

実際には3**n mod 2**1024を変数に入れといて、 mod 2**kのときには下のkビットを使います (-5 mod 2**kはビットパターンが「111……11011」)。

■ この問題は結果として、modulo 2**kな環境で3を底とした-5の対数(の整数解)を求めています。だからってまくろーりん展開とかしてもn→∞ ⇒ 1/x**n→0にならんのでダメ。指数とか対数の恒等式(log ab = log a + log bみたいなやつ)をいじっているとひらめきませんかね。
　解が下の桁から順に求まっていくのも面白いとこです。普通は収束するのって、小数点以下を上から下へ向ってのびていくから。逆順にして小数読みすると意味のある数にならないかとか考え妄想しました。

★ 2001/10/18 DM5th: 正論完走

■ 昨日はSATYで2DM。
　DM: Depend CD/E(A)[39] → Tiger, Too(B) → Herring Roe(B)
　DM: Wake Me Up(S) → Mister Magic(A)[24] → 正論(B)
Ext. Depend (CD)もAdv. Tiger, Tooもあとちょっとのところでねらったランクに届かず。たまにはAdv. Herring Roeもやってみよう。ありゃ、結構いけるんやん。 Bランクながらゲージはあまり減らずに楽しく叩けた。 Mister Magicもぎりぎりかい。正論の問題の部分、キックを8分で全部踏むという暴挙に出て完走。

■ 今日は体調悪く1回休み。動物愛護センターにうちの犬らしいのがいるというので、ヨメは見に出かけた。留守番する間に犬さがし用ポスターを作成。
　残念ながら違う犬だったとのこと。

★ 2001/10/19 おもしろ問題の解法の証明

■ Kamadaさんとこに先日の問題の解法の証明が。うげー、なんか難しそうです。私はこんな風に考えました。

■ お題: 3**n + 5 ≡ 0 (modulo 2**k)
　まず疑うべきは、「3**n mod 8は5や7には決してならない」みたいな解がない問ではないかということ。そこで、k=3〜16くらいまでしらみつぶしに調べるプログラムを書いた。これくらいなら待ってる間に答が得られる。

3**n + 5 ≡ 0 (modulo 2**k)なる最小のn

  k  3  4  5  6  7  8  9 10  11  12   13   14   15    16    17
  n  1  3  3 11 11 11 11 11 267 267 1291 3339 7435 15627 15627

解なしってことはないようだ。同じ数字がくり返し出たりしている。演算はすべてmodulo 2**kで行っているので、答もk-1ビット以内になるはず。そこで答を2進表示してみる。

 10進               2進
    1 ==              1
    3 ==             11
   11 ==           1011
  267 ==      100001011
 1291 ==    10100001011
 3339 ==   110100001011
 7435 ==  1110100001011
15627 == 11110100001011

規則性がある。同じ数字をくり返した後は、くり返した分だけ0がつくらしい。 1がつくときのビット位置はk-3みたいだ。この規則で探索するプログラムを走らせつつ、証明を考える。

■ 予想A: 3**n ≡ -5 (modulo 2**(k-1))
　　ならば、以下A1または(not A1 and A2)のどちらかが成立する。
　　A1. 3**n ≡ -5 (modulo 2**k)
　　A2. 3**(n+2**(k-3)) ≡ -5 (modulo 2**k)
A2をもう少し詳しく見ると、not A1であることから
　3**n ≡ -5 + 2**(k-1) (modulo 2**k)
であることに注意して、

3**(n+2**(k-3)) ≡ 3**n * 3**2**(k-3)
                ≡ (-5 + 2**(k-1)) * 3**2**(k-3) (modulo 2**k)

3**2**(k-3)はどうなのか。どのみち3**nを速く計算する過程で3**2**m mod 2**kの表は作ってあるのだ。

        
      m=0    1    2    3    4    5    6    7    8    9
k=3     3    1    1
  4     3    9    1    1
  5     3    9   17    1    1
  6     3    9   17   33    1    1
  7     3    9   81   33   65    1    1
  8     3    9   81  161   65  129    1    1
  9     3    9   81  417  321  129  257    1    1
 10     3    9   81  417  833  641  257  513    1    1

ありゃ、3**2**(k-2) ≡ 1 (modulo 2**k)なんですかい? 3**2**(k-3)はその1コ左側。1 + 2**(k-1)かな?
　予想B: 3**2**(k-3) ≡ 1 + 2**(k-1) (modulo 2**k)
予想Bの証明はKamadaさんの証明がすばらしいので略。念のためkの下限を確認しておくとk=3では成立せずk=4で成立。\

■ さて、予想A2の続き。

3**(n+2**(k-3))
  ≡ (-5 + 2**(k-1)) * 3**2**(k-3) (modulo 2**k)
  ≡ (-5 + 2**(k-1)) * (1 + 2**(k-1))
  ≡ -5 - 4 * 2**(k-1) + (2**(k-1))**2
  ≡ -5 - 2 * 2**k     +  2**k * 2**(k-2)
  ≡ -5 (modulo 2**k)

えーと、kの条件はk≧4ですな。以上で例のプログラムで求めたnが「3**n+5≡0 (modulo 2**k)」を満たすことがわかった。

■ 次にこうやって求めたnが最小であることを証明する。 nとは別のmがあって3**m+5≡0(modulo 2**k)とする。すると
　　3**n ≡ -5 (modulo 2**k)
　　3**m ≡ -5 (modulo 2**k)
各辺はどれも0ではないので辺々割って、
　　3**(m-n) ≡ 1 (modulo 2**k)
ところがmodulo 2**kで考えて3**j≡1となるjは2**(k-2)の倍数が4つあるのみ(予想C)。つまりm ≡ n (modulo 2**(k-2))。ここでnの決め方により0＜n＜2**(k-2)であることに注意すると、 mはnより小さくないことがわかる。

■ 最後に予想Cが残ったところで力つきた。
　予想C: k≧3かつ1≦j＜2**(k-2)ならばnot 3**j ≡ 1 (modulo 2**k)
j,kに関する帰納法でよさそうなんだけど、内側のループでj,kどっちを固定すべき?

←前 2001年10月上旬 ↑index 2001年10月下旬次→