Namaran

Code daily. Without assist.

2026-10-17

lut_count.rs

fn functions(k: u32) -> u64 {
    2u64.pow(2).pow(k)
}

fn main() {
    for k in 1..=4 {
        println!("{k}: {}", functions(k));
    }
}

0 か 1 の値を k 個受け取って 0 か 1 を返す関数を、k 変数のブール関数(Boolean function)といいます。入力の組は 2^k 通りあり、そのそれぞれに 0 か 1 を割り当てる方法の数だけ関数があるので、個数は 2^(2^k) です(^ は累乗)。functions(k) はこの個数を返すつもりの関数で、入力は main の k = 1 から 4 です。いまは 1: 4、2: 16、3: 64、4: 256 の4行が出ます。本来の出力は 1: 4、2: 16、3: 256、4: 65536 です。

Answer

Wrong

2u64.pow(2).pow(k)

メソッド呼び出しは左から順に評価されるので、この式は 2u64.pow(2) の 4 を先に作り、それを k 乗します。計算しているのは (2^2)^k = 4^k で、数学の 2^2^k が表す 2^(2^k) ではありません。4^k は 2^(2k) なので、2k と 2^k が等しい k = 1 と 2 では正しい値と一致し、k = 3 から小さすぎる値になります。

Right

2u64.pow(2u32.pow(k))

指数の 2^k を先に計算して、それを pow の引数に渡します。pow の指数は u32 なので、指数側は 2u32.pow(k) で作ります。右側の累乗を括弧の内側に置く形にすると、累乗の右結合がそのままコードの入れ子になります。k = 6 では 2^64 になって u64 に収まらず、デバッグビルドではオーバーフローの panic で止まります。