Sum of the first $n$ palindromes

Question

We put together a problem to be solved programmatically, and we know at lower numbers there is a solution to this problem. How would we go about proving whether the below problem has an answer, as our standard computational approaches do not yield a value.

$X$ is the sum of the first $N$ palindromes. Find the value for $N$ in which $X$ is both over $3$ million and is in it's self palindromic.

We used JS to create a function which finds lower values, but the integers are too large to find a solution where x is greater than 3m

function isPalindrome(x) {
    const s = `${x}`;

    for (let i = 0; i < (s.length - 1) / 2; i++) {
        if (s[i] !== s[s.length - i - 1]) return false
    }
    return true
}

function quickExhaustiveSearch(limit) {
    let i = 0,
        n = 0, // number of pals
        x = 0; // sum of N first pal

    console.log(`Solving for x>${limit} starting at i=${i} and n=${n}`);

    while (x < limit || !isPalindrome(x)) {
        if (isPalindrome(i)) {
            x += i;
            n++;
            console.log({x, i, n});
        }
        i++
    }

    console.log('Solution is', x, i, n);
}

Answer 1

FWIW, here's another Python script. It does the same job as Vepir's code, except it uses a generator to construct the palindromes directly so it's a lot faster. It also puts its progress reports on a single line.

def palgen():
    i = 1
    while True:
        ii = 10 * i
        r = range(i, ii)
        for j in r:
            s = str(j)
            yield s + s[-2::-1]
        for j in r:
            s = str(j)
            yield s + s[::-1]
        i = ii

total = 0
for i, s in enumerate(palgen(), 1):
    total += int(s)
    z = str(total)
    if z == z[::-1]:
        print(z, s, i)
    if i % 100000 == 0:
        print(' progress', z, s, i, end='\r', flush=True)

some output

1 1 1
3 2 2
6 3 3
111 33 12
353 77 16
7557 383 47
2376732 21512 314
 progress 2045049045042045044 2000001000002 3000000

That run took 35 seconds on this ancient 2GHz 32 bit machine.

Answer 2

Partial answer: (Would be great if someone can prove this observation)

I wrote a simple python script to sum palindromes: (python has no integer limit)

---

Update: Decided to listen to DanielV's comment, and optimized my script (credit to this answer):

#generates all palindromes in range
list = palindromes(1, 10**12)

count = 0
pastCount = 0
palindrome =  0

#sums them and check each sum for being a palindrome
for x in list:
    count += x
    palindrome += 1

    # print out only the newest palindromic sum
    if (pastCount != count and str(count) == str(count)[::-1]):
        print (count, palindrome)
        pastCount = count

    # This prints sum of the entire range (last sum)
    if (x == list[-1]):
        print ("progress:", count, palindrome)

Where the palindromes() function is in the linked answer.

$X$, Palindromic sums, it found: $1, 3, 6, 111, 353, 7557, 2376732$
(For first $N$ palindromes: $1, 2, 3, 12, 16, 47, 314$)

This sequence is also in the OEIS and looks like that are all terms there is.

By the look of it, I would bet on that the next sum of palindromes which is also palindromic, does not exist; that there is no solution for $N$ if $X$ is over three million.

But I'm not sure how to prove this.

Here is the output: (took few seconds)

1 1
3 2
6 3
111 12
353 16
7557 47
2376732 314
progress: 545046045045045041 1999999

Where you can see that if $N$ existed, it is surely greater than two million ($N\ge2000000$), where its $X$ is surely greater than $5\times10^{17}$, which is way beyond your three million lower bound.