โปรแกรมหาผลรวมกำลังสามของ N จำนวนธรรมชาติแรกใน C++

งานคือหาผลรวมของกำลังสามของจำนวนธรรมชาติ N ตัวแรก: 1³ + 2³ + 3³ + ... + N³

ตัวอย่าง

N = 4

1³ + 2³ + 3³ + 4³ = 1 + 8 + 27 + 64 = 100

N = 8

1³ + 2³ + ... + 8³ = 1296

สูตรปิด (Closed-form Formula)

มีสูตรสวยงาม:

1³ + 2³ + ... + N³ = (N(N+1)/2)² = (Sum of first N natural numbers)²

กล่าวคือ ผลรวมกำลังสาม = กำลังสองของผลรวมจำนวนธรรมชาติ

การตรวจสอบ

ตัวอย่างโค้ด (2 วิธี)

วิธีที่ 1: ลูปปกติ (Iterative)

#include <iostream>
using namespace std;

long long sumOfCubesLoop(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += 1LL * i * i * i;
    }
    return sum;
}

วิธีที่ 2: ใช้สูตร (O(1))

long long sumOfCubesFormula(int n) {
    long long s = 1LL * n * (n + 1) / 2;
    return s * s;
}

โค้ดเต็ม

#include <iostream>
using namespace std;

long long sumOfCubesLoop(int n) {
    long long sum = 0;
    for (int i = 1; i <= n; i++) sum += 1LL * i * i * i;
    return sum;
}

long long sumOfCubesFormula(int n) {
    long long s = 1LL * n * (n + 1) / 2;
    return s * s;
}

int main() {
    int n = 10;
    cout << "Loop: " << sumOfCubesLoop(n) << endl;
    cout << "Formula: " << sumOfCubesFormula(n) << endl;
    
    // ทดสอบ N ใหญ่
    n = 1000000;
    cout << "N=1,000,000 Formula: " << sumOfCubesFormula(n) << endl;
    return 0;
}

ผลลัพธ์

Loop: 3025
Formula: 3025
N=1,000,000 Formula: 250000500000250000

การพิสูจน์สูตร (Induction)

Base: n=1: 1³ = 1 = (1×2/2)² ✓

Inductive step: สมมติถูกสำหรับ n, พิสูจน์ n+1:

Σᵢ₌₁ⁿ⁺¹ i³ = (Σᵢ₌₁ⁿ i³) + (n+1)³
           = [n(n+1)/2]² + (n+1)³
           = (n+1)² [n²/4 + (n+1)]
           = (n+1)² (n²+4n+4)/4
           = (n+1)² (n+2)² / 4
           = [(n+1)(n+2)/2]² ✓

ความซับซ้อน

ข้อสังเกตเรื่อง Overflow

• int ล้นที่ N ~ 1600 (1600⁴ ≈ 6.5×10¹² > 2³¹)
• long long (64-bit) รองรับ N ~ 2×10⁶ (2×10⁶⁴ ≈ 1.6×10¹⁹ < 9×10¹⁸)
• N > 2×10⁶ ต้องใช้ __int128 หรือ Big Integer