Every positive integer can be written as the sum of 3 palindrome integers. Wha'ts the largest possible palindrome integer for each integer n?

Question

Let n be a positive integer then n = a + b + c for some a, b, and c that are palindrome integers. What is the largest possible integer a for k = 1 to 1_000_000?

Golf this or have the fastest running time.

NOTE: it's NOT the same as this question as I am asking for the largest palindrome component. The question just asks for ANY combination.

Answer 1

My Julia solution

using Base.Iterators

is_palindrome(n) = begin
    dn = digits(n)
    all(dn .== reverse(dn))
end

lim  = Int64(1e6)
res = filter(is_palindrome,lim:-1:0)

using DataFrames
lp = DataFrame(k = 1:1_000_000, largest_palindrome = Array{Int64,1}(lim))

# found stores the integers backwardds
ok(lim, res, lp) = begin
    found = BitArray(lim)
    found .= false
    tot = Int128(0)

    cap = lim
    r = res[1]

    for r in res[1:end-1]
        bs = res[res .<= (cap - r)]
        cs = res[res .<= ceil((cap - r)/2)]

        res1 = vec([r + b + c for (b,  c) in product(bs,cs)])

        res1 = res1[res1 .<= cap]

        for rr in res1
            if !found[rr]
                lp[rr,:largest_palindrome] = r
                tot = tot + r
                found[rr] = true
            end
        end

        for i in lim:-1:1
            if !found[i]
                cap = i
                break
            end
        end
    end

    (tot, found, lp)
end