โปรแกรม Java คำนวณผลรวมกำลังสอง n ตัวแรก (Sum of Squares)

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

Σ(i=1 to n) i² = n(n+1)(2n+1) / 6

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

public class Demo {
    // ใช้สูตรปิด (closed form) O(1)
    public static long sumOfSquares(long n) {
        return n * (n + 1) * (2 * n + 1) / 6;
    }
    
    // Iterative O(n) - สำหรับ verify
    public static long sumOfSquaresIterative(long n) {
        long sum = 0;
        for (long i = 1; i <= n; i++) {
            sum += i * i;
        }
        return sum;
    }
    
    public static void main(String[] args) {
        int n = 8;
        System.out.println("n = " + n);
        System.out.println("Formula: " + sumOfSquares(n));
        System.out.println("Iterative: " + sumOfSquaresIterative(n));
        
        // 1²+2²+...+8² = 1+4+9+16+25+36+49+64 = 204
        
        // Large n test
        long bigN = 1_000_000;
        System.out.println("\nSum of squares 1 to " + bigN + ": " + sumOfSquares(bigN));
    }
}

ผลลัพธ์

n = 8
Formula: 204
Iterative: 204

Sum of squares 1 to 1000000: 333333833333500000

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

ใช้ (k+1)³ - k³ = 3k² + 3k + 1
Sum ทั้งสองข้าง k=1..n:
(n+1)³ - 1³ = 3Σk² + 3Σk + n
Σk² = [n³ + 3n² + 3n - 3n(n+1)/2 - n] / 3 = n(n+1)(2n+1)/6

Overflow Prevention

• ใช้ long (64-bit) รองรับได้ถึง n ≈ 2.6×10⁶
• n ใหญ่กว่า: ใช้ BigInteger หรือคำนวณ modulo
• จัดกลุ่มการหาร: n * (n+1) / 2 * (2n+1) / 3 ลด intermediate overflow

Related Formulas

• Σi = n(n+1)/2
• Σi² = n(n+1)(2n+1)/6
• Σi³ = [n(n+1)/2]² = (Σi)²