Kiểm tra số là tổng các số nguyên liên tiếp C++

Số N có thể viết thành tổng ≥2 số nguyên liên tiếp ⇔ N KHÔNG phải lũy thừa của 2.

Chứng minh

• Tổng k số liên tiếp từ a: k×a + k(k-1)/2 = N.
• N = k×(2a+k-1)/2. Do 2a+k-1 và k khác chẵn/lẻ, N có ước lẻ > 1.
• Chỉ số lũy thừa 2 (1,2,4,8,16...) mới KHÔNG có ước lẻ > 1.

Kiểm tra nhanh

(N & (N-1)) != 0 → N KHÔNG phải lũy thừa 2 → CÓ thể viết thành tổng liên tiếp.

Chương trình C++

#include <iostream>
using namespace std;

bool isSumOfConsecutive(int n) {
    if (n <= 2) return false;
    return (n & (n - 1)) != 0; // Khong phai lu thua 2
}

void findConsecutiveSum(int n) {
    // Tim tat ca cach bieu dien
    for (int k = 2; k*(k+1)/2 <= n; k++) {
        // n = k*a + k(k-1)/2  ->  a = (n - k(k-1)/2) / k
        int num = n - k*(k-1)/2;
        if (num > 0 && num % k == 0) {
            int a = num / k;
            cout << n << " = ";
            for (int i = 0; i < k; i++) {
                if (i) cout << " + ";
                cout << a+i;
            }
            cout << " (k=" << k << ")\n";
        }
    }
}

int main() {
    vector test = {36, 15, 10, 8, 9, 32};
    for (int n : test) {
        cout << n << ": " << (isSumOfConsecutive(n) ? "Co" : "Khong (lu thua 2)") << "\n";
        if (isSumOfConsecutive(n)) findConsecutiveSum(n);
    }
    return 0;
}

Kết quả

36: Co
36 = 11 + 12 + 13 (k=3)
36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 (k=8)
15: Co
15 = 7 + 8 (k=2)
15 = 4 + 5 + 6 (k=3)
15 = 1 + 2 + 3 + 4 + 5 (k=5)
10: Co
10 = 1 + 2 + 3 + 4 (k=4)
8: Khong (lu thua 2)
9: Co
9 = 4 + 5 (k=2)
9 = 2 + 3 + 4 (k=3)
32: Khong (lu thua 2)