作者別: ARQ

記事の都合上, 解釈が面倒な数式を書くので, 同じ式を表現した WolframAlpha へのリンクを設定しています.

連分数とは、分数の分母にさらに分数が含まれるような数値表現である.

例えば, 1+2/(3+4/(5+6/7))というようなものである.

特に、分子の部分がすべて 1 になっているような連分数のことを正則連分数といい, 単に連分数といった時には正則連分数であることを暗黙で示していることがある.

正則連分数について, a₀+1/(a₁+1/(a₂+1/a₃)) を [a₀; a₁, a₂, a₃] と表現する. 各 a_i は正の整数 (a₀ は0や負の値を含めた整数) である.

ある実数を(正則)連分数に変換することを連分数展開というが, 有理数ならば有限項の連分数で, 無理数ならば無限項の連分数で表現されることがわかっている.例えば, 355/113=[3; 7, 16], π=[3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1, 1, 2, 2, 2, 2, 1, 84, 2, 1, 1, 15, 3, 13, 1, ...] となる.

無理数を分数(整数比)で近似する場合, 連分数展開を途中で打ち切って真分数や仮分数に戻すという手段が使われる。 そうして現れる分子や分母の値は, それ以下の整数を用いたあらゆる整数比(分数)よりもよりよい近似となることが知られている.

実際に, 例に挙げた 355/113=[3; 7, 16]=[3; 7, 15, 1] は 355 以下の整数を用いた分数の中で最良の円周率の近似である.

さて, 正則連分数展開は次の手順で行われる.

1. 正則連分数展開を行いたい数を ω₀ とし, n を 0 とする.
2. ω_n の整数部分を a_n とする.
3. ω_n の小数部分が 0 に等しい場合は, a_k (k≥n+1) は存在しない, すなわち, 連分数表現は a_n の項で打ち切る.
4. ω_n+1 を ω_n=a_n+1/ω_n+1 を満たすように定める.
5. n に 1 を加えて2番目の手続きに戻る.

この作業を行う数式処理ソフトををいくつか紹介する.

連分数近似を実装している数式処理ソフトの紹介

2018年11月16日にキログラムの定義を変更することが CGPM (国際度量衡総会)で可決され, 本日2019年5月20日により全世界的に施行されることとなった.

いままでのキログラムの定義は次のように物質に依存する定義であった。

• 水1リットルの重量
• 大気圧下で氷が溶けつつある温度における水1リットルの重量
• 最大密度(液温摂氏4度)における蒸留水1立方デシメートル(1リットル)の質量
• アルシーブ原器 (有体に言うと白金塊) の質量
• IPK (国際キログラム原器: 白金とイリジウムの合金)の質量

水はいろんなものを自然に溶かし込むし、金属も徐々にいろんなものを吸着して変質するので不変で安定したものというにははばかられた.

それでもIPKは誤差1億分の5という精度ではあったが, 近年の科学技術の発達により, これでも精度は足りないという状況であった.

今回の改訂は, 特殊相対性理論から得られた式 E=mc² と光子エネルギーの式 E=hν から m=hν/c² を得るので, 今までは実験値であったプランク定数を真の意味で定数とすることにより キログラムが定義されるということになる。

ただ, この定義に至る裏側で, 日本やドイツを中心とする科学者たちは (IPKと比べれば)手軽に作成できる原器を作り, その精度を裏付ける役割を担った. その原器はケイ素(シリコン)結晶である. このあたりの話は産業技術総合研究所のウェブサイトが詳しい.

非常に大きな数を扱うための概念として対数を高校数学で学習する. 例えば, 2¹⁰ は 10³ とほぼ等しい. 10 の累乗に値を換算したときの指数に相当する数を, その元の数の常用対数 をとった値というのである. これを式で表したものが log₁₀2¹⁰≈3 という関係である.

なお, 3dB(decibel( で 2 倍という関係はこの対数計算から得られるのである.

これを一般化すると, 1 ではない正の実数 a, 任意の実数 r について対数(logarithm(を次のように定義するということである。

a^r=R ⇔ log_aR=r

a=10 のときは常用対数, a=e (e: ネイピア数) のときは自然対数, a=2 のときは二進対数と特別に呼ばれる.

log_aR という表記であるが, 文脈から明らかな場合は底 a はしばしば省略される.

ここでよく話題になる話として, 様々な整数の常用対数をとるといくらになるのか? というものがある. いくつかの整数に対して, その概算値を出してみよう.

log(1) は正確に 0 である. なぜならば, すべての 0 ではない実数 R について R⁰=1 が成り立つからである.

log(2) は冒頭で話題にした 2¹⁰≈10³ の関係から 10log(2)≈3 ⇔ log(2)≈0.3 となる. 厳密には 2¹⁰>10³ であるから log(2)>0.3 である. 上からの評価もしたい. 1000<1024<1250 の関係を使うと. 常用対数をとると 3<10log(2)<=4-3log(2) となるから log(2)<4/13<0.3077 が得られるが、 ちょっとこれではおおざっぱすぎる. ここは天下り的ではあるが, 2⁹³<10²⁸ という関係を使う. すると, log(2)<28/93<0.3011 を得る.

log(3) についてもここでは近似値を求めることになる. 80<81 より 1+3log(2)<4log(3) から log(3)>19/40=0.475 という評価ができる. また, 20000>19683=3⁹ ⇔ 4+log(2)>9log(3) から log(3)<4/9+log(2)/9=400/837<0.4779

これらの値を用いて log(4)=2log(2), log(5)=1-log(2), log(6)=log(2)+log(3), log(8)=3log(2), log(9)=2log(3) が概算できる.

1桁の整数の残り log(7) は様々な近似が検討されている. 例えば, 48<49<50 ⇔ 4log(2)+log(3)<2log(7)<2-log(2) より 67/80=0.8375<log(7)<17/20=0.85 という簡易的な評価がある. もうちょっと精度を上げるならば 7⁴=2401>2400 ⇔ 4log(7)>2+3log(2)+log(3) より log(7)>27/32=0.84375, 48×1024/1000>49 ⇔ 14log(2)+log(3)-3>2log(7) より log(7)<1417/1674<0.8465 さらには, 10⁶<2²×3⁶6×7³ と 2¹⁰×7⁸<3¹⁰×10⁵ を評価すれば小数第3位まで確定できる.

最後に log_e(10) を評価する. そうすると, 自然対数と常用対数の変換に必要な定数が得られるのである. ただ, こちらについては積分計算により求めるのが一般的だろう. ∫₁²(1/x)dx=log_e(2) という関係があるからだ. 被積分関数は積分区間内において凸関数なので、台形近似では収束がちょっと遅い. シンプソンの公式なら劇的に早く収束する. 具体的には (1/(6n))(1+2Σ_j=1^n-11/(1+2j/(2n))+4Σ_j=1ⁿ(1/(1+(2j-1)/(2n)))+1/2) これを必要な精度まで計算して log₁₀(2) で割ると log_e(10) が得られる. シンプソンの公式は4次収束なので、n=2 でも3桁の精度は出る. log_e(2)≈0.693 なので log_e(10) は 2.25 から 2.31 の範囲にあるといえる.

おまけ: 連分数による近似

今年もよろしくお願いいたします.

昨年の積み残しがあるので今年は何とかクリアしたいです. 何とか次のものは達成したいところ.

• 数学検定1級合格
• 統計検定1級合格
• TOEICで人並みの点数を取れるようになるか英検準1級をとれるように頑張る
• 5kmを40分以内に走り切れる体力を取り戻す

学習の成果はこのブログにもちょっとずつ載せていきますので, 小難しい記事が増えるかもしれません...

今後ともよろしくお願いいたします.

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

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

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

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

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

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

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

1. r₀=a, s₀=1, t₀=0, r₁=b, s₁=0, t₀=1, i=1 とする.
2. r_i+1=r_i-1-q_ir_i を 0≤r_i+1≤abs(r_i), q_i は整数となるように定める.
3. s_i+1=s_i-1-q_is_i, t_i+1=t_i-1-q_it_i とする.
4. r_i+1=0 の場合は x=s_i, y=t_i であるので計算を終了する. r_i+1≠0 の場合は次の項目に進む.
5. i に 1 を加えて 2. の項目へ戻る.

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

個人的メモ

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

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

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

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

具体例

個人的なメモ

• フェルマーの小定理とは次の関係を言う: 素数 p と p とは互いに素な整数 a について a^p-1≡1 (mod p) が成り立つ.
• 数論におけるオイラーの定理とは次の関係を言う: 任意の正の整数 n と n とは互いに素な整数 a について a^φ(n)≡1 (mod n) が成り立つ.
  • φ(n) はオイラーのトーシェント関数であり、これは n 以下の n とは互いに素な正の整数の数となる。
  • n=Π_k=1^mp_k^b_k と素因数分解できたならば, φ(n)=nΠ_k=1^m(1-1/p_k)
• カーマイケルの定理とは次の関係を言う: φ(n) は a^m≡1(mod n) を満たす最小の m であるとは限らない.
  最小の m はカーマイケル関数λ(n)で与えられる.
  • カーマイケル関数は次のように再帰的に定義される.
    • λ(2^e)=1 (e=1), 2 (e=2), 2^e-2 (e≧3)
    • 奇素数 p について λ(p^e)=p^e-1(p-1)
    • n=Π_k=1^mp_k^b_k と素因数分解できたならば λ(n)=lcm(λ(p₁^b₁),...,λ(p_m^b_m)). ただし, lcm は引数たちの最小公倍数(least common multiple)を表す。

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

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

2018年6月に実施された統計検定の準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期

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

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

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

おまけ