ぺるせんたげの学習帳

手作り数学のブログです

斜辺を共有するピタゴラス数たち（解決編）

手作り数学

これの続きです。↓↓↓

percentage011.hatenablog.com

今回はこれの解決編として、非原始解も含めた二平方和分解の正確な個数とその具体的な値を与えます。これにより、斜辺を共有するピタゴラス数たちについての完全な情報の記述を目指します。



1. 前回の復習

斜辺を共有するピタゴラス数の二平方和分解の方法について、前回の記事で以下のような結果を得ました。

斜辺の長さ

\displaystyle{c=(\prod_{i=1}^{N}p_i^ {s_i})(\prod_{i=1}^{M}q_i^ {t_i})}

について、
1) t_i=0の場合:
　1つのcに対して原始ピタゴラス数は少なくとも2^ {N-1}個存在する
　非原始解を含めるともっとたくさん存在すると予想される
2) s_i=0の場合:
　ピタゴラス数にならない
3) t_iが非負偶数のとき:
　原始解を持たないが、非原始解を少なくとも2^ {N-1}個持つ

c の素因数を 4 で割ったあまりで分類することで、分解できる条件と原始解の個数の下限が得られました、というのが前回までのあらすじです。

逆にわかっていないのは、非原始解の個数とその具体的な値、分解と再構成の方法がガウス整数の範囲での因数分解とブラーマグプタの二平方恒等式によるもの以外に存在するのかしないのか、でした。これが原因で少なくともという控えめな主張に留まっています。
ということで、前回手をつけなかった非原始解について調べます。

2. 非原始解の構成

これまで非原始解についてはあまり触れてきませんでした。先に原始解について考察した方が見通しが良くなるだろうという直感があったからです。
前回の記事では、一度分解した素因数が再生しないように分割することで原始解を構成しました。そうしなければ分解した素因数が再生して非原始解になってしまうからでした。よって、今回は一部だけ分解しないまま残すことで非原始解を構成します。
4で割って3余る素数q_iはいくつあっても分解の個数に影響しないので、4で割って1余る素数p_iのみを素因数に持つ場合を考えます。つまり上の式においてt_i=0として考えます。

分解しない素因数として、例えばs_N個あるp_Nのうち一つだけを分解しないことを考えると、まず思いつく非原始解は\frac{c}{p_N}の原始解にp_Nをかけた形のものです。\frac{c}{p_N}の原始解はD\left(\frac{c}{p_N}\right)個存在し、それぞれにp_Nをかけることで同数の非原始解が生成されるので、このようなタイプの非原始解の個数はD\left(\frac{c}{p_N}\right)です。
また、前回の記事で示したように、原始解の個数は素因数の指数に依存しません。素因数の種類の個数のみが大事でした。なので一般にD(c)=D\left(\frac{c}{p_N}\right)=D\left(\frac{c}{{p_N}^{2}}\right)=D\left(\frac{c}{{p_N}^{3}}\right)=\cdots =D\left(\frac{c}{{p_N}^{s_N-1}}\right)となります。

ここでp_Nを全く分解せず完全に保存すると、分解の対象は\displaystyle{\prod_{i=1}^{N-1}p_i^ {s_i}}となり、分解の対象に含まれる素因数の種類が減るので、指数が原始解の個数に影響しないことを考慮することで、原始解の個数は\displaystyle{D\left(\prod_{i=1}^{N-1} p_i\right)}となります。

これは非原始解の個数を考える上で大事な点です。
分解の対象に含まれる素因数の種類の個数が変わらないうちは、その素因数の指数がなんであれ原始解の個数が一定なので、分解の対象に含まれる素因数p_iの指数を\sigma_i (1\leq \sigma_i \leq s_i)、分解の対象に含まれない素因数の添字をl_\lambdaとすれば、L_n=\{l_1, l_2, \cdots , l_n\}として
\displaystyle{D\left(\frac{c}{(\prod_{i \notin L_n}p_i^ {s_i-\sigma_i})(\prod_{i \in L_n}p_i^ {s_i})}\right)=D\left(\prod_{i\notin L_n}p_i ^{\sigma_i}\right)=D\left(\prod_{i\notin L_n}p_i\right)}です。
ここで、nにはn \lt Nという条件を課しておきます。n=Nのときは分解の対象が1となり、この場合は考えても意味がないからです。

こうして得られた原始解に、分解しないまま保存しておいた素因数を全てかけることで、分解の対象に含まれる素因数の種類の個数がN-nのときの分解が全て得られることになります。\forall i, \sigma_i=s_iの場合が原始解、それ以外の場合が非原始解に相当し、\{ \sigma_i | i \notin L_n \}の選び方は\displaystyle{\prod_{i \notin L_n}s_i}通りあるので、あるL_nに関する(非原始解も含めた)分解の個数をE(L_n)とすると、ここまでの議論は次の式としてまとめられます：
\displaystyle{E(L_n)=\left(\prod_{i\notin L_n}s_i\right) \times D\left(\prod_{i\notin L_n}p_i\right)}


3. 非原始解の網羅

次に、あるnに対して可能な全てのL_nについて考えます。

L_nはN個の素因数p_iのうち分解の対象に含まれないものの添字の集合なので、その選び方は{}_N C_n通りあり、前節で得たE(L_n)に{}_N C_nをかければ良い……となれば楽ですが、実際にはこうなりません。各素因数p_iの指数s_iが同じとは限らないために、L_nの中身が違えば\displaystyle{\prod_{i\notin L_n}s_i}が違ってくる可能性があるからです。
よって、\displaystyle{\sum_{L_n}}を「可能な全てのL_nについての総和」を得る記号として導入することで、あるnに関する(非原始解も含めた)分解の個数をE_nとすると、nが固定なら\displaystyle{D\left(\prod_{i\notin L_n}p_i\right)}はL_nに依らず一定なので、
\displaystyle{E_n=\sum_{L_n} E(L_n)=\sum_{L_n} \left(\prod_{i\notin L_n}s_i\right) \times D\left(\prod_{i\notin L_n}p_i\right)}
となります。
更に、nを0からN-1まで動かして足すことで、知りたかったcの分解の個数E(c)について、次の式が得られます：
\displaystyle{E(c)=\sum_{n=0}^{N-1}E_n=\sum_{n=0}^{N-1}\left\{\sum_{L_n} \left(\prod_{i\notin L_n}s_i\right) \times D\left(\prod_{i\notin L_n}p_i\right)\right\}}

さて、前回の記事で \displaystyle{D\left(\prod_{i\notin L_n}p_i\right) \geq 2^{N-n-1}}という不等式が得られているので、E(c)についても同様に
\displaystyle{E(c) \geq \sum_{n=0}^{N-1} 2^{N-n-1} \sum_{L_n}\prod_{i\notin L_n}s_i=\frac{1}{2} \sum_{n=0}^{N-1}\sum_{L_n}\prod_{i\notin L_n}2s_i}
と書けます。

この中で\displaystyle{\sum_{L_n}\prod_{i\notin L_n}2s_i}の部分は、可能な全ての組合せL_nに従ってN個の2s_iの中からN-n個選んで積を作り、それらを全て足したものです。これはN次多項式\displaystyle{\prod_{i=1}^{N}(x+2s_i)}のn次の項の係数に一致するので、
\displaystyle{E(c) \geq \frac{1}{2} \left\{\prod_{i=1}^{N}(1+2s_i)-1\right\}}
となります。最後に1を引いているのは、N次多項式\displaystyle{\prod_{i=1}^{N}(x+2s_i)}のN次の項に対応するn=Nの場合を除いているからです。


これで、原理的に特定できないs_iのみで書かれた式になりました。

4. ヤコビの二平方定理

限界まで情報を抽出することで、原始解の評価から更に進んで c の分解についての一定の評価ができました。
ここからどうしようか、という話になりますが、実はこの問題はほとんど解決されています。それを教えてくれるのがヤコビの二平方定理です。

ヤコビの二平方定理 自然数nを高々二個の平方数の和で表す方法の数r_2(n)は
\displaystyle{r_2(n)=4\sum_{2\nmid d|n}^{}(-1)^{\frac{d-1}{2}}}
で与えられる


2\nmid dは「2はdの約数ではない」、d\mid nは「dはnの約数である」、という意味です。
この式を日本語に翻訳すると、「n の約数のうち、4 を法にして 1 と合同になるものの個数から 3 と合同になるものの個数を引いたものの 4 倍に等しい」くらいのことになります。

……これこそまさに求めていた分解の個数そのものですね。
正確には、ヤコビの二平方定理の言う「平方数の和」とは、n^ 2=0^ 2+n^ 2を含み、更にn^ 2=(\pm a)^ 2+(\pm b)^ 2=(\pm b)^ 2+(\pm a)^ 2のように左右や負号を入れ替えたものも区別します。この記事では前者を考えないため 4 通りを除外し、後者については全て同一視するので個数が \frac{1}{8} になるので、分解の個数は r'_2(n)=\frac{1}{8}\{r_2(n)-4\}とカウントします。

さて、c は4 を法にして 1 と合同になる素因数p_i のみでできているので、c^2の約数のうち、4 を法にして 1 と合同になるものの個数は\displaystyle{\prod_{i=1}^{N}(2s_i+1)}です。
従って、上の式を使えば\displaystyle{r_2(c^2)=4\sum_{2\nmid d|c^2}^{}(-1)^{\frac{d-1}{2}}=4\prod_{i=1}^{N}(2s_i+1)}と書け、これを r'_2(c^2)に変換すると \displaystyle{r'_2(c^2)=\frac{1}{8}\left\{4\prod_{i=1}^{N}(2s_i+1)-4\right\}=\frac{1}{2}\left\{\prod_{i=1}^{N}(2s_i+1)-1\right\}}となります。


これはE(c)の下限そのものです。一方でヤコビの二平方定理は言わば分解個数の上限を与えるものなので、上限と下限が一致しました。

以上から、c の二平方和分解の正確な個数とその具体的な値が、前回の記事で行ったブラーマグプタの二平方恒等式による方法で完全に記述しきれていることがわかりました。

5. 結論

ピタゴラスの定理について「一つの斜辺の長さがどんな場合にいくつの解を持つのか」という疑問から始まって、最終的にヤコビの二平方定理の詳細について、完全な記述とその具体的な値の構成法が得られました。

ここで、得られた結果をまとめておきます。

斜辺の長さ \displaystyle{c=(\prod_{i=1}^{N}p_i^ {s_i})(\prod_{i=1}^{M}q_i^ {t_i})} について、
1) t_i=0の場合:
　原始解は2^{N-1}個
　非原始解を含めると\displaystyle{\frac{1}{2} \left\{\prod_{i=1}^{N}(2s_i+1)-1\right\}}個
2) s_i=0の場合:
　ピタゴラス数にならない
3) t_iが非負偶数のとき:
　原始解はない
　非原始解は\displaystyle{\frac{1}{2} \left\{\prod_{i=1}^{N}(2s_i+1)-1\right\}}個


前回の課題を解決できてよかったです。

終わり




参考

ヤコビの二平方定理 - Wikipedia

抽象化〇×クイズの最小手数

手作り数学
全n問の○×クイズを、満点がとれるまでやり直す。ただし、各問題の正誤は不明だが、過去に行った各回の点数は分かるとする。
このとき、どんな場合にも満点をとるには何回繰り返せば良いか？

問題の作成者：SOx @SOx_S_R_M



今回は論理パズルのお話です。


※上の目次のうち、重要な(そして面白い)のは 4. 論理的に考えてみる 以降です。数学的な話以外に興味がなければそこから読んでください。



1. 抽象化○×クイズ

問題の意味を確認します。

○×クイズとは、正解が○か×である問題に対し、○か×かで回答する二択形式のクイズのことです。

例：
　Q . 太陽は地球の周りを回っている。○か×か？
　A . ×

このように、正解が×であるときは、×と答えると正しい回答になります。正しい回答をしたら○とか、間違った回答をしたら×、とかいうことではないので注意しましょう。

さて、今回はn問の○×クイズがあり、何度か挑戦してそれら全てに正解することを目指し、最悪の場合での最小手数を考えます。ただし正解/不正解のフィードバックは、個々の問題についてはされず、総合得点のみ分かるという状況です。例えば正解が"○×○"である場合に"×××"と回答すれば1問正解となります。
また、満点と書かれていましたが、1問正解すると何点得られるのかは不明です。とりあえず1点として一般性は失われませんが、この点については後で議論します。

それでは早速やっていきましょう。

2. 愚直な方法

当たり前ですが、個々の問題の正解を知ることができれば全問正解です。なので個々の問題について一つ一つ正解を確認していけば良いです。

前述のとおり、○×クイズは二択です。よって特定の1問以外の回答を統一して、その1問について○と×の場合の得点を比較することで正解がわかるはずです。
1問目について○と×の場合を比較し、1問目の回答を判明した正解に固定して2問目について○と×の場合を比較し、2問目の回答を判明した正解に固定して3問目について○と×の場合を比較し……というのをn問目まで繰り返せばすべての正解がわかり、満点が得られます。
この方法では2n回の試行が必要……そうですが、実は正解を知るだけなら2n-1回でも十分です。n問目の正解については一度確認すればn-1点かn点かがわかるので、2回確認する必要がないのです。2n-1回目の試行で全ての正解がわかり、その時点で全問正解を達成するか、2n回目の試行で全問正解するかのどちらかです。

ということで、この方法での最小手数は最悪の場合で2n です。

3. もう少し賢い方法

得点しか情報がないので、基本的には各試行の得点の差を使って考えていくしかありません。上の方法も得点差を利用したものですが、もっと効率的な方法があります。一つの共通の基準と個々の問題を比較するのです。

1回目は(キャリブレーションとして)全て○で回答を出し、その得点を確認します。2回目は1問目だけを×にして回答し、その得点を確認します。1問だけ回答を変えているので得点は1増えるか1減るかのどちらかです。増えれば×が正解だったことになり、減れば○が正解だったということです。どちらであれ1問目の正解がわかります。
以降も同様に得点の増減を確認することで、各問題の正解を決定できます。

この方法は最初のキャリブレーションの1回と後の正解決定のn回の合計n+1回が必要……そうですが、全ての正解を決定するだけであれば、やはりn回で十分です。
n回目の試行が終わった時点での状況をよく見てみると、1問目~n-1問目までの正解が判明していて、n回目の試行は1問目~n-2問目までが正しい解答を選んでいて、n-1問目が正解か不正解のどちらか(どちらかは判明している)で、n問目はどちらかわからない状態です。このとき、n回目の試行の得点によって場合分けすることができます。
1. n点の場合：運良く全問正解だった場合です。この時点で全問正解が達成されました。
2. n-1点の場合：更に場合分けします。
　2-1. n-1問目が正解の場合：n問目が不正解であるとわかるので、n+1回目の試行で全問正解が可能です。
　2-2. n-1問目が不正解の場合：n問目が正解であるとわかるので、n+1回目の試行で全問正解が可能です。
3. n-2点の場合：n-2問目までは全て正しい解答を選んでいるので、残り2問はどちらも不正解であったということです。それらの回答を変えることで、n+1回目の試行で全問正解が可能です。

以上から、どの場合でもn+1回目の試行までには全問正解できることがわかります。

※一応書いておくと、○と×は入れ替えても問題ありません。シンボル自体に意味はないからです。

4. 論理的に考えてみる

上2つの方法はどちらも直観によって得られたものです。特に2つ目の方法は非常に効率が良さそうですが、今回知りたいのは"最小"手数です。直感的な方法ではなかなか最小性を保証できません。
そこでほしくなるのが数学による保証です。公理に従っていれば数学は公理の範囲で常に正しさを保証してくれるいいヤツなので、どうにか今回の問題を数学の言葉で表現したいところです。
そこで、2つ目の方法を数学の言葉に置き換えてみましょう。

i回目の試行での回答セットを行ベクトルA_i、n個の正解を順番に並べた列ベクトルをc、各試行での得点をp_iとします。
ところで、回答セットと正解はすべて○か×ですが、普通これらは計算できないので、このままでは扱いにくいです。そこで、○と×を対応する計算可能なものと置き換えます。具体的には○を1に、×を-1に対応付けます。
こうすると、○×クイズの挙動と計算が以下のようにXOR(排他的論理和)っぽく上手く対応します。

回答が○、正解が○の場合：1×1=1 (正解)
回答が○、正解が×の場合：1×(-1)=-1 (不正解)
回答が×、正解が○の場合：-1×1=-1 (不正解)
回答が×、正解が×の場合：-1×(-1)=1 (正解)

つまり、○と×に1と-1を、正解/不正解と積を対応付けることができるのです。
具体的に見てみましょう。

正解が"○×○"である場合にi回目の試行として"×××"と回答する状況では、c=(1,-1,1){}^T、A_i=(-1,-1,-1)なので、A_i\cdot c=p_i=(-1×1)+(-1×(-1))+(-1×1)=-1となります(右上のTは転置記号です)。
上で見たようにこの場合の得点は1点ですが、p_i=-1です。このズレは不正解のときの点数の違いが原因で、内積を利用した対応付けにより最小値は-nとなります。

これをn回の試行に関して考えると、A_iを積み重ねた回答行列Aと得点ベクトルpにより、Ac=pと表せます。
知りたいのは正解、つまりcです。Aが正則であればc=A^{-1}pとしてn回の試行と得点から計算できるので、n回の試行を一次独立になるように気をつけて行えば良いです。
ここで本題である最小性について考えます。Aとcの内積を計算するためにはAはn行である必要があり、正解の完全な情報を含むcを得るには正則な回答行列Aを得る必要があります。よってcを得るにはn次正則行列Aが必要になるのです。これは最低でもn回は試行が必要であることと同値なので、n回の試行の最小性が保証されます。

これで正解がわかることを2つ目の方法で確認してみましょう。
n=3、1回目の回答を"○○○"、2回目の回答を"×○○"、3回目の回答を"○×○"とすると、

 \begin{pmatrix}
1&1&1\\
-1&1&1\\
1&-1&1
\end{pmatrix}
c=
\begin{pmatrix}
1\\
-1\\
3
\end{pmatrix}

となり、Aは正則になっています。よってこの3回の試行でcが計算でき、

c=\frac{1}{2}
\begin{pmatrix}
1&-1&0\\
1&0&-1\\
0&1&1
\end{pmatrix}
\begin{pmatrix}
1\\
-1\\
3
\end{pmatrix}
=
\begin{pmatrix}
1\\
-1\\
1
\end{pmatrix}

全ての正解が"○×○"であることがわかります(今回は更に運良く3回目で全問正解もできていますが、常にこうなる訳ではありません)。

以上のことから、n問の○×クイズで全問正解するために必要な最小回数は最悪でn+1です。

5. 得点の変換

ここまで○×クイズの得点を1点と0点、○と×を1点と-1点に対応させてきました。この変換の正当性を確認しておきます。

変換前の得点の組を(T, F)、m問正解したときの変換前の合計得点をS(m)、変換後の得点の組を(T', F')、m問正解したときの変換後の合計得点をS'(m)とする。このとき
S(m)=mT+(n-m)F, S'(m)=mT'+(n-m)F'となる。
S(m)からS'(m)への変換は変換関数\phi: S'(m)=\phi(S(m))=\frac{T'-F'}{T-F}S(m)+\frac{TF'-T'F}{T-F}nを定義することで可能になる。
T, F, T', F'は任意なので、T=1, F=0, T'=1, F'=-1とすることで、上の議論で行った変換が可能であることが保証される。

6. 感想

自然言語で書かれた論理パズルを数学の言葉で書き直すことで厳密で見通しの良い議論ができました。
数学の効力は数学の提供する公理系が実際の問題と同一視できる場合に発揮されますが、その場合には非自明な結論を行うのに非常に強力です。このことを簡潔に評した言葉を引用して今回は終わりにしたいと思います。


"数学は着想や概念をフォーマリズム（形式化された理論的手続き）に翻訳し, そのフォーマリズムを適用して, あまり形式的でない分析が通常なら施せないような洞察を導き出す."

―― J. ヨスト, 現代数学の基本概念 上, 丸善出版, 2019


ぺるコン第3問をPythonに解かせてみた+おまけ

2018年秋にツイッターでぺるせんたげ数学コンテスト(ぺるコン)と題した数学の問題3問セットを公開しました。結構拡散してもらって、何人かが解答をくれたりツイートしてくれて、出題者としてとても楽しませてもらいました。
ありがとうございます。m( )m

さて、今回の本題。ぺるコン3問目です。
まずマシンパワーによる力業で解き、その後でちゃんとした解答例も公開します。

問題は以下のようなもの。

先に言っておくと、3問目は問題が間違っています。条件を満たす組があります。それを探してもらうという問題に変更しました。この記事でもそうします。

解答例では、素数であることや式変形によって得た満たすべき条件を使ってしらみつぶす量を減らすという方針で解いています。
しかし、現代のコンピュータの圧倒的な計算パワーの前では論理などいらないのです。
力こそパワー。


1. 現代魔法で解いてみよう！

少しどうでもいい話。
プログラムはコンピュータの底知れぬパワーで問題を解決してくれますが、(一部のすごい詳しい人を除いて)ぼくみたいな一般人はコンピュータがどうやって動いているかは知りません。

なんか0と1がピコピコするんでしょ、くらいの認識です。

そんなパワフルさとブラックボックスであることを指して、プログラムのことを現代魔法と呼んでいます。

ぺるコンを作るにあたって主に解答例作成で協力してくれたSOx氏が言い出したことです。

言い得て妙ですね。言い得て妙って言いたかっただけです。


本筋に戻ります。

この3問目の恐らく最初の正解者であるFoxQさん(https://twitter.com/foxq_stm)は、Pythonで解決し、問題文が間違っていることを指摘してくれました。FoxQさんはぺるコンを自身のブログで紹介してくれてもいます。ありがたいことです。以下にそのブログへのリンクを付しておきます。こちらもどうぞ。

sky-time-math.hatenablog.jp


ぼく自身はその方法で確かめていなかったので、この機にやってみようと思いました。


Pythonさんに解いてもらうにあたって考えたのは次のことです。

・順列つくるのどうしよう
・重複判定どうしよう

1つめはループ文(for文)をいっぱい使って作ろうかなぁ、でもめんどくさそうだなぁと思って調べたらitertoolsというとても便利な標準ライブラリを見つけたので、それを使いました。たった1行で9!=362880個の順列を作れました。

2つめは、出題者としては分母の積と分子の組が一致していれば重複とみなす、ということにしていたので、出力もこの条件の下で重複は排除したものにしようと思いました。ここで初心者ぺるせんたげは躓きました。
あれこれ考えた結果、

各項を構成する3つの数の組が3つとも重複していて、更に各項の分子が分母を構成する数に対して同じであれば、重複である。

という定義で判断させることにしました。リストとかディクショナリとかいろいろ使ってなんとか実装できました。
あとはプログラムを動かすだけです。

結果はこうなりました。かっこが多いのは仕様です。

pythonさんの解答

一応確かめてみると、

\frac{1}{3×6}+\frac{5}{8×9}+\frac{7}{2×4}=\frac{1}{18}+\frac{5}{72}+\frac{7}{8}=1

おおー、合ってますね。

一瞬で答えを導いてくれました。まさに現代魔法。

2. 論理の力で解いてみよう！

一応理系の大学生なので、計算ゴリラにならずちゃんと論理的に解答を導きました。

証明

まず、分母に5と7が入らないことを示します。
\frac{a}{bc}+\frac{d}{ef}+\frac{g}{hi}=1 \Leftrightarrow aefhi+bc(dhi+efg)=bcefhiで、右辺が整数なので左辺も整数である。このときb=5ならaefhiは5の倍数のはずだが、a~iの中でb以外に5の倍数はないので矛盾する。よってb \neq 5となる。対称性から分母に5は入らず、同様に7も分母に入らない。
このことから、5と7は分子に入るので、d=5, g=7とできます。

次に5と7の分母のどちらにも1が入らないことを示します。

1. 1が5の分母に入らないこと
e=1とすると\frac{5}{f} \lt 1 \Leftrightarrow f=6, 8, 9になるはずである。
1-(i). f=6のとき
\frac{a}{bc}+\frac{7}{hi}=1-\frac{5}{6}=\frac{1}{6}なので、\frac{7}{hi} \lt \frac{1}{6} \Leftrightarrow hi \gt 42
まだ使っていない数として2, 3, 4, 8, 9があるので、これを満たす組は\{h, i\}=\{8, 9\}であるが、
\frac{a}{bc}=\frac{1}{6}-\frac{7}{72}=\frac{5}{72}となり不適。
1-(ii). f=8のとき
\frac{a}{bc}+\frac{7}{hi}=1-\frac{5}{8}=\frac{3}{8}なので、\frac{7}{hi} \lt \frac{3}{8} \Leftrightarrow hi \gt \frac{56}{3} \Leftrightarrow hi \geq 19
まだ使っていない数として2, 3, 4, 6, 9があるので、これを満たす組は\{h, i\}=\{4, 6\}, \{3, 9\}, \{4, 9\}, \{6, 9\}であるが、それぞれ
\{4, 6\} \rightarrow \frac{a}{bc}=\frac{3}{8}-\frac{7}{24}=\frac{1}{12}かつ\{a, b, c\}=\{2, 3, 9\}
\{3, 9\} \rightarrow \frac{a}{bc}=\frac{3}{8}-\frac{7}{27}=\frac{25}{216}かつ\{a, b, c\}=\{2, 4, 6\}
\{4, 9\} \rightarrow \frac{a}{bc}=\frac{3}{8}-\frac{7}{36}=\frac{13}{72}かつ\{a, b, c\}=\{2, 3, 6\}
\{6, 9\} \rightarrow \frac{a}{bc}=\frac{3}{8}-\frac{7}{54}=\frac{53}{216}かつ\{a, b, c\}=\{2, 3, 4\}
となり不適。
1-(iii). f=9のとき
\frac{a}{bc}+\frac{7}{hi}=1-\frac{5}{9}=\frac{4}{9}なので、\frac{7}{hi} \lt \frac{4}{9} \Leftrightarrow hi \gt \frac{63}{4} \Leftrightarrow hi \geq 16
まだ使っていない数として2, 3, 4, 6, 8があるので、これを満たす組は\{h, i\}=\{2, 8\}, \{3, 6\}, \{3, 8\}, \{4, 6\}, \{4, 8\}, \{6, 8\}であるが、それぞれ
\{2, 8\} \rightarrow \frac{a}{bc}=\frac{4}{9}-\frac{7}{16}=\frac{1}{144}かつ\{a, b, c\}=\{3, 4, 6\}
\{3, 6\} \rightarrow \frac{a}{bc}=\frac{4}{9}-\frac{7}{18}=\frac{1}{18}かつ\{a, b, c\}=\{2, 4, 8\}
\{3, 8\} \rightarrow \frac{a}{bc}=\frac{4}{9}-\frac{7}{24}=\frac{11}{72}かつ\{a, b, c\}=\{2, 4, 6\}
\{4, 6\} \rightarrow \frac{a}{bc}=\frac{4}{9}-\frac{7}{24}=\frac{11}{72}かつ\{a, b, c\}=\{2, 3, 8\}
\{4, 8\} \rightarrow \frac{a}{bc}=\frac{4}{9}-\frac{7}{32}=\frac{65}{288}かつ\{a, b, c\}=\{2, 3, 6\}
\{6, 8\} \rightarrow \frac{a}{bc}=\frac{4}{9}-\frac{7}{48}=\frac{43}{144}かつ\{a, b, c\}=\{2, 3, 4\}
となり不適。
以上からe \neq 1である。対称性からf \neq 1なので、5の分母に1は入りません。

2. 1が7の分母に入らないこと
h=1とすると\frac{7}{i} \lt 1 \Leftrightarrow f=8, 9になるはずである。
2-(i). h=8のとき
\frac{a}{bc}+\frac{5}{ef}=1-\frac{7}{8}=\frac{1}{8}なので、\frac{5}{ef} \lt \frac{1}{8} \Leftrightarrow ef \gt 40
まだ使っていない数として2, 3, 4, 6, 9があるので、これを満たす組は\{e, f\}=\{6, 9\}であるが、
\frac{a}{bc}=\frac{1}{8}-\frac{5}{54}=\frac{7}{216}となり不適。
2-(ii). h=9のとき
\frac{a}{bc}+\frac{5}{ef}=1-\frac{7}{9}=\frac{2}{9}なので、\frac{5}{ef} \lt \frac{2}{9} \Leftrightarrow ef \gt \frac{45}{2} \Leftrightarrow ef \geq 23
まだ使っていない数として2, 3, 4, 6, 8があるので、これを満たす組は\{e, f\}=\{3, 8\}, \{4, 6\}, \{4, 8\}, \{6, 8\}であるが、それぞれ
\{3, 8\} \rightarrow \frac{a}{bc}=\frac{2}{9}-\frac{5}{24}=\frac{1}{72}かつ\{a, b, c\}=\{2, 4, 6\}
\{4, 6\} \rightarrow \frac{a}{bc}=\frac{2}{9}-\frac{5}{24}=\frac{1}{72}かつ\{a, b, c\}=\{2, 3, 8\}
\{4, 8\} \rightarrow \frac{a}{bc}=\frac{2}{9}-\frac{5}{32}=\frac{19}{288}かつ\{a, b, c\}=\{2, 3, 6\}
\{6, 8\} \rightarrow \frac{a}{bc}=\frac{2}{9}-\frac{5}{48}=\frac{17}{144}かつ\{a, b, c\}=\{2, 3, 4\}
となり不適。
以上からh \neq 1である。対称性からi \neq 1なので、7の分母に1は入りません。

今度はaの分母に1が入らないことを示します。
b=1とすると、Q=ef, R=hiとおいて
\frac{a}{c}+\frac{5}{Q}+\frac{7}{R}=1 \Leftrightarrow aQR+5cR+7cQ=cQR \Leftrightarrow (QR-5R-7Q)c=aQR
このときacQR=\frac{9!}{1\cdot 5\cdot 7}=2^{7}\cdot 3^{4} \Leftrightarrow aQR=\frac{2^{7}\cdot 3^{4}}{c}なので
(QR-5R-7Q)c=\frac{2^{7} \cdot 3^{4}}{c} \Leftrightarrow QR-5R-7Q=\frac{2^{7} \cdot 3^{4}}{c^{2}}
　\Leftrightarrow (Q-5)(R-7)=\frac{2^{7} \cdot 3^{4}}{c^{2}}+35となる。cについて場合分けすると、
c=2 \rightarrow (Q-5)(R-7)=2^{5}\cdot 3^{4}+35=2627=37\cdot 71
　\Leftrightarrow (Q, R)=(42, 78), (76, 44), (6, 2634), (2632, 8)
c=3 \rightarrow (Q-5)(R-7)=2^{7}\cdot 3^{2}+35=1187 (素数)
　\Leftrightarrow (Q, R)=(6, 1194), (1192, 8)
c=4 \rightarrow (Q-5)(R-7)=2^{3}\cdot 3^{4}+35=683 (素数)
　\Leftrightarrow (Q, R)=(6, 690), (688, 8)
c=6 \rightarrow (Q-5)(R-7)=2^{5}\cdot 3^{2}+35=323=17\cdot19
　\Leftrightarrow (Q, R)=(22, 26), (24, 24), (6, 330), (328, 8)
c=8 \rightarrow (Q-5)(R-7)=2\cdot 3^{4}+35=197 (素数)
　\Leftrightarrow (Q, R)=(6, 204), (202, 8)
c=9 \rightarrow (Q-5)(R-7)=2^{7}+35=163 (素数)
　\Leftrightarrow (Q, R)=(6, 170), (168, 8)
となり、可能な組(Q, R)が存在しない。
よってb \neq 1である。対称性からc \neq 1なので、aの分母に1は入りません。
以上から、a=1となります。

分子がすべて決定されたので、bc=Pとすると、
QR+5RP+7PQ=PQRとなり、次のように3通りの変形ができる。
　QR=(QR-7Q-5R)P
　5RP=(RP-R-7P)Q
　7PQ=(PQ-5P-Q)R
以上の3式から、QRはPを、RPはQを、PQはRを約数に持つので、P, Q, Rのうち8を含むものは3または9を含み、6と9は同時には含まれない。
よって可能な組は\{P, Q, R\}=\{12, 24, 36\}, \{18, 24, 24\}, \{6, 24, 72\}, \{8, 18, 72\}, \{12, 12, 72\}
またQR=(QR-7Q-5R)P \Leftrightarrow \frac{QR}{P}=(Q-5)(R-7)-35で、
PQR=2^{7}\cdot3^{4} \Leftrightarrow \frac{QR}{P}=\frac{2^{7}\cdot3^{4}}{P^{2}}なので、
(Q-5)(R-7)=\frac{2^{7}\cdot3^{4}}{P^{2}}+35となる。Pについて場合分けすると、
P=6 \rightarrow (Q-5)(R-7)=2^{5}\cdot3^{2}+35=323=17 \cdot 19
　\Leftrightarrow (Q, R)=(22, 26), (24, 24), (6, 330), (328, 8)
P=8 \rightarrow (Q-5)(R-7)=2\cdot3^{4}+35=197 (素数)
　\Leftrightarrow (Q, R)=(6, 204), (202, 8)
P=12 \rightarrow (Q-5)(R-7)=2^{3}\cdot3^{2}+35=107 (素数)
　\Leftrightarrow (Q, R)=(6, 114), (112, 8)
P=18 \rightarrow (Q-5)(R-7)=2^{5}+35=67 (素数)
　\Leftrightarrow (Q, R)=(6, 74), (72, 8)
P=24 \rightarrow (Q-5)(R-7)=2\cdot3^{2}+35=53 (素数)
　\Leftrightarrow (Q, R)=(6, 60), (58, 8)
P=36 \rightarrow (Q-5)(R-7)=2^{3}+35=43 (素数)
　\Leftrightarrow (Q, R)=(6, 50), (48, 8)
P=72 \rightarrow (Q-5)(R-7)=2+35=37 (素数)
　\Leftrightarrow (Q, R)=(6, 44), (42, 8)
上記のうち可能な組(P, Q, R)は(18, 72, 8)のみで、このとき
\frac{1}{18}+\frac{5}{72}+\frac{7}{8}=1となる。
よって解は\frac{1}{3\cdot6}+\frac{5}{8\cdot9}+\frac{7}{2\cdot4}のみです。

(証明終わり)


基本的には場合分けを繰り返します。その場合分けはなるべく少なくなるように工夫し、最終的には31通りの場合分けで解けるようにしました。これを多いと感じるか少ないと感じるかは人それぞれだと思います。

まず5と7について、素数であることを使って分母に入らないことを示します。そのあとで1が分母に入らないことを示していきます。特殊な値が分母に入ると式の値がおかしくなりそうだという勘でこの順番に分類していきました。

最後は1の分母の数で場合分けをしておしまいです。


だいたいどこも素因数分解でとどめを刺していますが、そのときたくさん素数が出てくるのがポイントです。これを見つけたときは気持ちよかったです。

Pythonさんに導いてもらった答えと一致していることがわかります。論理的に答えが1つしか存在しないことが示されました。めでたしめでたし。


A. 分母を積じゃなくて和にしてしまった

SOx氏がツイッターに上げた問題をPythonさんに解いてもらったんですが、そのついでにぺるコン3問目も解いてみようと思って前述のことをしていました。「この機に」とはSOx氏の問題のことです。

そこで致命的なミスをしました。

上記の通り、積と和を取り違えてしまったのです。

これで計算してみたらなんと答えが3つも出てきてびっくり。答えが1つしかないことは証明したはずなのに……と思ったら、プログラムにミスを見つけることができて一安心。

怪我の功名から生まれた改題の答えは次の通りです。

pythonさんの解答 (その2)

これも一応確かめます。

1つ目：\frac{1}{2+4}+\frac{5}{7+8}+\frac{6}{3+9}=\frac{1}{6}+\frac{5}{15}+\frac{6}{12}=1
2つ目：\frac{2}{6+9}+\frac{3}{7+8}+\frac{4}{1+5}=\frac{2}{15}+\frac{3}{15}+\frac{4}{6}=1
3つ目：\frac{2}{7+8}+\frac{3}{6+9}+\frac{4}{1+5}=\frac{2}{15}+\frac{3}{15}+\frac{4}{6}=1

全部合ってます。答えはこの3通りらしいです。

こんな感じで、
まず方程式を作り
コンピュータに任せ
面白い結果が出たら問題にする

というアプローチで作問するのもいいかもなぁと思いました。これが今回のオチです。


おしまい。

Midyの定理とGinsbergによる拡張とpercentageによる別証明

しっかり数学

「散歩してたらこんなの見つけたんだけど」

東洋医学の講義の時間に同級生から教えてもらった問題にまつわる話です。



1. 神社の算学

三重県桑名市にある桑名宗社(春日神社)には以下のような算学があるそうです。

f:id:percentage011:20210131193648j:plain
桑名宗社ホームページより http://www.kuwanasousha.org/archives/1934

講義中に教えてもらったのは1番(循環小数に関する分割和)です。以下に再掲します。

\frac{1}{7}=0.\dot{1}4285\dot{7}
は循環小数で、循環する数字「142857」を循環節という。循環節142857の数字を2分割、3分割して加えると次のように9が並ぶ数になります。
142+857=999, 14+28+57=99
一般にpを素数とするとき\frac{1}{p}の循環節についても、2分割、3分割して加えると999\cdots9のように9が並ぶ数になります。

へえ～面白いな～。
ということで、とりあえず9が並ぶことを証明していきましょう。

2. 証明

p=2,5のとき循環しないのでp\neq2,5とする。

2分割の場合

循環節をM、その桁数を2m、Mの上半分をU_2(M)、下半分をL_2(M)とする。このとき\frac{10^{2m}}{p}-\frac{1}{p}=MなのでpM=10^{2m}-1となる。また、M=10^{m}U_2(M)+L_2(M)である。
循環節の上半分と下半分を足したものがほしいので、桁をずらしてMを足すと、
(10^{2m}+10^{m}+1)M=(10^{2m}+10^{m}+1)\{10^{m}U_2(M)+L_2(M)\}
=10^{3m}U_2(M)+10^{2m}\{U_2(M)+L_2(M)\}+10^{m}\{U_2(M)+L_2(M)\}+L_2(M)
=10^{m}(10^{m}+1)\{U_2(M)+L_2(M)\}+10^{3m}U_2(M)+L_2(M)
ここで、
10^{3m}U_2(M)+L_2(M)=10^{2m}\cdot10^{m}U_2(M)+L_2(M)+10^{2m}L_2(M)-10^{2m}L_2(M)
=10^{2m}\{10^{m}U_2(M)+L_2(M)\}-(10^{2m}-1)L_2(M)
=10^{2m}M-pML_2(M)なので、
(10^{2m}+10^{m}+1)M=10^{m}(10^{m}+1)\{U_2(M)+L_2(M)\}+10^{2m}M-pML_2(M)
\Leftrightarrow10^{m}(10^{m}+1)\{U_2(M)+L_2(M)\}=\{10^{2m}+10^{m}+1-10^{2m}+pL_2(M)\}M=\{10^{m}+1+pL_2(M)\}M
\Leftrightarrow(10^{m}+1)\{U_2(M)+L_2(M)\}=\{1+\frac{1+pL_2(M)}{10^{m}}\}Mとなる。
この中で
1+\frac{1+pL_2(M)}{10^{m}}-p=10^{-m}[10^{m}+1-\{10^{m}-L_2(M)\}p]
=10^{-m}[10^{m}+1-\{10^{m}-(M-10^{m}U_2(M))\}p]
=10^{-m}\{10^{m}+1-10^{m}p+(10^{2m}-1)-10^{m}pU_2(M)\}
=1-p+10^{m}-pU_2(M)
=(1+10^{m})-\{1+U_2(M)\}p
なので、1+10^{m}-\{1+U_2(M)\}p=cとおくと、
pU_2(M)=1+10^{m}-p-c
\Leftrightarrow U_2(M)=\frac{10^{m}+1}{p}-(1+\frac{c}{p})=\frac{(10^{m}+1)M}{pM}-(1+\frac{c}{p})
=\frac{10^{m}+1}{10^{2m}-1}M-(1+\frac{c}{p})=\frac{M}{10^{m}-1}-(1+\frac{c}{p})
\Leftrightarrow(10^{m}-1)U_2(M)=M-(10^{m}-1)(1+\frac{c}{p})=10^{m}U_2(M)+L_2(M)-(10^{m}-1)(1+\frac{c}{p})
\Leftrightarrow U_2(M)+L_2(M)=(10^{m}-1)(1+\frac{c}{p})
このとき左辺は整数なので、10^{m}-1とcの少なくとも一方はpの倍数である。もし10^{m}-1がpの倍数であれば10^{m}-1=pH (Hは整数)と書くことができ、M=\frac{10^{2m}-1}{p}=\frac{1}{p}(10^{m}-1)(10^{m}+1)=H(10^{m}+1)となるが、Mは2m桁なのでHはm桁の整数であり、その場合は\frac{1}{p}の循環節がm桁ということになり矛盾する。よってcがpの倍数である。
U_2(M)は\frac{1}{p}の最初の小数点以下m桁なので、U_2(M)は10^{-m}pU_2(M)\leq1を満たす最大の整数である。このとき明らかに10^{-m}\{1+U_2(M)\}p>1 \Leftrightarrow \{1+U_2(M)\}p>10^{m}なので、c=1+10^{m}-\{1+U_2(M)\}p\lt1となる。
またU_2(M)+L_2(M)>0, 10^{m}-1>0なので1+\frac{c}{p}>0 \Leftrightarrow c>-pである。cはpの倍数だったので、以上の条件からc=0。
これにより1+10^{m}-\{1+U_2(M)\}p=0, 1+\frac{1+pL_2(M)}{10^{m}}-p=0なので1+\frac{1+pL_2(M)}{10^{m}}=p。
よって(10^{m}+1)\{U_2(M)+L_2(M)\}=pM=10^{2m}-1 \Leftrightarrow U_2(M)+L_2(M)=10^{m}-1である。

3分割の場合

基本的な考え方は2分割のときと同じですが、もともと技巧的だった式変形が更に複雑になります。

循環節をM、その桁数を3m、Mの上3分の1をU_3(M)、真ん中3分の1をI_3(M)、下3分の1をL_3(M)とする。このとき\frac{10^{3m}}{p}-\frac{1}{p}=MなのでpM=10^{3m}-1となる。また、M=10^{2m}U_3(M)+10^{m}I_3(M)+L_2(M)である。
循環節の上3分の1と真ん中3分の1と下3分の1を足したものがほしいので、桁をずらしてMを足すと、
(10^{4m}+10^{3m}+10^{2m}+10^{m}+1)M=10^{6m}U_3(M)+10^{5m}\{U_3(M)+I_3(M)\}
+10^{4m}\{U_3(M)+I_3(M)+L_3(M)\}+10^{3m}\{U_3(M)+I_3(M)+L_3(M)\}
+10^{2m}\{U_3(M)+I_3(M)+L_3(M)\}+10^{m}\{I_3(M)+L_3(M)\}+L_3(M)
=10^{2m}(10^{2m}+10^{m}+1)\{U_3(M)+I_3(M)+L_3(M)\}
+10^{6m}U_3(M)+10^{5m}\{U_3(M)+I_3(M)\}+10^{m}\{I_3(M)+L_3(M)\}+L_3(M)
ここで、
10^{6m}U_3(M)+10^{5m}\{U_3(M)+I_3(M)\}+10^{m}\{I_3(M)+L_3(M)\}+L_3(M)
=10^{4m}\{10^{2m}U_3(M)+10^{m}I_3(M)\}+10^{5m}U_3(M)+\{10^{m}I_3(M)+L_3(M)\}+10^{m}L_3(M)
=10^{4m}\{M-L_3(M)\}+10^{5m}U_3(M)+\{M-10^{2m}U_3(M)\}+10^{m}L_3(M)
=(10^{4m}+1)M+(10^{4m}-10^{m})\{10^{m}U_3(M)-L_3(M)\}
=(10^{4m}+1)M+10^{m}pM\{10^{m}U_3(M)-L_3(M)\}
なので、
(10^{4m}+10^{3m}+10^{2m}+10^{m}+1)M
=10^{2m}(10^{2m}+10^{m}+1)\{U_3(M)+I_3(M)+L_3(M)\}+(10^{4m}+1)M+10^{m}pM\{10^{m}U_3(M)-L_3(M)\}
\Leftrightarrow 10^{2m}(10^{2m}+10^{m}+1)\{U_3(M)+I_3(M)+L_3(M)\}
=[10^{4m}+10^{3m}+10^{2m}+10^{m}+1-(10^{4m}+1)-10^{m}p\{10^{m}I_3(M)-L_3(M)\}]M
=10^{m}[10^{2m}+10^{m}+1-p\{10^{m}U_3(M)-L_3(M)\}]M
\Leftrightarrow(10^{2m}+10^{m}+1)\{U_3(M)+I_3(M)+L_3(M)\}=\{10^{m}+1+10^{-m}-pU_3(M)+10^{-m}pL_3(M)\}M
この中で、
10^{m}+1+10^{-m}-pU_3(M)+10^{-m}pL_3(M)-p=c
とすると、
\frac{10^{3m}-1}{10^{m}(10^{m}-1)}-p\{U_3(M)-10^{-m}L_3(M)+1\}=c
\Leftrightarrow pM-10^{m}(10^{m}-1)p\{U_3(M)-10^{-m}L_3(M)+1\}=10^{m}(10^{m}-1)c
\Leftrightarrow 10^{2m}U_3(M)+10^{m}I_3(M)+L_3(M)-10^{m}(10^{m}-1)\{U_3(M)-10^{-m}L_3(M)+1\}=10^{m}(10^{m}-1)\frac{c}{p}
\Leftrightarrow \{10^{2m}-10^{m}(10^{m}-1)\}U_3(M)+10^{m}I_3(M)+\{1+10^{m}(10^{m}-1)10^{-m}\}L_3(M)=10^{m}(10^{m}-1)(1+\frac{c}{p})
\Leftrightarrow \{U_3(M)+I_3(M)+L_3(M)\}=(10^{m}-1)(1+\frac{c}{p})
このとき左辺は整数なので、10^{m}-1とcの少なくとも一方はpの倍数である。もし10^{m}-1がpの倍数であれば10^{m}-1=pT (Tは整数)と書くことができ、M=\frac{10^{3m}-1}{p}=\frac{1}{p}(10^{m}-1)(10^{2m}+10^{m}+1)=T(10^{2m}+10^{m}+1)となるが、Mは3m桁なのでTはm桁の整数であり、その場合は\frac{1}{p}の循環節がm桁ということになり矛盾する。よってcがpの倍数である。
c=10^{m}+1+10^{-m}-p\{U_3(M)-10^{-m}L_3(M)+1\}
=10^{m}+1-p+10^{-m}\{1+pL_3(M)\}-pU_3(M)
\Leftrightarrow pU_3(M)=10^{m}+1-p+10^{-m}\{1+pL_3(M)\}-c
で、U_3(M)は\frac{1}{p}の最初の小数点以下m桁なので、U_3(M)は10^{-m}pU_3(M)\leq1 \Leftrightarrow pU_3(M)\leq10^{m}を満たす最大の整数である。このとき明らかに\{1+U_3(M)\}p>10^{m}なのでpU_3(M)> 10^{m}-pである。
よって
10^{m}-p \lt pU_3(M) \leq 10^{m}
\Leftrightarrow 10^{m}-p \lt 10^{m}+1-p+10^{-m}\{1+pL_3(M)\}-c \leq 10^{m}
\Leftrightarrow 1-p+10^{-m}\{1+pL_3(M)\} \leq c \lt 1+10^{-m}\{1+pL_3(M)\}で、
1-p+10^{-m}\{1+pL_3(M)\}> -pなので-p \lt cである。
また、pM=10^{3m}-1 \Leftrightarrow 10^{-3m}=1-10^{-3m}pM=1-p\{10^{-m}U_3(M)+10^{-2m}I_3(M)+10^{-3m}L_3(M)\}
\Leftrightarrow 10^{-3m}\{1+pL_3(M)\}=1-p\{10^{-m}U_3(M)+10^{-2m}I_3(M)\}で、
10^{m}U_3(M)+I_3(M)は\frac{1}{p}の最初の小数点以下2m桁なので、10^{m}U_3(M)+I_3(M)はp\{10^{-m}U_3(M)+10^{-2m}I_3(M)\} \leq1 \Leftrightarrow p\{10^{m}U_3(M)+I_3(M)\} \leq 10^{2m}を満たす最大の整数である。このとき明らかにp\{10^{m}U_3(M)+I_3(M)+1\}>10^{2m}で、左辺は整数なので、
p\{10^{m}U_3(M)+I_3(M)+1\} \geq 10^{2m}+1 \Leftrightarrow p\{10^{m}U_3(M)+I_3(M)\} \geq 10^{2m}+1-p
\Leftrightarrow \{10^{-m}U_3(M)+10^{-2m}I_3(M)\} \geq 1-10^{-2m}(p-1)
\Leftrightarrow 1-\{10^{-m}U_3(M)+10^{-2m}I_3(M)\} \leq 10^{-2m}(p-1)であり、
10^{-3m}\{1+pL_3(M)\}=1-\{10^{-m}U_3(M)+10^{-2m}I_3(M)\} \leq 10^{-2m}(p-1)
\Leftrightarrow 10^{-m}\{1+pL_3(M)\}=p-1なので、
c \lt 1+10^{-m}\{1+pL_3(M)\} \leq 1+(p-1)=p \Leftrightarrow c \lt pである。
cはpの倍数であったので、以上の条件からc=0となる。
よって10^{m}+1+10^{-m}-pU_3(M)+10^{-m}pL_3(M)=p
\Leftrightarrow (10^{2m}+10^{m}+1)\{U_3(M)+I_3(M)+L_3(M)\}=pM=10^{3m}-1
\Leftrightarrow U_3(M)+I_3(M)+L_3(M)=10^{m}-1である。

(証明終わり)


だいぶややこしい計算をしましたが、「循環節の各部分を足したものを作りたい」という簡単な発想を不自然な演算を定義せず自然な代数処理で実現し、小数の持つ自明な制限(小数展開の有限部分と割る数の積が1を超えないこと)を適宜使うことで、知識としては小学校の算数レベルで解決することができました。
アイデアが泥臭すぎた代償(？)として、非常にテクニカルな計算ルートをたどることになりました。上の証明ではあたかも最初からその道が見えていたかのように書かれていますが、実際には証明に4日かかっています……4日ならだいぶ早い方ですけどね。

3. 証明の新規性？

ところで、2分割したものを足して9が並ぶという性質はMidyの定理(Midy 1836)と呼ばれ、また3分割についてはGinsbergの論文(Ginsberg 2004)[1]で証明されたらしいです[2]。



！？！？



なんと、21世紀に証明されたばかりの定理を僕も証明できてしまったらしいです。しかもGinsberg 2004を見てみると、上の証明とは違う(とてもスマートな)やり方でした。

もしかしたら新規性のある別証明を作れているのかもしれないと思うとワクワクしますね。

A. 参考

[1] B. D. Ginsberg 2004, Midy’s (Nearly) Secret Theorem — An Extension After 165 Years, College Mathematics Journal, 35 (2004), 26-30.
[2] 循環小数の一性質 －Midy の定理とその一般化－/富山大学理学部 https://www.sci.u-toyama.ac.jp/topics/topics16.html

斜辺を共有するピタゴラス数たち

手作り数学

ピタゴラスの定理というものがあります。
これは直角三角形の辺の長さの関係についての定理で、具体的には次のような主張です。

ピタゴラスの定理 直角三角形について、aとbを直角を挟む2辺の長さ、cを斜辺の長さとすると、
a^2+b^2=c^2


非常にシンプルです。

直角三角形なら3辺の長さの比が常に上の関係式を満たすというのは自明ではなく、これまでプロアマ問わずたくさんの人がこの定理を調べてきました。
この関係式は全ての辺の長さが整数であるような直角三角形というとても特殊な図形の議論で登場することが多く、特にピタゴラスの定理を満たす3つの整数の組はピタゴラス数と呼ばれ、整数の話題として有名です。
この記事ではピタゴラス数について、斜辺に注目して調べた結果を書いていきます。
以下、ピタゴラス数はピタゴラスの定理を満たす3つの自然数の組とし、原則a,b,cの関係は上の通りとします。

注：著者は数学に対して厳密性を求め(られ)ない人なので、穏やかな気持ちで読んでください。



1. ピタゴラス数の諸性質

ピタゴラス数は自然数の2乗に関する定理なので、まずは自然数の2乗を観察してみます。

1^2=1, 2^2=4, 3^2=9, 4^2=16, 5^2=25, 6^2=36, 7^2=49, \dots


ふむ、よくわからんですね。
よくわからないので適切な"眼鏡"をかけてみます。

1^2≡1, 2^2≡0, 3^2≡1, 4^2≡0, 5^2≡1, 6^2≡0, 7^2≡1, \dots mod 4


規則性が表れました。4で割ったあまりを考えると、奇数の2乗は1、偶数の2乗は0になることがわかります(これは非常に簡単に示せます)。

さて、最初の定理において、aとbがともに奇数だったらどうなるでしょうか。
a^ 2≡1, b^ 2≡1なので、a^ 2+b^ 2≡2です。
ところで、a^ 2+b^ 2=c^ 2なので、当然c^ 2≡2となります。
しかしc^ 2も上の規則を満たすはずなので、c^ 2≡0 or 1でなければいけません。
矛盾しました。つまりaとbは同時に奇数になってはいけないのです。
このことから次の事実を得ます(確認してみてください)。

系 ピタゴラス数のうち斜辺以外の2辺の長さは
「奇数と偶数」か「偶数と偶数」でなければならない


余談ですが、系とは「既知の事実からただちに正しいとわかる主張」のことらしいです。

ここで、aとbがともに偶数である場合を考えると、偶数の2乗の和なので、当然c^ 2も偶数です。このときcも偶数になります。
つまり、aとbがともに偶数なら3辺とも偶数になるのです。
全部偶数ですね。つまり2で割ることができます。割れるものは割っておきたいですよね(NPCの家の壺とか)。

2に限らず、ピタゴラス数が互いに素でないとき、それらを最大公約数で割ってもピタゴラス数になります。それなら一番簡単な数の組が好ましいです。
そのような、互いに素であるピタゴラス数を原始ピタゴラス数と言います。定数倍の違いを除けば、全てのピタゴラス数はどれかの原始ピタゴラス数と同一視できるわけです。
このことによって、本質的には原始ピタゴラス数だけ考えれば良い場合が多いです(何を本質と見るかは考える対象によって違いますが)。

このように最大公約数で割って原始ピタゴラス数に変換すると、a,b,cのうち少なくとも1つは奇数になります(全て偶数なら2で割ることができるため)。そして上の議論からaとbが同時に偶数であればcも偶数になるため、aとbのどちらか一方は奇数になります。
更に系から、もう一方が偶数になることがわかります。
以上のことから、aとbは奇数と偶数のペアに限定され、よってcは奇数に決定されます。
つまり、原始ピタゴラス数のうち、aとbは奇数と偶数(どちらが奇数でどちらが偶数でも良い)、cは奇数であることが言えるのです。

他にも、ピタゴラス数を辺の長さとして持つ直角三角形の面積は偶数であるとか、少なくとも1つは5の倍数であるとか、ピタゴラス数については色々な事実が知られているらしいですが、今回の話には不要なので省きました。


2. 前準備

ここまででピタゴラス数一般に関する前提知識の確認は終わりで、次からは本題の証明に必要な話です。道具として使うだけなので理解する必要はありません(ぼくも理解していません)。おおらかにいきましょう。

4で割って1あまる自然数は、非負整数nを用いて4n+1と表せます。これはフェルマーの二平方和定理によって、2つの整数の2乗の和(二平方和)として表せることが保証されています。

フェルマーの二平方和定理 4n+1 (nは非負整数)は2つの整数\alphaと\betaによって
4n+1=\alpha^ 2+\beta^ 2
と表すことができる


この二平方和への分解は、複素数の世界で考えることで因数分解と見なせます。

ガウス整数による因数分解 \alpha^ 2+\beta^ 2=(\alpha+\betai)(\alpha-\betai)


右辺の複素数は実部も虚部も整数です。このような複素数をガウス整数、ガウス整数全体の集合(にたし算とかけ算をいい感じに定義したもの)をガウス整数環と言います。環はたし算とかけ算がいい感じになっている集合です。詳しくは触れません。
系の直前に書いたc^ 2≡0 or 1から、二平方和に分解できる、つまりガウス整数によって因数分解できる素数は4n+1型素数だけであることがわかります(2は例外で、2=(1+i)(1-i)のように因数分解できます)。この意味において、4n+3型素数のことをガウス素数と言います。ガウス整数環上でも素数であるからです。
ガウス整数環の特徴として、素因数分解が一通りしかないことがあります(一意分解整域)。フェルマーの二平方和定理と合わせて考えることで、4n+1型の自然数の二平方和分解が一通りしか存在しないことが言えます。

また、二平方和同士の積も二平方和になることが知られています。

ブラーマグプタの二平方恒等式 (w^ 2+x^ 2)(y^ 2+z^ 2)=(wy-xz)^ 2+(wz+xy)^ 2=(wy+xz)^ 2+(wz-xy)^ 2


これで本題の斜辺を共有するピタゴラス数たちを考える準備が整いました。


3. 斜辺を共有する複数のピタゴラス数

いよいよ本題に入ります。

斜辺を共有するピタゴラス数とは、ピタゴラスの定理を満たす自然数の組(a_1,b_1,c)と(a_2,b_2,c)で、a_1\neq a_2, b_1\neq b_2であるような組たちのことです。共有すると言うからには2つ以上あります。
そもそもそんな組があるのかどうか疑問かもしれませんが、実際に存在します。
例えば、65がそのような斜辺の例です。計算してみましょう。

16^ 2+63^ 2=256+3969=4225=65^ 2
25^ 2+60^ 2=625+3600=4225=65^ 2
33^ 2+56^ 2=1089+3136=4225=65^ 2
39^ 2+52^ 2=1521+2704=4225=65^ 2

確かに複数のピタゴラス数が斜辺として65を共有しています。
もう一例あげてみます。

716^ 2+32037^ 2=512656+1026369369=1026882025=32045^ 2
2277^ 2+31964^ 2=5184729+1021697296=1026882025=32045^ 2
6764^ 2+31323^ 2=45751696+981130329=1026882025=32045^ 2
8283^ 2+30956^ 2=68608089+958273936=1026882025=32045^ 2
15916^ 2+27813^ 2=253319056+773562969=1026882025=32045^ 2
17253^ 2+27004^ 2=297666009+729216016=1026882025=32045^ 2
21093^ 2+24124^ 2=444914649+581967376=1026882025=32045^ 2
22244^ 2+23067^ 2=494795536+532086489=1026882025=32045^ 2

目がチカチカしますね。
驚くべきことに、この8通りの分解は全て原始ピタゴラス数になっています。

ここで2つの疑問が生じます。
・cがどのような条件を満たせばc^ 2が複数通りの二平方和分解を持つのか？
・c^ 2は何通りの二平方和分解を持つのか？

これを調べるために、cを与えれば自動でピタゴラス数を網羅してくれるプログラムを書いて計算させてみました(上の計算は全てプログラムに投げました)。
すると、原始ピタゴラス数に限って言えば、二平方和分解の個数は2の非負整数乗っぽいぞ、ということが見えてきました。
この"2のべき乗"という構造は何に由来するのでしょうか？


4. 強い制限下での分解

c^ 2は4n+1型の自然数です。では、cはどうでしょうか？
cは奇数なので、4で割ったあまりは1 or 3です。このどちらの場合でも2乗すれば4n+1型になりますが、まずはc≡1の場合を考えます

フェルマーの二平方和定理により、4n+1型自然数は二平方和分解が可能です。素数は自然数に含まれるので、当然4n+1型素数も二平方和分解できます。
ここでブラーマグプタの二平方恒等式を思い出してください。二平方和の積は二平方和になるというアレです。
この恒等式によって、cが4n+1型素数の積であれば、二平方和分解可能であることが保証されます。
よって、ここではまずcの素因数が全て4n+1型素数であるという強い制限の下で斜辺を共有する原始ピタゴラス数の個数を考えていきます。

最初に、cの素因数が重複のない4n+1型素数のみである場合です。

cの素因数が重複のない4n+1型素数の場合の分解の個数

cのi番目の素因数をp_iとすると、\displaystyle{c=\prod_{i=1}^{N}p_i}となり、
\displaystyle{P(N-1)=\prod_{i=1}^{N-1}p_i}とおけばc=P(N-1)\times p_Nとなる。
p_N=\alpha^ 2+\beta^ 2、複数あるかもしれない分解のうちある一つをとってP(N-1)=A^ 2+B^ 2とすると、
c^ 2=(\alpha+\beta i)^ 2 (\alpha-\beta i)^ 2 (A+Bi)^ 2 (A-Bi)^ 2である。
(\alpha+\beta i)^ 2=r, (\alpha-\beta i)^ 2=\bar r, (A+Bi)^ 2=R, (A-Bi)^ 2=\bar Rとすると、ここでの目標はc^ 2を互いに素な自然数による二平方和に分解することなので、\sqrt rと\sqrt{\bar r}、\sqrt Rと\sqrt{\bar R}の積を作るのは避けたい(これをしてしまうと、せっかく分解したp_NやP(N-1)が再生してしまいます)。よって考えるべきはrR \times \bar r\bar Rとr\bar R\times\bar r Rの2つ。


1) rR\times \bar r\bar R
rR=\{(\alpha^ 2-\beta^ 2)+2\alpha\beta i\} \{(A^ 2-B^ 2)+2AB i\}
=\{(\alpha^ 2-\beta^ 2)(A^ 2-B^ 2)-4\alpha\beta AB\}+\{2\alpha\beta(A^ 2-B^ 2)+2AB(\alpha^ 2-\beta^ 2)\}i
\bar r\bar R=\{(\alpha^ 2-\beta^ 2)-2\alpha\beta i\}\{(A^ 2-B^ 2)-2AB i\}
=\{(\alpha^ 2-\beta^ 2)(A^ 2-B^ 2)-4\alpha\beta AB\}-\{2\alpha\beta(A^ 2-B^ 2)+2AB(\alpha^ 2-\beta^ 2)\}i
ここで\gamma_1=(\alpha^ 2-\beta^ 2)(A^ 2-B^ 2)-4\alpha\beta AB, \delta_1=2\{\alpha\beta(A^ 2-B^ 2)+AB(\alpha^ 2-\beta^ 2)\}とすると、
rR=\gamma_1+\delta_1i, \bar r\bar R=\gamma_1-\delta_1i なので、c^ 2=\gamma_1^ 2+\delta_1^ 2

2) r\bar R\times \bar r R
r\bar R=\{(\alpha^ 2-\beta^ 2)+2\alpha\beta i\}\{(A^ 2-B^ 2)-2AB i\}
=\{(\alpha^ 2-\beta^ 2)(A^ 2-B^ 2)+4\alpha\beta AB\}+\{2\alpha\beta(A^ 2-B^ 2)-2AB(\alpha^ 2-\beta^ 2)\}i
\bar r R=\{(\alpha^ 2-\beta^ 2)-2\alpha\beta i\}\{(A^ 2-B^ 2)+2AB i\}
=\{(\alpha^ 2-\beta^ 2)(A^ 2-B^ 2)+4\alpha\beta AB\}-\{2\alpha\beta(A^ 2-B^ 2)-2AB(\alpha^ 2-\beta^ 2)\}i
ここで\gamma_2=(\alpha^ 2-\beta^ 2)(A^ 2-B^ 2)+4\alpha\beta AB, \delta_2=2\{\alpha\beta(A^ 2-B^ 2)-AB(\alpha^ 2-\beta^ 2)\}とすると、
r\bar R=\gamma_2+\delta_2i, \bar r R=\gamma_2-\delta_2i なので、c^ 2=\gamma_2^ 2+\delta_2^ 2


上の2通りの変形が可能であるが、これらはいずれも(\gamma_1,\delta_1,c)や(\gamma_2,\delta_2,c)が原始ピタゴラス数であるための必要条件でしかないので、次にこれらが十分条件であることを示す。
\gamma_1, \delta_1はそれぞれ
\gamma_1=(\alpha^ 2+\beta^ 2)(A^ 2+B^ 2)-2(\alpha B+A\beta)^ 2=p_N P(N-1)-2(\alpha B+A\beta)^ 2,
\delta_1=2(\alpha A-\beta B)(\alpha B+A\beta)と変形できる。
\gamma_1とcが互いに素でないと仮定すると、p_N P(N-1)=cなので\alpha B+A\betaもcと互いに素でない。このとき\alpha B+A\betaはcの素因数の倍数なので、その素因数をp_j、mを整数として
\alpha B+A\beta=m p_jとなる。また、\alpha A-\beta B=Mとすると、 \gamma_1^ 2+\delta_1^ 2=\{p_N P(N-1)-2(m p_j)^ 2\}{}^ 2+4M^ 2 (m p_j)^ 2
={p_N}^ 2 {P(N-1)}^ 2-4m^ 2 p_j^ 2 p_N P(N-1)+4m^ 4 p_j^ 4+4M^ 2 m^ 2 p_j^ 2=c^ 2={p_N}^ 2 {P(N-1)}^ 2
\Leftrightarrow M^ 2=p_N P(N-1)-m^ 2 {p_j}^ 2
p_N P(N-1)はp_jの倍数であってかつ{p_j}^ 2の倍数でないので、p_N P(N-1)=K p_j(K\perp p_j)とすることができる。このときMもp_jの倍数のはずなので、M=\mu p_jとできる。
\mu^ 2 {p_j}^ 2=K p_j-m^ 2 {p_j}^ 2
\Leftrightarrow K=(\mu^ 2+m^ 2)p_j
これはK\perp p_jに矛盾する。
よって\alpha B+A\betaとp_jが互いに素なので、\gamma_1とcも互いに素である。
ところで、\delta_1^ 2=c^ 2-\gamma_1^ 2であるが、右辺はp_jの倍数でないので、\delta_1もp_jの倍数でない。
また、\gamma_1と\delta_1の最大公約数をdとすると、\gamma_1^ 2+\delta_1^ 2=c^ 2はd^ 2の倍数になるのでcはdの倍数になるが、cは素因数としてp_jしかもたず、これがdの約数になることは、d=1の場合を除いて\gamma_1\perp cに矛盾する。
よってd=1。これは(\gamma_1, \delta_1, c)が互いに素であることを意味する。
同様の議論により(\gamma_2, \delta_2, c)も互いに素である。

以上のことから、cの分解の個数をD(c)とするとD(c)=2D(P(N-1))なので、P(N-1)以降に上記の議論を繰り返し適用することで、
D(c)=2D(P(N-1))=2^ 2 D(P(N-2))=\cdots=2^{N-1}D(P(1)))=2^{N-1}
よってcの素因数がN個の重複のない4n+1型素数の場合、その二平方和分解は少なくとも2^ {N-1}個あることがわかる。

(証明終わり)


これで、斜辺を共有するピタゴラス数の個数について一定の評価ができました。

見どころ(？)は\gamma_1と\delta_1から共通の構造である\alpha B+A\betaを取り出したところですね。
式変形は上手くやれば上手くいくのです。

さて、証明の最後の部分で分解の個数について触れましたが、少なくともと控えめな主張になっていますね。
これは2のべき乗構造を生み出す根幹の部分に理由があります。
証明の中で、cをガウス整数の範囲でr, \bar r, R, \bar Rの4つの因数に分解しましたが、それらの再構成の方法は、なんとブラーマグプタの二平方恒等式に従っています。
上の証明で行った再構成がブラーマグプタの二平方恒等式によることは、以下の式変形(というより文字で置き換えることによるエイリアス)を見ることで様子がはっきりします。

s=\alpha^ 2-\beta^ 2, t=2\alpha\beta, S=A^ 2-B^ 2, T=2ABとすると、
{p_k}^ 2=(\alpha^ 2+\beta^ 2)^ 2=s^ 2+t^ 2, P^ 2=(A^ 2+B^ 2)^ 2=S^ 2+T^ 2なので、
c^ 2={p_k}^ 2 P^ 2=(s^ 2+t^ 2)(S^ 2+T^ 2)
これは二平方和の積なので、ブラーマグプタの二平方恒等式によって次のような2通りの二平方和に分解できる。
1. (sS-tT)^ 2+(sT+St)^ 2
2. (sS+tT)^ 2+(sT-St)^ 2

上の証明の中に出てくる\gamma_1, \delta_1, \gamma_2, \delta_2は全てこの形をしています。確認してみてください。

確かにこれで2通りの分解はできていますが、果たしてこれ以外の分解・再構成は存在しないのでしょうか？
ここにおいて、cの分解と再構成の方法がガウス整数の範囲での因数分解とブラーマグプタの二平方恒等式によるもの以外に存在しないことを証明していないので、少なくともという弱い主張に留まっているのです。

実は、他の分解・再構成の方法があるかないかは、著者にはまだわかっていません。
上で触れた自動でピタゴラス数を網羅してくれるプログラムを100回ほど回した限りでは、強い制限下における分解の個数は全て2のべき乗(2^ 0=1を含む)でした。なので楽観的に、上記以外の方法はないだろうと予想しています。

次に、cの素因数である4n+1型素数の指数が1以外も許される場合、つまり素因数に重複がある場合です。

cの素因数が重複のある4n+1型素数の場合の分解の個数

p_iをcのi番目の素因数、その指数をs_iとすると、

\displaystyle{c=\prod_{i=1}^{N}p_i^ {s_i}}

となる。

\displaystyle{P=\prod_{i\neq k}^{N}p_i^ {s_i}}

とすると、c={p_k}^ {s_k} Pとなる。
p_k=\alpha^ 2+\beta^ 2、P=A^ 2+B^ 2とすると、
c^ 2=(\alpha+\beta i)^ {2s_k} (\alpha-\beta i)^ {2s_k} (A+Bi)^ 2 (A-Bi)^ 2である。
(\alpha+\beta i)^ 2=r, (\alpha-\beta i)^ 2=\bar r, (A+Bi)^ 2=R, (A-Bi)^ 2=\bar Rとすると、ここでの目標はc^ 2を互いに素な自然数による二平方和に分解することなので、やはり\sqrt rと\sqrt{\bar r}、\sqrt Rと\sqrt{\bar R}の積を作るのは避けたい。
そのためには、rと\bar rを分離しなければならず、それを実現できるのはr^ {s_k} R\times ({\bar r})^ {s_k} \bar Rとr^ {s_k} \bar R\times ({\bar r})^ {s_k} Rの2通りしかない。
これは重複のない場合と同じなので、分解の個数も同じになる。
つまり、cの素因数である4n+1型素数にどのような重複があっても、分解の個数は素因数の指数s_kによらないことがわかった。

(証明終わり)


cを構成する素因数が4n+1型素数のみであれば、その重複に関係無く、素因数の種類の数のみによって分解の個数が決まるということです。指数の変動に対して安定であると言えます。

今までは原始ピタゴラス数(原始解と呼ぶことにします)にしか注目してきませんでしたが、非原始解の個数は指数が大きいほど増えていくようです。非原始解の個数を表す式はまだありません。読者への演習問題としても良いかもしれませんね。


5. 素因数の拡張

前節で、cの素因数が4n+1型素数のみである場合を考えました。4n+3型素数は二平方和に分解できないガウス素数で、扱いにくいからです。
例えば、cが4n+3型素数の場合、cはピタゴラス数になりません。

cが4n+3型素数でないことの証明

cを4n+3型素数とする。
a^ 2+b^ 2=c^ 2が成り立つと仮定すると、
b^ 2=c^ 2-a^ 2=(c-a)(c+a)となる。3つの自然数\alpha, \beta,g(ただし\alphaと\betaは互いに素)によってb=\alpha\beta gとすると、
b^ 2=\alpha^ 2 \beta^ 2 g^ 2=\alpha^ 2 g \times \beta^ 2 gなので、c-a=\alpha^ 2 g, c+a=\beta^ 2 gとしても良い(符号をこのように設定しても一般性を失わない)。
※ここでgはc-aとc+aの最大公約数を意識しています。
すると、a=c-\alpha^ 2 g=\beta^ 2 g-cなので、c=\frac{g}{2}(\alpha^ 2+\beta^ 2)となる。
l,m,Nを整数として、\alphaと\betaの偶奇について考えると、
1) \alpha=2lかつ\beta=2mのとき:
　\alpha\perp\betaに反するので矛盾。
2) \alpha=2lかつ\beta=2m-1のとき:
　c=\frac{g}{2}(4l^ 2+4m^ 2-4m+1)=\frac{g}{2}(4N+1)と表すことができ、4N+1が奇数、cが素数であることからg=2。
　そのとき4n+3=4N+1となるので矛盾。
　\alpha=2l-1かつ\beta=2mのときも同様に矛盾する。
3) \alpha=2l-1かつ\beta=2m-1のとき:
　c=\frac{g}{2}(4l^ 2-4l+1+4m^ 2-4m+1)=g(2l^ 2-2l+2m^ 2-2m+1)
　　=g\{2l(l-1)+2m(m-1)+1\}で、連続する2整数の積は偶数になるので、
　c=g(4l'+4m'+1)=g(4N+1)と表すことができ、4N+1が奇数、cが素数であることからg=1。
　そのとき4n+3=4N+1となるので矛盾。
以上の3パターン全てで矛盾するので、cは4n+3型素数ではない。

(証明終わり)


上の結果は、たとえc^ 2が4n+1型整数であってもcが4n+3型素数であれば二平方和分解ができないことを主張しています。これはフェルマーの二平方和定理に矛盾しているように見えますが、\alpha=0と\beta=cの場合があるので矛盾していません。上の証明ではa,bを自然数に限定しているので、0が使えなくなっているのです(今更ですが自然数に0を含めないことにしています)。

上の結果を使うと、cの素因数に4n+3型素数が含まれる場合、cは原始解を持たないことがわかります。

p_iを4n+1型素数、s_iをp_iの指数、q_iを4n+3型素数、t_iをq_iの指数として、cを

\displaystyle{c=(\prod_{i=1}^{N}p_i^ {s_i})(\prod_{i=1}^{M}q_i^ {t_i})}

とします。
これまでと同様に個々の素数を二平方和に分解してからブラーマグプタの二平方恒等式に従って再構成しようとすると、{q_i}^ {t_i}が二平方和に分解できないので、c^ 2=\gamma^ 2+\delta^ 2のように分解してから係数のようにかけるしかなく、これだと(\gamma,\delta,c)が互いに素にならないので、原始解を作ることができません。
この場合でも非原始解は存在しますが、N個の4n+1型素数によって作られた2^ {N-1}個の分解に4n+3型素数を全てかけた形のものしか得られないため、分解の個数は変わりません。

また当然ですが、二平方和を4で割ったあまりは0か1なので、cがこのどちらでもない場合はピタゴラス数を構成しません。


6. まとめ

以上の結果をまとめると、次のようになります。

\displaystyle{c=(\prod_{i=1}^{N}p_i^ {s_i})(\prod_{i=1}^{M}q_i^ {t_i})}

について、
1) t_i=0の場合:
　1つのcに対して原始ピタゴラス数は少なくとも2^ {N-1}個存在する
　非原始解を含めるともっとたくさん存在すると予想される
2) s_i=0の場合:
　ピタゴラス数にならない
3) t_iが非負偶数のとき:
　原始解を持たないが、非原始解を少なくとも2^ {N-1}個持つ

斜辺を共有するピタゴラス数の個数が(もし分解・再構成の方法が他に無ければ)2のべき乗という非常に特殊な値を取るのは面白いと思いました。


A. おまけ/ピタゴラス数の和差が成すピタゴラス数たち

上の議論を考えているときに訪れた寄り道的な話題を紹介します。

cが複数通りの二平方和に分解されるとき、ブラーマグプタの二平方恒等式とエイリアスによって、次のように整理されます。

c=pP(ただしp,Pは4n+1型の自然数)のとき、p=\alpha^ 2+\beta^ 2, P=A^ 2+B^ 2と表すことができる。
ここでs=\alpha^ 2-\beta^ 2, t=2\alpha\beta, S=A^ 2-B^ 2, T=2ABとすると、
c^ 2=(sS-tT)^ 2+(sT+St)^ 2=(sS+tT)^ 2+(sT-St)^ 2となる。
s, Sが奇数、t, Tが偶数なので、sS-tT, sS+tTは奇数、sT+St, sT-Stは偶数となる。

ここで新たに
(sS-tT)+(sS-tT)=2sS=\sigma_1、(sT+St)+(sT-St)=2sT=\tau_1、
(sS-tT)-(sS-tT)=2tT=\sigma_2、(sT+St)-(sT-St)=2St=\tau_2、
つまりcと共に原始解を構成する2数のうち偶奇を揃えて足したり引いたりした数を考えると、
\sigma_1^ 2+\tau_1^ 2=4s^ 2S^ 2+4s^ 2T^ 2
=4s^ 2(S^ 2+T^ 2)=4s^ 2\{(A^ 2-B^ 2)^ 2+4A^ 2B^ 2\}
=4s^ 2(A^ 2+B^ 2)^ 2=(2sP)^ 2
\sigma_2^ 2+\tau_2^ 2=4t^ 2T^ 2+4S^ 2t^ 2
=4t^ 2(S^ 2+T^ 2)=4t^ 2\{(A^ 2-B^ 2)^ 2+4A^ 2B^ 2\}
=4t^ 2(A^ 2+B^ 2)^ 2=(2tP)^ 2
となり、これらもピタゴラス数になります。どちらも原始ピタゴラス数のP倍なので、Pで割ることができます。
それらのうちPで割って奇数になるもの同士、Pで割って偶数になるもの同士の和や差を考えると、これまたピタゴラス数になっています。
以下、この操作をどこまで続けても、生成される数は全てピタゴラス数です。





追記(2022/02/06)
続きを書きました。こちらもどうぞ↓↓↓

percentage011.hatenablog.com







参考資料

ガウス整数 - Wikipedia
ブラーマグプタの二平方恒等式 - Wikipedia
一意分解環 - Wikipedia

手作業で円周率を求めよう

手作り数学

円周率を求める方法は無数にあります。
多角形で挟んで範囲を狭める古典的な方法は中学校とかで聞いたかもしれません。ラマヌジャンとかいうインド人が立てた狂気の式の中にも円周率を計算するものがありますが、円周率あたりは沼なので深く立ち入らないことにします。調べればいくらでも謎の級数による導出があるので、それらの難しい話は偉大なGoogle先生に任せ、この記事では頭ではなく手を動かして円周率を求めていきます。前提知識は小学校の算数程度、使う道具は鉛筆、定規、コンパスとすごく大きな紙です。

そもそも円周率とはなんなのか

まずは円周率が何かを確認しておきます。
円周率とは円の周長と直径の比です。
なので、何も難しいことを考えなくても、これら2つの長さがわかれば良いのです。この記事で紹介する方法もこれら2つの長さを測定して円周率を求めていきます。

測定可能なモデルを作る

最も正確な方法は真円の直径と円周長を測ることですが、真円の円周長を測ることは非常に難しいです。それができたら苦労はしません。真の値を知るのは無理なので、近似値を求めます。
何で円を近似しようか……と考えると、やはり多角形がまっさきに思いつきました。素直にこれを使います。
さて、古典的な多角形による円周率の近似の難しさは、図形の精密さに尽きると思います。コンパスで描いた円に対して多角形の角を増やせば、どんどん辺は短くなり、ある段階で一定水準以上の精度の測定が不可能になるからです。
ここで、円周率の定義を思い出してください。円周率とは円の周長と直径の比です。2つの値の比なので、円周率を測定する方法としては、既知の直径に対して周長を測定するというのと、既知の周長に対して直径を測定するという2つのアプローチがあります。上の方法は前者を採用した結果精度の問題で詰んでいるので、今回は後者を採用します。
そうすると何が良いかというと、辺を短くしなくて済むのです。ですがこれはトレードオフになっていて、今度は多角形の構成が難しくなります。
やることは長さ既知の辺によってなるべく正確に正多角形を作り、なるべく正確にその直径に相当する対角線の長さを測定するというシンプルなものですが、ここで2つの問題が生じます。
1つ目は、正多角形をどうやって正確に構成するか、つまり隣り合う辺の成す角の精度をどう保証するかです。これはコンパスによる角の2等分線の作図によって解決します。しかも、角の2等分線の作図において基準となる長さを十分大きくすれば、コンパスの操作による誤差や引かれた線の太さによる誤差も小さくすることができます。
ただしこの解決法によって作図できる正多角形が正2n角形に限定されますが、関心は円周率にあるので、別に問題にはなりません。
2つ目は、直径の測定による誤差です。1つ目の問題の解決法によって正2n角形を利用することになったので、直径相当の対角線は容易に特定できますが、その長さの測定には古典的な方法と同様に精度の限界が存在します。どうすれば良いでしょうか？
実は、今回はそもそもこれが問題になっていないのです。角を増やせばそれだけ直径も大きくなりますが、定規による測定誤差の大きさは変わらないので、正2n角形が円に近づくほど測定誤差を無視できるようになるのです。素晴らしいですね。

この方法の妥当性

前述の方法で円周率を近似できそうだというのは直感的にはわかりますが、一応証明しておきます。ここだけ高校数学レベルですが結果的には正しいので飛ばしても良いです。

証明

1辺が2の正n角形をP_nとする。P_nを角を底角としてn分割した図形を考えると、それは底辺の長さが2で頂角の大きさが\frac{2\pi}{n}の二等辺三角形である。底辺ではない辺の長さをLとすると、
1=L\sin{\frac{\pi}{n}}なので
\displaystyle{L=\frac{1}{\sin{\frac{\pi}{n}}}=\frac{n}{\pi}\frac{\frac{\pi}{n}}{\sin{\frac{\pi}{n}}}}となる。よって

\displaystyle{\lim_{n \to \infty}\frac{L}{n}}

\displaystyle{=\lim_{n \to \infty}\frac{1}{\pi}\frac{\frac{\pi}{n}}{\sin{\frac{\pi}{n}}}=\frac{1}{\pi}}

(証明終わり)
ということで、確かに円周率(の逆数)が求められました。ただし直径をnで割っています。これは1次元の長さがn1に比例することを補正するための処理です。

手を動かそう

さてこれで準備は整いました。以下の手順で円周率を求めていきます。
1. 1辺の長さが2cmの正8角形を作図する
2. 角の2等分線の作図によって正8角形と1つの辺を共有する正16角形を作図する
3. 2の手順を繰り返すことで正2n角形を作図する
4. 正n角形の対角線の長さを測る
5. 周長(=2n)を対角線の長さで割る
6. 円周率の近似値！嬉しい！！！

実際にやってみた

以下のようになりました。
n=8のとき：\pi\approx16\div4.83=3.31262\dots
n=16のとき：\pi\approx32\div9.6=3.33333\dots
n=32のとき：\pi\approx64\div20.25=3.16049\dots
n=64のとき：\pi\approx128\div40.55=3.15659\dots
かなり面倒だった割には、この程度の近似ではあまり良い精度では得られませんでした。しかし特別な道具、精密な作業、難しい考え方なしに近似値を求められることに嬉しさを感じました。

連続するΣをΠでまとめる

手作り数学

たし算とかけ算の間には

\displaystyle{+++\cdots+=\times}

という関係がありますが(伝われ)、実はこれが \sum と \prod にも言えそうなのです。つまり

\displaystyle{\sum\sum\sum\cdots\sum=\prod}

も言えそう、という感じ。
これは自分で作った問題を解く過程で発見したもので、先に予想が立ってから証明しました。必要は発明の母とはよく言ったものですね。



まずは結果から

結果から言うと、こうなります。

定理1 \displaystyle{\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_1=1}^{a_2}1=\frac{1}{(n-1)!}\prod_{i=1}^{n-1}({a_n}+i-1)}


ゴツい。

等号の左右で見比べてみると、n-1個あった \sum がたった1個の \prod にまとまっています。嬉しいです。
これが成り立つことを示します。そう、みんな大好き証明タイムです。



補題ってかっこいい

定理1を示すにあたり、以下の補題を考えます。


\sum が消えています。あとでこれを繰り返し使うことで \sum をまとめていくので、これが本質的な部分です。
以下の補題の証明は昔どこかのサイトで見たもののほぼそのままです。どこだったか覚えがなくてリンクを貼れないこと、引用元を明示できないことが残念ですが、必要なので使わせていただきます。どなたか心当たりがある方は教えていただけるとありがたいです。

証明

\displaystyle{f_r(j)=\prod_{i=1}^{r}(j+i-1)}

とおくと

\displaystyle{f_r(j)=\frac{(j+r)-(j-1)}{r+1}\prod_{i=1}^{r}(j+i-1)\\ =\frac{1}{r+1}(\prod_{i=1}^{r+1}(j+i-1)-\prod_{i=0}^{r}(j+i-1))\\ =\frac{1}{r+1}(f_{r+1}(j)-f_{r+1}(j-1))}

なので

\displaystyle{\sum_{j=1}^{J}f_r(j)=\sum_{j=1}^{J}\frac{1}{r+1}(f_{r+1}(j)-f_{r+1}(j-1))\\ =\frac{1}{r+1}(f_{r+1}(J)-f_{r+1}(0))}

となる。ところで

f_{r+1}(0)=0

なので

\displaystyle{\sum_{j=1}^{J}f_r(j)=\frac{1}{r+1}f_{r+1}(J)}

元の記号に戻すことで

\displaystyle{\sum_{j=1}^{J}\prod_{i=1}^{r}(j+i-1)=\frac{1}{r+1}\prod_{i=1}^{r+1}(J+i-1)}

が得られた。

(証明終わり)




定理1の証明

続いて定理1の証明です。めちゃくちゃゴツいです。

証明

\displaystyle{\sum_{a_1=1}^{a_2}1=a_2=\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}

なので

\displaystyle{\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_1=1}^{a_2}1}
\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_2=1}^{a_3}\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}

ここで補題で示した恒等式を使うと

\displaystyle{\sum_{a_2=1}^{a_3}\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}
\displaystyle{=\frac{1}{1!}\sum_{a_2=1}^{a_3}\prod_{i=1}^{1}(a_2+i-1)}
\displaystyle{=\frac{1}{1!}\frac{1}{1+1}\prod_{i=1}^{2}(a_3+i-1)}
\displaystyle{=\frac{1}{2!}\prod_{i=1}^{2}(a_3+i-1)}

これを繰り返し適用することで

\displaystyle{\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_2=1}^{a_3}\frac{1}{1!}\prod_{i=1}^{1}(a_2+i-1)}
\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_3=1}^{a_4}\frac{1}{2!}\prod_{i=1}^{2}(a_3+i-1)}
\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_u=1}^{a_{u+1}}\frac{1}{(u-1)!}\prod_{i=1}^{u-1}(a_u+i-1)}
\displaystyle{=\sum_{a_{n-1}=1}^{a_n}\frac{1}{(n-2)!}\prod_{i=1}^{n-2}(a_{n-1}+i-1)}
\displaystyle{=\frac{1}{(n-2)!}\sum_{a_{n-1}=1}^{a_n}\prod_{i=1}^{n-2}(a_{n-1}+i-1)}
\displaystyle{=\frac{1}{(n-1)!}\prod_{i=1}^{n-1}({a_n}+i-1)}
(証明終わり)



ここまででタイトルの連続するΣをΠでまとめるはできました。

このままでも＋と\timesとの関係として十分面白いのですが、よく見ると一番右の\sumは1をたしています。これではつまらないので、実用性を与えるために定理1を拡張します。





どんな数列でも足せる

定理1では1を足していました。定理1を拡張した定理2では任意の数列を足せるようにします。

定理2 任意の数列\{A_n\}に対して
\displaystyle{S_A(a_n)=\sum_{a_{n-1}=1}^{a_n}\sum_{a_{n-2}=1}^{a_{n-1}}\sum_{a_{n-3}=1}^{a_{n-2}}\cdots\sum_{a_1=1}^{a_2}A_{a_1}}
とすると
\displaystyle{S_A(a_n)=\sum_{a_{n-1}=1}^{a_n}{}_{a_n-a_{n-1}+n-2}C_{n-2}A_{a_{n-1}}}



\prodがありませんが、内部では\sumがまとめられています。なので証明の中で定理1の証明で使った補題を再利用します。
紛らわしいですが、数列\{A_n\}と添字数列\{a_n\}は全く関係のないものであることに注意してください。
また、\{a_n\}を形式的に数列ということにしましたが、これは定理の形の都合でa_nから自然に定義されるもので、自動的にa_{k-1}\leq a_kとなります。Σが並んでいるので、区別のために添字数列のようにまとめて扱いましたが、本来的に数列である必要性はありません。
よって、形式的な入れ替えが可能です。

定理2の証明

帰納法で示す。

ステップ1　n=2 のとき

\displaystyle{S_A(a_2)=\sum_{a_1=1}^{a_2}A_{a_1}=\sum_{a_1=1}^{a_2}{}_{a_2-a_1+2-2}C_{2-2}A_{a_1}}

ステップ2　n=k のとき成り立つと仮定

するとn=k+1のとき

\displaystyle{S_A(a_{k+1})=\sum_{a_k=1}^{a_{k+1}}S_A(a_k)\\=\sum_{a_k=1}^{a_{k+1}}\sum_{a_{k-1}=1}^{a_k}{}_{a_k-a_{k-1}+k-2}C_{k-2}A_{a_{k-1}}}
Aの添字であるa_{k-1}を固定して足す順番を変えると、定義からa_k \geq a_{k-1}なので、
\displaystyle{\sum_{a_{k-1}=1}^{a_{k+1}}\sum_{a_k=a_{k-1}}^{a_{k+1}}{}_{a_k-a_{k-1}+k-2}C_{k-2}A_{a_{k-1}}}
a_{k-1}とa_{k}を形式的に入れ替えることで、
\displaystyle{\sum_{a_k=1}^{a_{k+1}}\sum_{a_{k-1}=a_k}^{a_{k+1}}{}_{a_{k-1}-a_k+k-2}C_{k-2}A_{a_k}}
\displaystyle{=\sum_{a_k=1}^{a_{k+1}}\sum_{a'_{k-1}=1}^{a_{k+1}-a_k+1}{}_{a'_{k-1}-1+k-2}C_{k-2}A_{a_k}}
このとき、入れ替えによってa_k \leq a_{k-1}となります。 ここでa_{k-1}'=a_{k-1}-a_k+1のように置き換えているので、a'_{k-1}\geq 1となりますが、自然とその条件を満たしていることがわかります。

式変形を続けると、

\displaystyle{=\sum_{a_k=1}^{a_{k+1}}\sum_{a'_{k-1}=1}^{a_{k+1}-a_k+1}\frac{(a'_{k-1}-1+k-2)!}{(a'_{k-1}-1)!(k-2)!}A_{a_k}}
\displaystyle{=\sum_{a_k=1}^{a_{k+1}}A_{a_k}\sum_{a'_{k-1} =1}^{a_{k+1}-a_k+1}\frac{1}{(k-2)!}\prod_{i=1}^{k-2}(a'_{k-1} +i-1)}

ここで補題を適用すると

\displaystyle{\sum_{a_k=1}^{a_{k+1}}A_{a_k}\sum_{a'_{k-1} =1}^{a_{k+1}-a_k+1}\frac{1}{(k-2)!}\prod_{i=1}^{k-2}(a'_{k-1} +i-1)}
\displaystyle{=\sum_{a_k=1}^{a_{k+1}}A_{a_k}\frac{1}{(k-1)!}\prod_{i=1}^{k-1}(a_{k+1}-a_k+i)}
\displaystyle{=\sum_{a_k=1}^{a_{k+1}}\frac{(a_{k+1}-a_k+k-1)!}{(a_{k+1}-a_k)!(k-1)!}A_{a_k}}
\displaystyle{=\sum_{a_k=1}^{a_{k+1}}{}_{a_{k+1}-a_k+k-1}C_{k-1}A_{a_k}}
(証明終わり)


これで定理1の拡張版である定理2が得られました。任意の数列を好きなだけ足し上げることができます。

ステップ2で足す順番を変えるところは、具体的に表を書いてみるとわかりやすいです。あとは技術的な問題なので、式をいじくり回すだけです。




実際に使ってみる

せっかくなので、フィボナッチ数列を例に定理2を使ってみます。

\{A_n\}=1,1,2,3,\cdots 、a_4=5 、とすると


愚直に足す

\displaystyle{\sum_{a_3=1}^{5}\sum_{a_2=1}^{a_3}\sum_{a_1=1}^{a_2}A_{a_1}}
=A_1
+\{A_1+(A_1+A_2)\}
+\{A_1+(A_1+A_2)+(A_1+A_2+A_3)\}
+\{A_1+(A_1+A_2)+(A_1+A_2+A_3)+(A_1+A_2+A_3+A_4)\}
+\{A_1+(A_1+A_2)+(A_1+A_2+A_3)+(A_1+A_2+A_3+A_4)+(A_1+A_2+A_3+A_4+A_5)\}
=1+3+7+14+26=51



定理2を使う

\displaystyle{S_A(a_4=5)=\sum_{a_3=1}^{5}{}_{5-a_3+4-2}C_{4-2}A_{a_3}}
={}_{6}C_{2}A_1+{}_{5}C_{2}A_2+{}_{4}C_{2}A_3+{}_{3}C_{2}A_4+{}_{2}C_{2}A_5
=15+10+12+9+5
=51



一致しました。定理2を使った方がずっと楽に計算できました。素晴らしいです。

追記(2019/12/01)
先日大学で友達と一緒にお昼を食べていたら、
「特定のfor文のネストを線形時間で解けるようになる高速化アルゴリズムなんじゃない？」
という話が上がりました。
使う場面がどれだけあるかはさておいて、確かにm重ループの計算がO(Nm)からO(N)に削減できている気がします。
なかなか良い結果が得られたなぁとニヤニヤを深めました。