OpenAI o1（４）

OpenAI o1（３）からの続き

引き続き，o1 のプログラミング能力について検証してみよう。数学体感教室2024の問題3を一般化したものについて，o1-mini に Julia プログラムを作成させた。1回目は関数定義が重複するエラーが出ていたので，そのエラーコードを読ませると，2回目には正しい答えが得られた。

Ｑ（koshix）：

$a_i \ (i=1 ... n) $が正の整数であり，$n$個の$a_i$の組 $(a_1, a_2,  ..., a_n)$ 最大公約数は1であるとする。

$a_1/a_2=k_1,\  2*a_2/a_3=k_2, \ 3*a_3/a_4=k_3,\  ... (n-1)*a_{n-1}/a_n \\ =k_{n-1},  n*a_n/a_1 = k_n $において，$(k_1, k_2, ... k_n)$ は整数となって，$k_1*k_2*k_3*...*k_{n-1}*k_n = n!$ が成り立つ。

$n$を与えたときに，上記の条件を満足する$(k_1, k_2, ..., k_n)$ の組の数 $b_n$ を求める Julia プログラムを作成せよ。

このプログラムを用いて，$ b_1, b_2, ..., b_8$ の値を計算せよ。

Ａ（OpenAI o1-mini 思考時間29秒）：

以下に、与えられた条件を満たす $(k_1, k_2, ..., k_n)$の組の数 $b_n$ を計算する Julia プログラムを示します。このプログラムは、各 $n$に対して $n!$ の素因数分解を行い、各素数の指数を用いて組み合わせの数を計算します。

アプローチ

１．素数の列挙：各 $n$ に対して，$n!$ の素因数分解に必要な素数を列挙します。

２．指数の計算：各素数 $p$ について，$n!$ 中の $p$ の指数 $e_p$ を計算します。

これは，$\lfloor \dfrac{n}{p} \rfloor + \lfloor \dfrac{n}{p^2} \rfloor +\lfloor \dfrac{n}{p^3} \rfloor +\cdots $で求められます・

３．組み合わせの計算：各素数 $p$ に対して，$\binom{n+e_p-1}{e_p}$を計算します。これにいおり，$e_p$ 個の指数を $k_i$ に分配する方法の数が求まります。

４．総数の計算：すべての素数についての組み合わせの数を掛け合わせることで、総数 $b_n$ を得ます。

Julia プログラム（修正版）

以下のJuliaプログラムは、上記のアプローチに基づいて $b_n$ を計算します。

# Primes.jl パッケージのインポート

import Primes: primes

# n! における素数 p の指数を計算する関数

function exponent_in_factorial(n::Int, p::Int)::Int

    exponent = 0

    power = p

    while power <= n

        exponent += div(n, power)

        power *= p

    end

    return exponent

end

# b_n を計算する関数

function calculate_b(n::Int)::Int

    if n == 0

        return 1

    end

    

    # n >= 2 の場合のみ素数を取得

    if n >= 2

        primes_list = Primes.primes(2, n)

    else

        primes_list = Int[]  # 空の配列

    end

    

    total = 1

    for p in primes_list

        e_p = exponent_in_factorial(n, p)

        # 組み合わせの計算

        total *= binomial(n + e_p - 1, e_p)

    end

    return total

end

# b_1 から b_8 までを計算して表示

for n in 1:8

    bn = calculate_b(n)

    println("b_$n = $bn")

end

プログラムの説明

・exponent_in_factorial 関数：与えられた $n$ と素数 $p$ に対して，$n!$ の中の $p$ の指数を計算します。

・calculate_b 関数：与えられた $n$ に対して，$b_n$ を計算します。まず，$n$ 以下の素数を取得し、各素数についての組み合わせの数を計算して掛け合わせます。

・メインループ： $n=1$ から $n=8$ までの $b_n$ を計算し，結果を表示します。

実行結果

上記のプログラムを実行すると、以下のように $b_1$ から $b_8$ までの値が得られます。

$b_1 = 1$

$b_2 = 2$

$b_3 = 9$

$b_4 = 80$

$b_5 = 875$

$b_6 = 15876$

$b_7 = 288120$

$b_8 = 7907328$

これにより、各 $n$ に対して条件を満たす $(k_1, k_2, ..., k_n)$ の組の数 $b_n$ を効率的に計算することができます。

このプログラムは，Mathematicaだとより簡潔に表現できる。これは，もとの関数を２つ与えた上で，ChatGPT-4oに作ってもらった。エラーが出ていたが，3回目の修正で正しい答えに到達した。

f[n_] := FactorInteger[n!]

g[n_, k_] := Binomial[n + k - 1, k]

h[n_] := 

 Module[{factors = f[n], product = 1}, 

  Do[product *= g[n, pair[[2]]], {pair, factors}];

  product]

a = Table[h[k], {k, 1, 8}]

ListPlot[Log[a]] 

{1, 2, 9, 80, 875, 15876, 288120, 7907328} 

図：n=1-8 に対するh[n] の対数のListPlot（Mathematica）