基於四底對數的整數級數求和

***此篇文章由 Gemini AI 產生*** ### **問題定義** 我們的目標是計算一個特定總和 `S`，這個總和是由一個函數 `f(i) = ⌊log₄(i)⌋ + 1` 對所有從 1 到 `4^p - 1` 的整數 `i` 的值累加而成。其數學表達式為： $$S_p = \sum_{i=1}^{4^p-1} \left( \lfloor \log_4(i) \rfloor + 1 \right)$$ 這裡的 `p` 是一個正整數。 --- ### **公式推導** 直接計算這個總和很困難，關鍵在於觀察函數 `f(i)` 的特性。`f(i)` 的值在一系列連續的整數區間內是恆定的，這些區間由 4 的次方所界定。 #### **步驟一：級數的轉換** 1. **分析函數值**： * 對於任何落在區間 $[4^k, 4^{k+1} - 1]$ 內的整數 `i`，`log₄(i)` 的值會介於 `k` 與 `k+1` 之間 (即 `k ≤ log₄(i) < k+1`)。 * 因此，`⌊log₄(i)⌋` 的值恆為 `k`。 * 所以，對於這個區間內的所有 `i`，函數 `f(i)` 的值恆為 `k+1`。 2. **計算區間內的整數數量**： * 在區間 $[4^k, 4^{k+1} - 1]$ 中，整數的數量為： $$(4^{k+1} - 1) - 4^k + 1 = 4^{k+1} - 4^k = 4^k(4-1) = 3 \cdot 4^k$$ 3. **重寫總和表達式**： * 我們的總和 $S_p$ 是加總到 $4^p - 1$，這恰好涵蓋了從 `k=0` 到 `k=p-1` 的所有完整區間。 * 因此，我們可以將原本對 `i` 的求和，轉化為對 `k` 的分組求和： $$S_p = \sum_{k=0}^{p-1} (\text{區間內函數的值}) \times (\text{區間內的整數數量})$$ $$S_p = \sum_{k=0}^{p-1} (k+1) \cdot (3 \cdot 4^k)$$ #### **步驟二：求解等比等差數列** 我們可以將常數 3 提出，得到一個**等比等差數列**的和： $$S_p = 3 \cdot \sum_{k=0}^{p-1} (k+1) \cdot 4^k$$ 令核心部分為 `A`： $$A = \sum_{k=0}^{p-1} (k+1) \cdot 4^k = 1 \cdot 4^0 + 2 \cdot 4^1 + 3 \cdot 4^2 + \dots + p \cdot 4^{p-1}$$ 我們使用**錯位相減法**來求解 `A`。首先將 `A` 乘以級數的公比 4： $$4A = 1 \cdot 4^1 + 2 \cdot 4^2 + \dots + (p-1) \cdot 4^{p-1} + p \cdot 4^p$$ 接著，將 `A` 減去 `4A`： $$-3A = (1 \cdot 4^0 + 2 \cdot 4^1 + \dots + p \cdot 4^{p-1}) - (1 \cdot 4^1 + 2 \cdot 4^2 + \dots + p \cdot 4^p)$$ 合併同類項後，算式變為： $$-3A = 1 \cdot 4^0 + (2-1) \cdot 4^1 + (3-2) \cdot 4^2 + \dots + (p - (p-1)) \cdot 4^{p-1} - p \cdot 4^p$$ 這可以簡化為一個等比級數與一個單項： $$-3A = (4^0 + 4^1 + 4^2 + \dots + 4^{p-1}) - p \cdot 4^p$$ 括號中的部分是一個首項為 1，公比為 4，共有 `p` 項的等比數列。其和為 $\frac{4^p - 1}{4 - 1} = \frac{4^p - 1}{3}$。代入上式： $$-3A = \frac{4^p - 1}{3} - p \cdot 4^p$$ 為了求解 `A`，我們繼續整理。兩邊同乘以 -1： $$3A = p \cdot 4^p - \frac{4^p - 1}{3}$$ 通分整理後： $$3A = \frac{3p \cdot 4^p - (4^p - 1)}{3}$$ 最終得到： $$3A = \frac{(3p - 1) \cdot 4^p + 1}{3}$$ --- ### **最終公式** 我們最初的目標是 $S_p = 3 \cdot A$。將 `A` 的結果代入，即可得到該總和的封閉形式解（closed-form solution）： $$S_p = \frac{(3p - 1) \cdot 4^p + 1}{3}$$ 這個公式允許我們直接代入 `p` 來獲得最終結果，而無需進行迭代求和。 --- ### **範例驗證 (p=2)** 現在我們設定 `p = 2` 來驗證公式的準確性。我們要計算從 `i = 1` 到 `4² - 1 = 15` 的總和： $$S_2 = \sum_{i=1}^{15} \left( \lfloor \log_4(i) \rfloor + 1 \right)$$ #### **方法一：直接套用公式** 將 `p = 2` 代入我們推導出的公式，逐步計算： $$S_2 = \frac{(3 \cdot 2 - 1) \cdot 4^2 + 1}{3}$$ $$S_2 = \frac{(6 - 1) \cdot 16 + 1}{3}$$ $$S_2 = \frac{5 \cdot 16 + 1}{3}$$ $$S_2 = \frac{80 + 1}{3}$$ $$S_2 = \frac{81}{3} = 27$$ 公式計算出的結果是 **27**。 #### **方法二：分組逐項計算** 我們也可以將 1 到 15 的數字分組來計算實際總和： 1. **第一組 (k=0):** 當 `i` 在區間 `[1, 3]` * 包含的數字：1, 2, 3 (共 3 個) * 對於這些數字，`⌊log₄(i)⌋ + 1` 的值皆為 `0 + 1 = 1`。 * 此組的總和為： 3 個數字 × 1 = 3 2. **第二組 (k=1):** 當 `i` 在區間 `[4, 15]` * 包含的數字：4, 5, ..., 15 (共 `15 - 4 + 1 = 12` 個) * 對於這些數字，`⌊log₄(i)⌋ + 1` 的值皆為 `1 + 1 = 2`。 * 此組的總和為： 12 個數字 × 2 = 24 **總和** = 第一組總和 + 第二組總和 = `3 + 24 = 27`。 兩種方法得到的結果 **27** 完全相同。