2024年9月22日日曜日

OpenAI o1(4)

OpenAI o1(3)からの続き

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

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

アプローチ
1.素数の列挙:各 $n$ に対して,$n!$ の素因数分解に必要な素数を列挙します。
2.指数の計算:各素数 $p$ について,$n!$ 中の $p$ の指数 $e_p$ を計算します。
これは,$\lfloor \dfrac{n}{p} \rfloor + \lfloor \dfrac{n}{p^2} \rfloor +\lfloor \dfrac{n}{p^3} \rfloor +\cdots $で求められます・
3.組み合わせの計算:各素数 $p$ に対して,$\binom{n+e_p-1}{e_p}$を計算します。これにいおり,$e_p$ 個の指数を $k_i$ に分配する方法の数が求まります。
4.総数の計算:すべての素数についての組み合わせの数を掛け合わせることで、総数 $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だとより簡潔に表現できる。これは,もとの関数を2つ与えた上で,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)

0 件のコメント:

コメントを投稿