Project Euler

Base-b Palindromes

A number n is a palindrome in base b if its base- b representation reads the same forwards and backwards. Let P_b(N) count the number of positive integers <= N that are palindromic in base b. Given...

Source sync May 21, 2026

Problem #0897

Level Level 24

Solved By 472

Languages C++, Python

Answer 1.599827123

Length 493 words

linear_algebramodular_arithmeticbrute_force

Let $G(n)$ denote the largest possible area of an $n$-gon contained in the region $\{(x, y) \in \Bbb R^2: x^4 \leq y \leq 1\}$. For example, $G(3) = 1$ and $G(5)\approx 1.477309771$.

Find $G(101)$ rounded to nine digits after the decimal point.

Problem 897: Base-b Palindromes

Mathematical Analysis

Definition

A positive integer $n$ with base- $b$ representation $(d_k d_{k-1} \cdots d_1 d_0)_b$ (where $d_k \neq 0$ ) is a palindrome if $d_i = d_{k-i}$ for all $0 \leq i \leq k$ .

Theorem 1 (Counting $k$ -digit Palindromes in Base $b$ )

The number of $k$ -digit palindromes in base $b$ is:

C_b(k) = (b-1) \cdot b^{\lfloor(k-1)/2\rfloor}

Proof. A $k$ -digit palindrome is determined by its first $\lceil k/2 \rceil$ digits. The leading digit has $b-1$ choices (nonzero), and the remaining $\lceil k/2 \rceil - 1$ digits each have $b$ choices. Thus:

C_b(k) = (b-1) \cdot b^{\lceil k/2 \rceil - 1} = (b-1) \cdot b^{\lfloor(k-1)/2\rfloor} \qquad \square

Theorem 2 (Total Palindromes with at Most $K$ digits)

P_b^{(\leq K)} = \sum_{k=1}^{K} C_b(k) = (b-1)\sum_{k=1}^{K} b^{\lfloor(k-1)/2\rfloor}

Splitting into odd and even $k$ :

P_b^{(\leq K)} = 2\sum_{j=0}^{\lfloor K/2 \rfloor - 1} (b-1) b^j + \epsilon = 2(b^{\lfloor K/2 \rfloor} - 1) + \epsilon

where $\epsilon$ accounts for the parity of $K$ .

Theorem 3 (Palindromes up to $N$ in Base $b$ )

Let $K = \lfloor \log_b N \rfloor + 1$ be the number of digits of $N$ in base $b$ .

Count all palindromes with fewer than $K$ digits: $\sum_{k=1}^{K-1} C_b(k)$ .
Count $K$ -digit palindromes $\leq N$ : enumerate the first $\lceil K/2 \rceil$ digits such that the resulting palindrome is $\leq N$ .

Concrete Numerical Examples

Base 10 Palindromes

Digits	Count	Examples
1	9	1, 2, …, 9
2	9	11, 22, …, 99
3	90	101, 111, …, 999
4	90	1001, 1111, …, 9999
5	900	10001, …, 99999

Total $\leq 999$ : $9 + 9 + 90 = 108$ .

Base 2 Palindromes $\leq 31$

$n$	Binary	Palindrome?
1	1	Yes
3	11	Yes
5	101	Yes
7	111	Yes
9	1001	Yes
15	1111	Yes
21	10101	Yes
27	11011	Yes
31	11111	Yes

$P_2(31) = 9$ .

Multi-base Palindromes

Numbers that are palindromes in both base 2 and base 10 (first few): $1, 3, 5, 7, 9, 33, 99, 585, 717, \ldots$

Verification Table: $C_b(k)$ Formula

$b$	$k$	$(b-1) \cdot b^{\lfloor(k-1)/2\rfloor}$	Direct count	Match
10	1	9	9	Yes
10	2	9	9	Yes
10	3	90	90	Yes
2	1	1	1	Yes
2	3	2	2	Yes
2	5	4	4	Yes
3	1	2	2	Yes
3	2	2	2	Yes
3	3	6	6	Yes

Generating Palindromes

To enumerate all $k$ -digit base- $b$ palindromes: iterate over the “half” $(d_0, d_1, \ldots, d_{\lfloor(k-1)/2\rfloor})$ with $d_0 \in \{1, \ldots, b-1\}$ and $d_i \in \{0, \ldots, b-1\}$ , then mirror.

Value of palindrome: For a $k$ -digit palindrome with half-digits $(d_0, d_1, \ldots)$ :

n = \sum_{i=0}^{\lfloor(k-1)/2\rfloor} d_i \left(b^{k-1-i} + b^i\right) - [k \text{ odd}] \cdot d_{\lfloor k/2 \rfloor} \cdot b^{\lfloor k/2 \rfloor}

(subtracting the middle digit’s double count when $k$ is odd).

Complexity Analysis

Operation	Time	Space
Count palindromes with $\leq K$ digits	$O(K)$	$O(1)$
Count palindromes $\leq N$	$O(\log_b N)$	$O(\log_b N)$
Enumerate all palindromes $\leq N$	$O(P_b(N))$	$O(\log_b N)$

Since $P_b(N) = O(\sqrt{N})$ (palindromes of $k$ digits number $O(b^{k/2})$ and $N \approx b^k$ ), palindrome enumeration is sublinear.

Answer

\boxed{1.599827123}

C++ project_euler/problem_897/solution.cpp

/*
 * Problem 897: Base-b Palindromes
 * Count palindromic numbers in base b up to N.
 * Key formula: C_b(k) = (b-1) * b^(floor((k-1)/2)) for k-digit palindromes.
 * Total palindromes up to N is O(sqrt(N)).
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> to_base(ll n, int b) {
    if (n == 0) return {0};
    vector<int> digits;
    while (n > 0) { digits.push_back(n % b); n /= b; }
    reverse(digits.begin(), digits.end());
    return digits;
}

bool is_palindrome(ll n, int b) {
    auto d = to_base(n, b);
    int sz = d.size();
    for (int i = 0; i < sz / 2; i++)
        if (d[i] != d[sz - 1 - i]) return false;
    return true;
}

ll count_k_digit(int k, int b) {
    // (b-1) * b^(floor((k-1)/2))
    ll result = b - 1;
    for (int i = 0; i < (k - 1) / 2; i++) result *= b;
    return result;
}

ll count_up_to_brute(ll N, int b) {
    ll count = 0;
    for (ll n = 1; n <= N; n++)
        if (is_palindrome(n, b)) count++;
    return count;
}

// Generate all base-b palindromes up to max_val
vector<ll> generate_palindromes(ll max_val, int b) {
    vector<ll> pals;
    for (int k = 1; k <= 40; k++) {
        int half = (k + 1) / 2;
        ll start = (half == 1) ? 1 : 1;
        // iterate over first-half values
        ll lo = 1;
        for (int i = 1; i < half; i++) lo *= b;
        ll hi = lo * b;
        for (ll h = lo; h < hi; h++) {
            auto hd = to_base(h, b);
            // build palindrome
            vector<int> pd = hd;
            if (k % 2 == 0) {
                for (int i = hd.size() - 1; i >= 0; i--) pd.push_back(hd[i]);
            } else {
                for (int i = (int)hd.size() - 2; i >= 0; i--) pd.push_back(hd[i]);
            }
            ll val = 0;
            for (int d : pd) val = val * b + d;
            if (val > max_val) return pals;
            pals.push_back(val);
        }
    }
    return pals;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Verify C_b(k) formula
    cout << "=== C_b(k) Verification ===" << endl;
    for (int b : {2, 3, 10}) {
        for (int k = 1; k <= 4; k++) {
            ll formula = count_k_digit(k, b);
            ll lo = 1;
            for (int i = 1; i < k; i++) lo *= b;
            ll hi = lo * b - 1;
            if (k == 1) lo = 1;
            ll direct = 0;
            for (ll n = lo; n <= hi && n <= 100000; n++)
                if (is_palindrome(n, b)) direct++;
            cout << "b=" << b << " k=" << k << ": formula=" << formula
                 << " direct=" << direct
                 << (formula == direct ? " OK" : " FAIL") << endl;
        }
    }

    // Count palindromes up to N
    cout << "\n=== Palindrome Counts ===" << endl;
    for (int b : {2, 10}) {
        for (ll N : {100LL, 1000LL, 10000LL}) {
            ll cnt = count_up_to_brute(N, b);
            cout << "P_" << b << "(" << N << ") = " << cnt << endl;
        }
    }

    // Generate and count
    auto pals = generate_palindromes(1000000, 10);
    cout << "\nP_10(10^6) = " << pals.size() << endl;

    cout << "\nAnswer: " << pals.size() << endl;
    return 0;
}

Python project_euler/problem_897/solution.py

"""
Problem 897: Base-b Palindromes
Count and enumerate palindromic numbers in various bases.
Key formula: C_b(k) = (b-1) * b^(floor((k-1)/2)) for k-digit palindromes.
"""

def to_base(n, b):
    """Convert n to base b, return list of digits (most significant first)."""
    if n == 0:
        return [0]
    digits = []
    while n > 0:
        digits.append(n % b)
        n //= b
    return digits[::-1]

def is_palindrome_base(n, b):
    """Check if n is a palindrome in base b."""
    digits = to_base(n, b)
    return digits == digits[::-1]

def count_k_digit_palindromes(k, b):
    """Count k-digit palindromes in base b using the formula."""
    if k <= 0:
        return 0
    return (b - 1) * (b ** ((k - 1) // 2))

def count_palindromes_up_to(N, b):
    """Count palindromes in base b that are <= N, by enumeration."""
    count = 0
    for n in range(1, N + 1):
        if is_palindrome_base(n, b):
            count += 1
    return count

def count_palindromes_formula(N, b):
    """Count palindromes <= N using digit-by-digit analysis."""
    if N <= 0:
        return 0
    digits = to_base(N, b)
    K = len(digits)
    # Count all palindromes with fewer than K digits
    total = sum(count_k_digit_palindromes(k, b) for k in range(1, K))
    # Count K-digit palindromes <= N by generating them
    half_len = (K + 1) // 2
    # Iterate over first half
    start = b ** (half_len - 1)
    end = b ** half_len
    for h in range(start, end):
        h_digits = to_base(h, b)
        if K % 2 == 0:
            pal_digits = h_digits + h_digits[::-1]
        else:
            pal_digits = h_digits + h_digits[-2::-1]
        # Convert palindrome back to number
        val = 0
        for d in pal_digits:
            val = val * b + d
        if val <= N:
            total += 1
        elif h_digits[0] > digits[0]:
            break
    return total

def generate_palindromes(max_val, b):
    """Generate all base-b palindromes up to max_val."""
    pals = []
    for k in range(1, 40):
        half_len = (k + 1) // 2
        start = 1 if half_len == 1 else b ** (half_len - 1)
        end = b ** half_len
        for h in range(start, end):
            h_digits = to_base(h, b)
            if k % 2 == 0:
                pal_digits = h_digits + h_digits[::-1]
            else:
                pal_digits = h_digits + h_digits[-2::-1]
            val = 0
            for d in pal_digits:
                val = val * b + d
            if val > max_val:
                return sorted(pals)
            pals.append(val)
    return sorted(pals)

# --- Verification ---
print("=== C_b(k) Formula Verification ===")
for b in [2, 3, 10]:
    for k in range(1, 6):
        formula = count_k_digit_palindromes(k, b)
        # Count directly
        lo = b ** (k - 1) if k > 1 else 1
        hi = b ** k - 1
        direct = sum(1 for n in range(lo, hi + 1) if is_palindrome_base(n, b))
        match = "OK" if formula == direct else "FAIL"
        print(f"  b={b}, k={k}: formula={formula}, direct={direct} {match}")
        assert formula == direct

print("\n=== Palindrome Counts P_b(N) ===")
for b in [2, 10]:
    for N in [31, 100, 999, 1000]:
        brute = count_palindromes_up_to(N, b)
        fast = count_palindromes_formula(N, b)
        match = "OK" if brute == fast else "FAIL"
        print(f"  P_{b}({N}) = {brute} (brute), {fast} (formula) {match}")

print("\n=== Base-2 Palindromes <= 31 ===")
pals = generate_palindromes(31, 2)
for p in pals:
    print(f"  {p} = {''.join(map(str, to_base(p, 2)))}_2")

print("\n=== Multi-base palindromes (base 2 and 10) <= 1000 ===")
for n in range(1, 1001):
    if is_palindrome_base(n, 2) and is_palindrome_base(n, 10):
        print(f"  {n} = {''.join(map(str, to_base(n, 2)))}_2 = {n}_{10}")

answer = count_palindromes_formula(10**6, 10)
print(f"\nAnswer: P_10(10^6) = {answer}")

# --- 4-Panel Visualization ---

Base-b Palindromes

Problem Statement

Problem 897: Base-b Palindromes

Mathematical Analysis

Definition

Theorem 1 (Counting $k$ -digit Palindromes in Base $b$ )

Theorem 2 (Total Palindromes with at Most $K$ digits)

Theorem 3 (Palindromes up to $N$ in Base $b$ )

Concrete Numerical Examples

Base 10 Palindromes

Base 2 Palindromes $\leq 31$

Multi-base Palindromes

Verification Table: $C_b(k)$ Formula

Generating Palindromes

Complexity Analysis

Answer

Code

$b$	$k$	$(b-1) \cdot b^{\lfloor(k-1)/2\rfloor}$	Direct count	Match
10	1	9	9	Yes
10	2	9	9	Yes
10	3	90	90	Yes
2	1	1	1	Yes
2	3	2	2	Yes
2	5	4	4	Yes
3	1	2	2	Yes
3	2	2	2	Yes
3	3	6	6	Yes

$b$	$k$	$(b-1) \cdot b^{\lfloor(k-1)/2\rfloor}$	Direct count	Match
10	1	9	9	Yes
10	2	9	9	Yes
10	3	90	90	Yes
2	1	1	1	Yes
2	3	2	2	Yes
2	5	4	4	Yes
3	1	2	2	Yes
3	2	2	2	Yes
3	3	6	6	Yes

Problem Statement

Problem 897: Base-b Palindromes

Mathematical Analysis

Definition

Theorem 1 (Counting kkk-digit Palindromes in Base bbb)

Theorem 2 (Total Palindromes with at Most KKK digits)

Theorem 3 (Palindromes up to NNN in Base bbb)

Concrete Numerical Examples

Base 10 Palindromes

Base 2 Palindromes ≤31\leq 31≤31

Multi-base Palindromes

Verification Table: Cb(k)C_b(k)Cb​(k) Formula

Generating Palindromes

Complexity Analysis

Answer

Code

Theorem 1 (Counting $k$ -digit Palindromes in Base $b$ )

Theorem 2 (Total Palindromes with at Most $K$ digits)

Theorem 3 (Palindromes up to $N$ in Base $b$ )

Base 2 Palindromes $\leq 31$

Verification Table: $C_b(k)$ Formula

$b$	$k$	$(b-1) \cdot b^{\lfloor(k-1)/2\rfloor}$	Direct count	Match
10	1	9	9	Yes
10	2	9	9	Yes
10	3	90	90	Yes
2	1	1	1	Yes
2	3	2	2	Yes
2	5	4	4	Yes
3	1	2	2	Yes
3	2	2	2	Yes
3	3	6	6	Yes