ユークリッドの互除法

世界最古に発見されたアルゴリズムのひとつとして知られるユークリッドの互除法は, 歴史上の価値のみならず, 公約数という素因数が絡む計算を素因数分解せずに効率的に求めることができるという点で非常に有用な手法となっています.

ユークリッドの互除法とは, 2つの0ではない整数a, b に対して, 次の手続を繰り返すことで ab の最大公約数を求めることができます.

  1. b=0 ならば a が求めるべき最大公約数である. アルゴリズムはここで終了する.
  2. c≡a (mod b) を計算し, ab を代入, bc を代入する.
  3. 最初に戻る.

ラメの定理により, アルゴリズムの繰り返し回数は a, b のうち小さい方の 10 進桁数を d とすれば, 高々 5d 回となることが知られており, 5d 回程度の繰り返しが発生する例はフィボナッチ数列(最初の2項を1としたもの)の隣接2項を対象とした場合が知られています.

もしも, これを素因数分解で解決しようとすると, a, b のうち小さい方の正の平方根の数だけ「試しに割り算して割り切れるかを確かめる」作業が必要となります。

つまり, abのもとで割算の回数を比較すると, ユークリッドの互除法ならば 2.2log(b), 素因数分解するなら √b と見積もることができます. b が大きい場合, どちらの方が効率がいいのかは明らかです.

この方法を拡張すると不定方程式 ax+by=gcd(a,b) の整数解を導出することができます. これが拡張されたユークリッドの互除法です. 拡張されたユークリッドの互除法の手順は次のとおりです.

  1. r0=a, s0=1, t0=0, r1=b, s1=0, t0=1, i=1 とする.
  2. ri+1=ri-1-qiri を 0≤ri+1≤abs(ri), qi は整数となるように定める.
  3. si+1=si-1-qisi, ti+1=ti-1-qiti とする.
  4. ri+1=0 の場合は x=si, y=ti であるので計算を終了する. ri+1≠0 の場合は次の項目に進む.
  5. i に 1 を加えて 2. の項目へ戻る.

ユークリッドの互除法の使用例

モジュラ逆数について

個人的メモ

m における整数 a のモジュラ逆数 a-1 (mod m) とは, aa-1≡1 (mod m) を満たす a-1x (mod m) なる整数 x の合同類である.

m における整数 a のモジュラ逆数が存在するための必要十分条件は gcd(m, a)=1 である.

a-1 (mod m) を求める最も汎用的な方法は拡張されたユークリッドの互除法を用いることである. つまり, a, m が所与であるもとでの ax-qm=gcd(a,m)=1 を満たす xa-1 (mod m) である.

他にも, オイラーのトーシェント関数を用いて a-1aφ(m)-1 (mod m) としたり, カーマイケル関数を用いて a-1aλ(m)-1 (mod m) と求める方法があるが, これは m を因数分解する必要があるので効率的な導出方法ではない. これらの特殊形として, m が素数 p であった場合は, a-1ap-2 (mod p) とすることができる.

具体例

合同式に関する諸性質

個人的なメモ

  • フェルマーの小定理とは次の関係を言う: 素数 pp とは互いに素な整数 a について ap-1≡1 (mod p) が成り立つ.
  • 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 nn とは互いに素な整数 a について aφ(n)≡1 (mod n) が成り立つ.
    • φ(n) はオイラーのトーシェント関数であり、これは n 以下の n とは互いに素な正の整数の数となる。
    • nk=1mpkbk と素因数分解できたならば, φ(n)=nΠk=1m(1-1/pk)
  • カーマイケルの定理とは次の関係を言う: φ(n) は am≡1(mod n) を満たす最小の m であるとは限らない.
    最小の m はカーマイケル関数λ(n)で与えられる.

    • カーマイケル関数は次のように再帰的に定義される.
      • λ(2e)=1 (e=1), 2 (e=2), 2e-2 (e≧3)
      • 奇素数 p について λ(pe)=pe-1(p-1)
      • nk=1mpkbk と素因数分解できたならば λ(n)=lcm(λ(p1b1),...,λ(pmbm)). ただし, lcm は引数たちの最小公倍数(least common multiple)を表す。

    n≡1 (mod λ(n)) を満たすような n をカーマイケル数という.

以上によれば, 2n≡1 (mod 15) を満たす n は, フェルマーの小定理では導出できない (n=3×5)が,
オイラーの定理によれば n=8 のときに成立することが分かり, カーマイケルの定理によれば, 最小の整数 n は 4 である.

統計検定準1級に合格しました

2018年6月に実施された統計検定の準1級に合格しました。

2018年6月実施分統計検定試験結果通知書
2018年6月実施分統計検定試験結果通知書

統計検定準1級合格証
統計検定合格証準1級

創設時の2011年のときは1級から4級までの4段階だったところ, 2015年から準1級が新設され, その初回に受験はしていたのですが当時は力が及ばなかっただけに感動も一入です.

準1級は5者択一マーク式(今回は24問)と記述試験(今回は数値のみの回答2問5か所, 小論述問題2問5項目, 論述試験1問)からなっているところ,
数値回答は致命的間違いがあって半分落とし、小論述問題は1問が空白、論述試験も 2 割 (さすがに空白はまずいと思いひねり出したものが1つ当たった)が
マーク式は 8 割方正解できたので、滑り込みで合格ラインに乗っかったというところでした。

統計検定は正確なボーダーラインと配点を公表していないので, 受験直後は完答できた人以外は合格発表までやきもきさせられるのですよね... 他の試験 (例えば, 情報処理技術者試験や放射線取扱主任者試験 (第1種及び第2種) は 6 割という情報を公表しているので, 統計検定もおそらくそれに倣っている (大学でも「可」の評価が出る) とは思いますが.

次は数学検定1級の再チャレンジです. 試験日は2018年7月22日(もうすぐ!)です.

将棋棋士の藤井聡太氏が七段昇段最年少記録を更新する

5人目の中学生将棋棋士として有名となった藤井聡太氏が5月18日付で七段昇段を決めた. これにより、七段昇段の最年少記録が更新された(15歳9か月)。なお、これまでの記録は60年以上前に達成された加藤一二三氏の17歳3か月である。

ただ、60年前と比べて昇段する機会が増えたという側面もあることに留意したい。

八段以上への昇段はかなり難しい。順位戦A級への昇級、竜王のタイトルをとる、他のタイトルを複数とる(八段以上はタイトル戦以外の棋戦に優勝するだけでは昇段できない)、
勝ち星を一定数積み上げるという、わかりやすい実績をあげる方法しかないからである。

なお, 歴代の最年少昇段記録は追記のとおりで合っているはず. (誤りがあればコメントで指摘願います)

将棋の最年少昇段記録
段位 記録保持者 昇段日 昇段時年齢 昇段理由
四段 藤井聡太 2016年10月1日 14歳2か月 第59回(2016年度前期)三段リーグ1位
五段 加藤一二三 1955年4月1日 15歳3か月 順位戦C級1組へ昇級 (第9期(1955年度)順位戦C級2組西組1位)
六段 藤井聡太 2018年2月17日 15歳6か月 五段昇段後全棋士参加棋戦優勝 (第11回朝日杯将棋オープン戦優勝)
七段 藤井聡太 2018年5月18日 15歳9か月 竜王戦ランキング戦2期連続昇級(6組→5組→4組)
八段 加藤一二三 1958年4月1日 18歳3か月 順位戦A級へ昇級 (第12期(1958年度)順位戦B級1組2位)
九段 渡辺明 2005年11月30日 21歳7か月 竜王位2期

第37回うみねこマラソン 5km 完走

今年も何とか走り切ることができました。

第37回八戸うみねこマラソン 5kmの部 完走証 (45分59秒)
第37回八戸うみねこマラソン 5kmの部 完走証

前回も参加自体はしていたのですが、コンディションを整えきれず痛みに耐えかねて一部区間を歩いてしまったので,
今回はとにかく遅くてもいいから走りとおすことだけを考えて競技に臨みました.
結果, それを実行できたことには満足しています.

ただ, 走行速度は一番よかったときと比べると 2/3 程度しか出ていないので, まずはそこまでの速度を取り戻したいところです.

おまけ

ENDYMION BDP 初クリア

12 回目の挑戦にして, ようやく ENDYMION BASIC DOUBLE をクリア.

もともとの曲の速さも相まって, Marvelous を狙っている余裕はすでになく, ほとんどが早 Great になってしまったが,
私にとっては貴重なレベル 13 の LIFE4 クリアとなった.

このスコア内容を見てのとおり, ランク AA+ (95万点以上) を獲得して ACE FOR ACES の出現を狙うだけの余裕はないので,
後は解禁をゆっくり待ちたいと思う.

ENDYMION BDP 798390 (140-111-196-19-14-2)
ENDYMION BDP 初クリア 20180421

ENDYMION BDP 攻略中

毎週, ENDYMION Double Basic に挑戦しているところであるが, 今日は久々に記録を更新できた. とはいっても, クリアできたということではなく, 4 ミスするまでの記録が伸びたということではあるが.

ようやく変則リズム地帯を抜けるか, というところで足が追い付かなくなって 4 ミス目を喫してしまう.

記録更新を狙うには, もっと基礎能力 (足さばきも体力も) を向上しないといけないと痛感. そろそろ, 毎年参加しているマラソン大会の時期も近づいたので, 体力向上のためのトレーニングを開始したい.

ENDYMION BDP 620330 (131-97-100-10-10-4) Failed at 2818-03-17T15:11
ENDYMION BDP 進捗状況20180317

第76期順位戦 A 級最終局を観戦してきました

万難を排しても観戦したかった将棋の順位戦A級最終局. 前日に現地入りしたかったが, 利用する予定の公共交通機関が荒天のために運休するかもしれず, 不安に苛まれながら時期を待っていたが, 結構な遅延があったものの何とか運行し, 無事前日 (3月1日) 入りを果たせた.

順位戦はリーグ形式で行われる棋戦であり, 八大タイトルの中でも竜王位と並び最上位とされる名人位をかけた予選の位置づけとなっている.
順位戦は上位のリーグから順番にの A 級 (原則 10 名) から B1 級 (原則 13 名), B2 級 (この組以下は人数不定), C1 級, C2 級の5つのリーグからなる棋戦である. 日本プロサッカーの J リーグのように, 毎年各リーグの上位と下位でそれぞれ入れ替えが発生し, 飛び級の精度は存在しない. A 級の最高成績者がが名人と七番勝負を行い, その勝者が次期名人となる. リーグ終了時点で相星の場合, 該当する棋士の優劣は前期の順位の高い順に次期の順位が割り当てられるため, 仮にリーグの昇降級及び残留がリーグ途中で確定しても, 次期の順位に影響がある限りはいわゆる捨て対局はほとんど発生しない. よって, 他の棋戦にあるリーグ戦とは異なり, ほぼ全員が最後まで気が抜けない棋戦となる.

さて, 大盤解説会が始まるまでに時間があったので, 三保の松原を見て歩きつつ時間を過ごし, 記念写真を撮りつつ, 対局が深夜に及ぶことが予想されることからドリンク剤を調達しておいた.

さて, 対局前の状況は次のとおりであった.

最終局前の勝敗状況 (名人挑戦 1 名, 降級 3 名)
前期順位 氏名 次局対局相手
9 久保利明 王将 6 3 深浦康市
10 豊島将之 八段 6 3 広瀬章人
2 羽生善治 竜王 6 4 (対局なし)
1 稲葉陽 八段 5 4 行方尚史
4 広瀬章人 八段 5 4 豊島将之
8 佐藤康光 九段 5 4 屋敷伸之
3 渡辺明 棋王 4 5 三浦弘行
7 深浦康市 九段 4 5 久保利明
11 三浦弘行 九段 4 5 渡辺明
5 行方尚史 八段 3 6 稲葉陽
6 屋敷伸之 九段 2 7 佐藤康光

順位戦の他のクラスの最上位における相星は前期順位により昇級枠の足きりが発生するが, A 級最上位での相星は前期順位をもとにしたパラマス式トーナメント (ステップラダー) が組まれ, 最後の勝ち残りが名人に挑戦する. 今回の場合は最大で 6 名が 6 勝 4 敗で並ぶ可能性がある.

逆に, 降級枠に目を向けると, 屋敷伸之九段が最下位で降級することが確定してしまっているので, 数少ない捨て対局となってしまっている. もちろん, 勝ち負けで対局料 (ボクシングでいうところのファイトマネー) は変わるはずなので, そういう意味では手抜きをすることはないはずであるが... あとの 2 枠が気になるところである. 行方尚史八段はかろうじて残留の目があるものの, 自身が勝ったうえで深浦康市九段と三浦九段がともに負けないと残留できない. 渡辺明棋王, 深浦康市九段, 三浦弘行九段は勝てば自力で残留が決められるので, 何としてでも勝ちたいところ. 特に, 渡辺明棋王と三浦弘行九段は直接対決するので, 残留決定戦の様相となっている.

そして, 対局の結果は...

将棋棋士の藤井聡太氏が現役中学生として初の六段昇段を決める

5人目の中学生将棋棋士として有名となった藤井聡太氏が2月17日付で六段昇段を決めた. 将棋棋士は四段昇段後からプロということになるが, 現役中学生がプロ棋士の六段に昇段したのは史上初である. また、これは最年少記録である。

なお、五段に昇段した唯一の中学生でもあるが、過去に中学在学中に昇段を内定させていた棋士として加藤一二三氏がいる。
また、五段昇段の最年少記録は加藤一二三氏である。

なお, 藤井聡太六段には最年少七段の記録を狙う機会がまだ残っている.
2018年度までに条件を満たす機会が残っている棋戦と昇段条件は次のとおりである.

  • 第66期王座戦 (2018年9月頃) タイトル獲得すると六段以下の棋士に限り七段へ昇段 (執筆時点で二次予選進出)
  • 第44期棋王戦 (2018年9月頃) タイトル獲得すると六段以下の棋士に限り七段へ昇段 (執筆時点では予選対局待ち)
  • 第31期竜王戦 (2018年12月頃) 今期で4組昇級を果たすと連続昇級により段位が1つ昇段 (執筆時点で昇級まであと3勝)
  • 第68期王将戦 (2019年1月頃) タイトル獲得すると六段以下の棋士に限り七段へ昇段 (執筆時点では一次予選進行中)

他のタイトル戦の昇段規定と最年少記録の更新の関係は次のとおり

  • 第77期及び第78期順位戦 (2020年3月頃) 2018年度に所属するC1級で昇級を決めると B2 級へ、さらに B2 級で昇級を決めると B1級順位戦への昇級となり、この時点で七段になっていない場合は七段になれる. 順位戦は飛び級規定が存在しないため、順位戦の昇段規定では加藤一二三氏の最年少七段及び最年少八段の記録は更新できない。なお、名人戦への挑戦権を獲得するには、さらに上のA級順位戦で優勝する必要がある。名人獲得で九段昇段となるのは理論上最速で2022年5月となる。
    よって、最年少九段の達成は順位戦・名人戦でも可能である。
  • 第31期竜王戦 (2018年12月頃) 今期で4組昇級を果たすことができれば七段へ昇段することは前述のとおり。さらに, ランキング戦5組優勝を果たし、
    竜王挑戦トーナメントで竜王挑戦権を得て竜王を獲得できれば八段へ昇段となる。
  • 第32期竜王戦 (2019年12月頃) 前期で5組残留となった場合は4組昇級だけでは「連続昇級」の要件に該当しないので七段へ昇段することはできない。ただし, ランキング戦5組優勝を果たし、竜王挑戦トーナメントで竜王挑戦権を得た時点で七段昇段となる。竜王を獲得できれば八段へ昇段となる。
  • 第4期叡王戦 (2019年6月頃) タイトル獲得すると六段以下の棋士に限り七段へ昇段 (執筆時点では段位別予選の組み合わせ決定待ち)
  • 第60期王位戦 (2019年9月頃) タイトル獲得すると六段以下の棋士に限り七段へ昇段 (執筆時点では第59期王位戦予選敗退)
  • 第90期棋聖戦 (2019年7月頃) タイトル獲得すると六段以下の棋士に限り七段へ昇段 (執筆時点では第89期棋聖戦予選敗退)

他、最年少段位獲得記録を更新するには、実質的に次の条件を早期に満たすこととなる。(勝数規定では最年少段位獲得記録の更新には間に合わない)

  • 最年少七段達成:いずれかのタイトル獲得、NHK杯テレビ将棋トーナメント優勝、朝日杯将棋オープン戦優勝のうちのいずれかを2020年11月までに達成する。
  • 最年少八段達成:竜王獲得を2021年11月までに達成する。第31期または第32期であればフルセット勝負でも間に合うが、第33期の場合は4勝0敗で奪取しないと日程上最年少記録を更新できない。
  • 最年少九段達成:第80期(2023年)までに名人獲得、第36期(2023年)までに竜王2期獲得、タイトル3期獲得かつ八段昇段(順位戦A級昇級か竜王1期獲得)のうちのいずれかを2024年3月までに達成する。

なお, 歴代の最年少昇段記録は追記のとおりで合っているはず. (誤りがあればコメントで指摘願います)

将棋の最年少昇段記録
段位 記録保持者 昇段日 昇段時年齢 昇段理由
四段 藤井聡太 2016年10月1日 14歳2か月 第59回(2016年度前期)三段リーグ1位
五段 加藤一二三 1955年4月1日 15歳3か月 順位戦C級1組へ昇級 (第9期(1955年度)順位戦C級2組西組1位)
六段 藤井聡太 2018年2月17日 15歳6か月 五段昇段後全棋士参加棋戦優勝 (第11回朝日杯将棋オープン戦優勝)
七段 加藤一二三 1957年4月1日 17歳3か月 順位戦B級1組へ昇級 (第11期(1957年度)順位戦B級2組1位)
八段 加藤一二三 1958年4月1日 18歳3か月 順位戦A級へ昇級 (第12期(1958年度)順位戦B級1組2位)
九段 渡辺明 2005年11月30日 21歳7か月 竜王位2期