Problem 941: Binary Palindrome Sums

Mathematical Foundation

Definition 1. A positive integer $n$ is a binary palindrome if its binary representation $b_{k-1} b_{k-2} \cdots b_1 b_0$ satisfies $b_i = b_{k-1-i}$ for all $0 \le i \le k-1$, where $b_{k-1} = 1$ (no leading zeros).

Theorem 1. The number of $k$-bit binary palindromes is $2^{\lfloor (k-1)/2 \rfloor}$ for $k \ge 1$.

Proof. A $k$-bit binary palindrome is determined by its first $\lceil k/2 \rceil$ bits. The leading bit $b_{k-1} = 1$ is fixed. The remaining $\lceil k/2 \rceil - 1 = \lfloor (k-1)/2 \rfloor$ bits are free, each independently 0 or 1. The second half is determined by symmetry: $b_i = b_{k-1-i}$. Hence there are exactly $2^{\lfloor (k-1)/2 \rfloor}$ palindromes of bit-length $k$. $\square$

Lemma 1. Every $k$-bit binary palindrome with $k \le 30$ satisfies $n < 2^{30}$, and every $n$ with $1 \le n < 2^{30}$ has bit-length at most 30.

Proof. A $k$-bit number $n$ satisfies $2^{k-1} \le n < 2^k$. For $k \le 30$, we have $n < 2^{30}$. Conversely, $n < 2^{30}$ implies $n$ has at most 30 bits. $\square$

Theorem 2 (Sum Formula). Let $f = \lfloor (k-1)/2 \rfloor$ denote the number of free bits for $k$-bit palindromes. The sum of all $k$-bit binary palindromes is:

for even $k$, and

for odd $k \ge 3$ (with $S_1 = 1$).

Proof. Each palindrome has value $V = 2^{k-1} + (\text{mirror contributions}) + b_0$ (for even $k$, $b_0 = b_{k-1} = 1$). The leading and trailing bits contribute $2^{k-1} + 1$ to each palindrome. Each free bit $b_i$ at position $k-1-i$ also appears at the mirror position $i$, contributing $2^{k-1-i} + 2^i$ when $b_i = 1$. Over all $2^f$ palindromes, each free bit is 1 in exactly half, giving factor $2^{f-1}$. For odd $k$, the middle bit at position $(k-1)/2$ is its own mirror. $\square$

Editorial

Compute the sum of all binary palindromes less than 2^30. A binary palindrome is a positive integer whose binary representation reads the same forwards and backwards (no leading zeros). Generation strategy: For each bit length k (1..30), generate palindromes by choosing the first ceil(k/2) bits (with MSB = 1), then mirroring to produce the full k-bit palindrome. Results:.

Pseudocode

    total = 0
    For k from 1 to max_bits:
        For half from 2^(ceil(k/2) - 1) to 2^ceil(k/2) - 1:
            palindrome = BuildPalindrome(half, k)
            total += palindrome
    Return total

    bits = binary_digits(half, ceil(k/2))
    full = bits + reverse(bits[0 : floor(k/2)]) // mirror first half
    Return binary_to_int(full)

Complexity Analysis

• Time: $O\!\left(\sum_{k=1}^{30} 2^{\lfloor (k-1)/2 \rfloor}\right) = O(2^{15})$. With $O(k)$ per palindrome for construction, total is $O(30 \cdot 2^{15}) \approx O(10^6)$.
• Space: $O(1)$ auxiliary (palindromes generated on the fly).

Answer

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long total=0;
    int cnt=0;
    for(int k=1;k<=30;k++){
        int half=(k+1)/2;
        for(int fh=(1<<(half-1));fh<(1<<half);fh++){
            long long val=0;
            vector<int> bits;
            int t=fh;
            for(int i=0;i<half;i++){bits.push_back(t&1);t>>=1;}
            reverse(bits.begin(),bits.end());
            vector<int> full=bits;
            if(k%2==1){
                for(int i=half-2;i>=0;i--) full.push_back(bits[i]);
            } else {
                for(int i=half-1;i>=0;i--) full.push_back(bits[i]);
            }
            if((int)full.size()!=k) continue;
            for(int b:full) val=val*2+b;
            if(val>0&&val<(1LL<<30)){total+=val;cnt++;}
        }
    }
    cout<<total<<endl;
    return 0;
}

"""
Problem 941: Binary Palindrome Sums

Compute the sum of all binary palindromes less than 2^30.

A binary palindrome is a positive integer whose binary representation reads
the same forwards and backwards (no leading zeros).

Generation strategy:
    For each bit length k (1..30), generate palindromes by choosing the
    first ceil(k/2) bits (with MSB = 1), then mirroring to produce the
    full k-bit palindrome.

Results:
    - 1-bit: {1}
    - 2-bit: {3}  (11)
    - 3-bit: {5, 7}  (101, 111)
    - Count of binary palindromes < 2^30: computed below

Methods:
    1. gen_binary_palindromes  -- generate all binary palindromes up to max_bits
    2. count_by_bitlength      -- count palindromes grouped by bit length
    3. sum_by_bitlength        -- partial sums by bit length
    4. is_binary_palindrome    -- direct check (verification)
"""

def gen_binary_palindromes(max_bits=30):
    """Generate all binary palindromes with at most max_bits bits, in sorted order."""
    pals = []
    for k in range(1, max_bits + 1):
        if k == 1:
            pals.append(1)
            continue
        half = (k + 1) // 2
        for first_half in range(1 << (half - 1), 1 << half):
            bits = bin(first_half)[2:]
            if k % 2 == 1:
                full = bits + bits[-2::-1]
            else:
                full = bits + bits[::-1]
            val = int(full, 2)
            if val < (1 << max_bits):
                pals.append(val)
    return sorted(pals)

def count_by_bitlength(pals):
    """Return dict mapping bit_length -> count."""
    counts = {}
    for p in pals:
        bl = p.bit_length()
        counts[bl] = counts.get(bl, 0) + 1
    return counts

def sum_by_bitlength(pals):
    """Return dict mapping bit_length -> sum of palindromes."""
    sums = {}
    for p in pals:
        bl = p.bit_length()
        sums[bl] = sums.get(bl, 0) + p
    return sums

def is_binary_palindrome(n):
    """Check if n is a binary palindrome."""
    b = bin(n)[2:]
    return b == b[::-1]

# Verification
assert is_binary_palindrome(1)    # 1
assert is_binary_palindrome(3)    # 11
assert is_binary_palindrome(5)    # 101
assert is_binary_palindrome(7)    # 111
assert not is_binary_palindrome(2)  # 10
assert not is_binary_palindrome(6)  # 110

# Brute-force check for small range
brute_small = [n for n in range(1, 1024) if is_binary_palindrome(n)]
gen_small = [p for p in gen_binary_palindromes(10) if p < 1024]
assert brute_small == gen_small, "Generator mismatch with brute force"

# Computation
pals = gen_binary_palindromes(30)
answer = sum(pals)
print(answer)