1からnまでの整数を円形に並べると、最小値に「1/4」が現れる？――円環最大公約数コストの予想

はじめに

$1,2,\ldots,n$ を円形に並べる。ただし、隣り合う整数だけでなく、2つ先の整数ともなるべく共通の約数を持たないようにする。
この単純な組合せ最適化問題を考えたところ、最小値に興味深い規則性が現れた。
特に、最小値の下界は一般の $n$ について証明できる。一方、その下界をすべての $n$ で達成できるかどうかは、まだ証明できていない。
本記事では、この問題を「四分の一障壁予想」と仮称し、定式化、証明、数値検証の結果を紹介する。
なお、これは2026年10月15日に生成AIの補助を用いて考案・検討した個人的な予想である。先行研究を網羅的に調査したわけではなく、既知の定理から導ける可能性も残っている。「数学界で未解決と認定されている」という主張ではないことをあらかじめ断っておく。

1. 問題の定義

整数 $n\ge3$ とし、$1,2,\ldots,n$ を重複なく円形に並べる。その並びを
$$ \pi=(a_1,a_2,\ldots,a_n) $$
とする。円形なので添字は巡回的に扱い、
$$ a_{n+1}=a_1,\qquad a_{n+2}=a_2 $$
と定める。

ここで $\gcd(a,b)$ は $a$ と $b$ の最大公約数、$\mathfrak S_n$ は $1,\ldots,n$ の順列全体である。
2つの整数が互いに素であれば、その最大公約数は1となる。したがって、すべてのコスト項は1以上であり、
$$ M_n\ge n $$
が直ちに分かる。
しかし、偶数同士など共通の約数を持つ整数が一定数存在するため、実際の最小値は一般に $n$ より大きくなる。問題は、こうした整数同士の衝突を円周上でどこまで避けられるかということである。

2. 具体例：8個の整数を並べる

まず $n=8$ を考える。次の順番で円形に並べてみる。
$$ \pi=(1,2,4,3,5,8,6,7) $$
各位置について、隣と2つ先の整数との最大公約数の積を計算すると
$$ (1,2,1,1,1,2,1,1) $$
となる。したがって
$$ S(\pi)=10 $$
である。これは10という値を達成する並びが存在することを意味するので、$M_8\le10$ が分かる。
ところが、後述する下界の定理を使うと $M_8\ge10$ も示せる。よって
$$ \boxed{M_8=10} $$
であり、上記の配置は最適解である。

3. 四分の一障壁予想

小さな $n$ に対して同様の計算を進めると、最小コストの増分に規則性が見えてくる。

ここで $\lceil x\rceil$ は切り上げ、$\lfloor x\rfloor$ は切り捨てである。この予想が正しければ
$$ \lim_{n\to\infty}\frac{M_n}{n}=\frac54 $$
が従う。つまり、整数の数を無限に増やしても、最適な円形配置における1要素当たりの平均コストは最終的に $1.25$ に近づくということである。
なぜ最小値に4分の1が現れるのだろうか。次の節では、その原因の一部を証明する。

4. 最小値の下界は証明できる

実は、予想の右辺が必ず下界になることは、偶数の配置間隔を考えることで証明できる。

4.1 下界が予想値と一致することの確認

$n=2m$ が偶数の場合、
$$ \begin{aligned} M_n &\ge n+\left\lceil\frac{3m-2m}{2}\right\rceil\\ &=n+\left\lceil\frac n4\right\rceil \end{aligned} $$
となる。一方、$n=2m+1$ が奇数の場合、
$$ \begin{aligned} M_n &\ge n+\left\lceil\frac{3m-(2m+1)}{2}\right\rceil\\ &=n+\left\lfloor\frac{n-1}{4}\right\rfloor \end{aligned} $$
となる。つまり、四分の一障壁予想の右辺はすべての $n$ に対して厳密な下界である。
残されているのは、この下界が必ず達成可能かどうかという問題である。

5. 数値検証：$n=3$ から $36$ まで

$3\le n\le36$ の各整数について、実際に下界を達成する順列を発見し、Pythonによって再検算した。結果は以下のとおりである。

ここで注意したいのは、単に探索プログラムがこれらを最小値として報告したわけではないという点である。各 $n$ について、次の2つを確認している。

1. 第4節の定理から、予想値より小さくならないことが証明されている。
2. 実際に予想値を達成する具体的な順列が存在する。
   これらを組み合わせることで、$3\le n\le36$ の範囲については最小値が厳密に確定する。
   例えば $n=20$ では
   $$ \begin{aligned} \pi=(&20,14,9,17,10,12,11,7,18,16,\\ &5,3,2,8,15,1,4,6,13,19) \end{aligned} $$
   が $S(\pi)=25$ を達成する。同様に $n=36$ でも $M_{36}=45$ を達成する順列が存在する。具体的な順列データと検算プログラムは付録に掲載する。
   ただし、有限個の検証によって任意の自然数に対する主張が証明されるわけではない。

6. 本当の難しさは「達成する配置」の構成にある

下界の証明では、偶数の個数と配置間隔しか利用していない。しかし、実際に下界を達成するためには、より複雑な整数の約数構造を考える必要がある。
例えば、偶数の衝突を最小限に抑えられたとしても、3の倍数同士が近接すれば最大公約数が3以上になる可能性がある。同様に、5の倍数や7の倍数についても考慮が必要である。
さらに、本問題では最大公約数を加算するのではなく、2つの最大公約数を掛け合わせている。そのため、同一の位置で複数の共通因子が生じるとコストが大きくなりやすい。
偶数によって定まる不可避のコストだけを発生させ、それ以外の余分なコストを完全に回避できるか。これが予想の核心である。

7. 今後の研究課題

7.1 一般の $n$ での成立

最も重要なのは、
$$ M_n=n+\left\lceil\frac{3\lfloor n/2\rfloor-n}{2}\right\rceil $$
がすべての $n\ge3$ で成立することを証明するか、反例を発見することである。特に、一般の $n$ に対する具体的な順列の構成法が見つかれば、直接的な証明につながる可能性がある。

7.2 最適配置の構成アルゴリズム

下界を達成する配置を多項式時間で構成できるだろうか。最適値の公式が分かることと、実際に最適な並びを効率良く見つけられることは別の問題であり、計算量の観点からも研究の余地がある。

7.3 距離 $r$ への一般化

本記事では、隣と2つ先の整数を評価した。そこで $2\le r< n$ に対して
$$ S_r(\pi)=\sum_{i=1}^{n}\prod_{j=1}^{r}\gcd(a_i,a_{i+j}) $$
を考える（添字は巡回的に解釈する）。このとき
$$ M_{n,r}=\min_{\pi\in\mathfrak S_n}S_r(\pi) $$
はどのような挙動を示すだろうか。元の問題は $r=2$ に相当する。$r$ を固定して $n$ を無限に大きくしたとき、
$$ \lim_{n\to\infty}\frac{M_{n,r}}{n} $$
は存在するのだろうか。存在するとすれば、その値を決定できるだろうか。

8. まとめ

本記事では、円形に配置した整数について、隣および2つ先との最大公約数の積を最小化する問題を考えた。得られた結果は次のとおりである。

• 任意の $n\ge3$ に対する最小コストの下界を証明した。
• $3\le n\le36$ の34ケースで、下界を達成する具体的な配置を確認した。
• 下界がすべての $n$ で達成されるという「四分の一障壁予想」を提示した。
• 一般的な構成アルゴリズムと距離 $r$ への拡張を研究課題として挙げた。
  予想が正しければ、最適配置の平均コストは漸近的に $5/4$ に収束する。
  小さな計算結果と単純な下界の証明から生まれた予想だが、その背後には整数の約数構造と組合せ最適化の問題が存在している。既存の定理との関連、一般の構成法、反例などについて、ご存知の方がいればぜひご指摘いただきたい。

付録：Pythonによる検証コード

以下に、$3\le n\le36$ において下界を達成する配置データと、その検証プログラムを示す。Python 3の標準ライブラリのみを使用しており、外部ライブラリのインストールは不要である。
コードは次の処理を行う。

1. 各 $n$ に対応する順列が $1,\ldots,n$ を重複なく含むことを確認する。
2. 円環最大公約数コスト $S(\pi)$ を直接計算する。
3. 証明済みの下界を計算する。
4. 両者が一致することを確認する。
   このコード自体は一般の場合の予想を証明するものではない。各 $n$ に対する具体的な順列が下界を達成することを検算するためのものである。

      from math import gcd
# 各 n について、下界を達成する円形配置
witnesses = {
    3: [1, 2, 3],
    4: [1, 2, 4, 3],
    5: [1, 2, 3, 4, 5],
    6: [1, 2, 3, 5, 4, 6],
    7: [1, 2, 3, 5, 4, 6, 7],
    8: [1, 2, 4, 3, 5, 8, 6, 7],
    9: [1, 2, 3, 5, 4, 6, 7, 8, 9],
    10: [1, 2, 3, 4, 10, 9, 7, 8, 6, 5],
    11: [1, 2, 3, 5, 4, 6, 7, 11, 8, 10, 9],
    12: [1, 6, 4, 11, 9, 10, 8, 3, 7, 2, 12, 5],
    13: [1, 13, 10, 3, 8, 2, 9, 5, 4, 6, 7, 11, 12],
    14: [3, 11, 8, 2, 1, 12, 7, 5, 6, 14, 13, 9, 4, 10],
    15: [3, 8, 13, 9, 14, 2, 15, 1, 4, 6, 5, 7, 12, 10, 11],
    16: [6, 5, 13, 12, 10, 11, 9, 4, 2, 1, 3, 14, 16, 15, 7, 8],
    17: [7, 16, 6, 13, 1, 12, 14, 5, 3, 8, 11, 9, 10, 4, 17, 2, 15],
    18: [12, 1, 5, 18, 8, 13, 15, 16, 7, 6, 10, 17, 9, 14, 4, 3, 11, 2],
    19: [7, 9, 2, 8, 15, 17, 4, 6, 11, 1, 10, 3, 19, 14, 12, 13, 5, 18, 16],
    20: [20, 14, 9, 17, 10, 12, 11, 7, 18, 16, 5, 3, 2, 8, 15, 1, 4, 6, 13, 19],
    21: [19, 21, 2, 16, 3, 11, 20, 6, 1, 14, 12, 5, 7, 18, 4, 13, 15, 8, 17, 9, 10],
    22: [11, 5, 18, 4, 1, 15, 14, 8, 19, 9, 16, 2, 3, 10, 22, 21, 17, 20, 6, 13, 7, 12],
    23: [16, 5, 13, 12, 2, 17, 15, 14, 8, 9, 7, 4, 3, 19, 10, 18, 11, 1, 6, 20, 23, 21, 22],
    24: [19, 9, 14, 16, 15, 23, 22, 24, 7, 13, 12, 10, 1, 3, 20, 2, 21, 17, 8, 6, 5, 11, 18, 4],
    25: [4, 19, 14, 24, 5, 7, 12, 2, 17, 15, 22, 13, 21, 8, 10, 9, 23, 20, 6, 11, 25, 18, 16, 1, 3],
    26: [26, 7, 11, 12, 2, 25, 21, 16, 10, 19, 9, 20, 14, 3, 23, 22, 24, 13, 17, 18, 4, 5, 6, 8, 1, 15],
    27: [17, 24, 26, 23, 21, 8, 22, 9, 13, 4, 15, 11, 16, 6, 25, 1, 18, 10, 7, 27, 20, 14, 3, 19, 2, 12, 5],
    28: [23, 17, 18, 8, 19, 15, 14, 16, 27, 13, 10, 28, 3, 11, 2, 24, 25, 1, 6, 4, 5, 21, 26, 20, 9, 7, 22, 12],
    29: [26, 21, 23, 20, 11, 27, 10, 8, 3, 25, 2, 24, 7, 1, 12, 22, 13, 15, 4, 14, 9, 19, 16, 18, 29, 5, 6, 28, 17],
    30: [1, 15, 22, 28, 3, 17, 16, 27, 5, 14, 12, 29, 13, 6, 20, 11, 21, 10, 4, 9, 19, 8, 30, 23, 26, 18, 7, 25, 24, 2],
    31: [7, 24, 10, 19, 9, 20, 26, 21, 11, 4, 6, 31, 25, 8, 18, 13, 29, 30, 2, 1, 15, 22, 16, 3, 17, 28, 27, 5, 14, 12, 23],
    32: [19, 24, 14, 17, 15, 4, 2, 21, 25, 26, 16, 3, 7, 32, 30, 31, 23, 28, 18, 5, 29, 6, 20, 11, 9, 8, 10, 27, 13, 22, 12, 1],
    33: [5, 28, 18, 11, 25, 6, 22, 1, 3, 32, 23, 33, 14, 20, 9, 19, 10, 12, 31, 2, 24, 13, 29, 30, 8, 7, 15, 4, 26, 21, 17, 16, 27],
    34: [12, 7, 5, 24, 22, 25, 9, 26, 10, 3, 17, 28, 2, 33, 1, 8, 6, 13, 31, 30, 16, 23, 18, 20, 11, 27, 14, 32, 15, 19, 4, 21, 29, 34],
    35: [35, 26, 6, 17, 1, 30, 16, 19, 3, 8, 14, 9, 25, 28, 18, 31, 7, 34, 24, 5, 11, 12, 10, 23, 21, 20, 22, 13, 15, 4, 29, 27, 32, 2, 33],
    36: [30, 28, 29, 9, 8, 14, 15, 11, 26, 12, 1, 35, 24, 2, 25, 3, 16, 22, 21, 17, 10, 36, 23, 5, 18, 4, 19, 27, 32, 34, 33, 7, 20, 6, 31, 13],
}
def score(a):
    """円環最大公約数コストを計算する。"""
    n = len(a)
    assert sorted(a) == list(range(1, n + 1))
    return sum(
        gcd(a[i], a[(i + 1) % n]) * gcd(a[i], a[(i + 2) % n])
        for i in range(n)
    )
def lower_bound(n):
    """証明済みの下界を計算する。"""
    e = n // 2
    return n + (3 * e - n + 1) // 2
# 3から36まで全ケースの配置があることを確認
assert set(witnesses) == set(range(3, 37))
# 各配置が下界を達成することを確認
for n in sorted(witnesses):
    a = witnesses[n]
    value = score(a)
    bound = lower_bound(n)
    assert value == bound, (n, value, bound)
    print(f"n={n:2d}, M_n={value}")
print("All 34 cases verified.")
    

すべての検査に成功すれば、最後に次のように出力される。

      n=34, M_n=43
n=35, M_n=43
n=36, M_n=45
All 34 cases verified.
    

本コードに含まれる順列は、計算結果を第三者が追試するための具体的な証拠（witness）である。将来、さらに大きな $n$ の成立例や反例が発見された場合も、同じ評価関数を使って確認できる。

参考情報

• Project Euler Problem 886 "Coprime Permutations"：隣接する整数が互いに素となる順列を数える問題。
• The Square of a Hamiltonian Cycle：グラフにおける距離2までの隣接関係を扱う研究。
  これらは問題の考え方に関連する参考情報であり、今回の最適化問題の新規性を保証するものではない。

本記事の問題設定、予想の形成、計算検証および文章の整理には生成AIを利用した。下界の証明と有限範囲の計算結果については検証を行っているが、一般の場合の証明と十分な先行研究調査は未完了である。