ผลรวมกำลังสามของ n จำนวนธรรมชาติแรกใน Java

ผลรวมกำลังสาม (Sum of Cubes)

คำนวณ 1³ + 2³ + 3³ + ... + n³

สูตรทางคณิตศาสตร์

(1 + 2 + ... + n)² = [n(n+1)/2]²

คือ ผลรวมกำลังสามของ n จำนวนแรก = กำลังสองของผลรวม n จำนวนแรก

ตัวอย่างโค้ด (Loop)

import java.util.*; 

public class Demo { 
    public static int sumOfCubesLoop(int n) { 
        int sum = 0; 
        for (int i = 1; i <= n; i++) { 
            sum += i * i * i; // i³
        } 
        return sum; 
    } 
    
    // ใช้สูตรทางคณิตศาสตร์ O(1)
    public static int sumOfCubesFormula(int n) { 
        int sum = n * (n + 1) / 2; 
        return sum * sum; 
    } 
    
    public static void main(String[] args) { 
        int n = 7; 
        
        System.out.println("Loop:    " + sumOfCubesLoop(n)); 
        System.out.println("Formula: " + sumOfCubesFormula(n)); 
        
        // Verify
        System.out.println("1³+2³+...+7³ = " + (1+8+27+64+125+216+343)); 
    } 
}

ผลลัพธ์

Loop:    784
Formula: 784
1³+2³+...+7³ = 784

คำอธิบาย

โค้ดต้นฉบับใช้ลูป O(n) แต่สามารถคำนวณได้ O(1) ด้วยสูตร [n(n+1)/2]²

การพิสูจน์แบบ Induction

Base: n=1: 1³ = 1 = [1(2)/2]² = 1 ✓
Assume true for n=k: 1³+...+k³ = [k(k+1)/2]²
Prove for n=k+1:
1³+...+k³+(k+1)³ = [k(k+1)/2]² + (k+1)³
= (k+1)² [k²/4 + (k+1)]
= (k+1)² [(k²+4k+4)/4]
= (k+1)² [(k+2)²/4]
= [(k+1)(k+2)/2]² ✓

BigInteger สำหรับ n ใหญ่

import java.math.BigInteger; 

public static BigInteger sumOfCubesBig(int n) { 
    BigInteger N = BigInteger.valueOf(n); 
    BigInteger sum = N.multiply(N.add(BigInteger.ONE)).divide(BigInteger.valueOf(2)); 
    return sum.multiply(sum); 
}

การประยุกต์ใช้

• คณิตศาสตร์: Nicomachus's theorem
• Computer Science: Algorithm analysis, Loop invariants
• Physics: Moment of inertia calculations