素数ものさし (その6)
素数ものさし (その2) で 1cm 単位で 62cm まで測れる素数ものさしを見つけた．調べた限りではこれが最長の素数ものさしだった．
今回は，62cm より長い素数ものさしが存在しないことの証明を示す．
リンク
62cm の「素数ものさし」が最長であることの証明
i 番目の素数を pi で表す．すなわち p1 = 2, p2 = 3, p3 = 5, ... である． 3 以上の素数はすべて奇数である．また 5 以上の素数を 6 で割った余りは 1 か 5 になることに注意する．したがって 5 以上の素数は 6 m - 1 または 6 m + 1 のどちらかで表せる (m は 1 以上の整数)．
素数だけを目盛にしているものさし(単位は cm とする)が， 1cm からものさしの全長 L cm までのすべての長さを 1cm 単位で測れる時，そのものさしを「素数ものさし」と呼ぶことにする．以下では，素数ものさしの最適性(余分な目盛を含んでいるかどうか)については考慮せず，全長以下のすべての素数を目盛として含んでいる素数ものさしを対象とする．すなわち L 以下のすべての素数 p1, ..., pn が目盛として含まれている場合だけを考える．
この素数ものさしが測れる長さは，全長である L cm を除くと以下の3通りに場合分けできる．
- (測り方1) i 番目の目盛と j 番目の目盛 (i < j とする)の間のpj - pi cm
- (測り方2) 0cm の端と i 番目の目盛の間の pi cm
- (測り方3) L cm の端と i 番目の目盛の間の L - pi cm
では 62cm より長い素数ものさしが存在しないことの証明に進む．
最初に L - 1 が素数でなければならないことに注意する．なぜなら L - 1 cm を測ろうとした場合， 1cm の場所に目盛がないため，L - 1 cm の場所に目盛が必要となる．すなわち L = pn + 1 でなければならない．したがって，素数ものさしの全長 L を 6 で割った余りは， 0 または 2 である．
そこで L = 6m の場合と L = 6m + 2 の場合に分けて考える(m は1以上の整数)．
- L = 6m の場合．L が 42cm 以上の時，33cm を測れないことを示す．
まず (測り方1) では 33cm を測れない．(測り方1) で奇数の長さを測るには pi = 2 でなければならないが， 35 が素数でないため 33cm を測れない．次に (測り方2) でも 33 が素数でないため 33cm を測れない．最後に (測り方3) でも 33cm を測れない．なぜなら L - pi が測る長さ 33 に一致しなければならないが，これより pi = L - 33 = 6m - 33 となり，pi が 3で割り切れて素数とならない．したがって，どの測り方でも 33cm を測ることはできない． - L = 6m + 2 の場合．L が 128cm 以上の時，119cm を測れないことを示す．
まず (測り方1) では 119cm を測れない．(測り方1) で奇数の長さを測るには pi = 2 でなければならないが， 121 は 11で割りきれて素数でないため 119cm を測れない．次に (測り方2) でも 119 が 7で割りきれて素数ではないため測れない．最後に (測り方3) でも 119cm を測れない．なぜなら L - pi が測る長さ 119 に一致しなければならないが，これより pi = L - 119 = 6m - 117 となり， 3で割り切れて素数とならない．したがって，どの測り方でも 119cm を測ることはできない．
以上から，素数ものさしが存在すれば 128cm 未満であることが示された．また 素数ものさし (その2) で 128cm 未満のすべての素数ものさしを探した所，その中で 62cm が最長であることがわかっている．したがって 62cm より長い素数ものさしは存在しない．
