# Generating Numeric Palindromes.

I have just started the Euler project, and felt like I didn't get the fourth problem right...I used string conversion to test if my numbers were symmetrical, instead of relying on (the much faster) method of mathematically producing palindromes.

I have searched more than a dozen times on variations of this subject, and have found every last approach to this problem (computationally) involves translating the number from base 2 to base 10, so that it can be manipulated in a more human-friendly way.

Is there a pattern, or function that exists to generate palindromic numbers?

-
If you want to generate a list of, say, 6-digit palindromes, then you can use the expression ABCCBA = 100000A+10000B+1000C+100C+10B+A and iterate through all the digits. However, your method sounds like a better way to solve the problem in the first place. One heuristic you could use, if you really want to, is that every palindrome with an even number of digits is divisible by 11. – Lopsy Jan 10 '12 at 1:29
@Lopsy good answer...why is it a comment? – Droogans Jan 10 '12 at 1:41
– Mariano Suárez-Alvarez Jan 10 '12 at 2:00
@MarianoSuárez-Alvarez if someone wanted to cheat off of my answer, I would say more power to them. Hopefully they'd learn something and get the fifth one right! – Droogans Jan 10 '12 at 2:10
Well, the point of the discussion I linked to is that the Project Euler authors would prefer that people do not share answers. I, really, do not care at all :) – Mariano Suárez-Alvarez Jan 10 '12 at 2:12

Mathematically producing palindromes is not necessarily faster than using strings.

-

For a six digit palindrome (as in Project Euler problem 4), you can take an integer $n$ with $100 \le n \le 999$ and calculate

$$1100 \times n - 990 \times \lfloor n/10 \rfloor - 99 \times \lfloor n/100 \rfloor$$

and palindromes with other numbers of digits can be generated a similar way.

For example with $n=317$ you get $1100 \times 317 - 990 \times 31 - 99 \times 3 = 317713$.

-
Yes it works...I tweaked it a bit trying to get it right for four digit palindromes...11000 * n - 9901 * (n / 10) - 989 * (n / 100). It's off by one or two, depending on what number you pick. – Droogans Jan 10 '12 at 2:37
If you mean eight digit palindromes then $$11000 \times n - 9900 \times \lfloor n/10 \rfloor - 990 \times \lfloor n/100 \rfloor - 99 \times \lfloor n/1000 \rfloor.$$ Remember $\lfloor x \rfloor$ is the floor or integer part of $x$. – Henry Jan 10 '12 at 8:05

Here is an algorithm for generating numeric palindromes.

I recently did the google codejam competition and there was a question involving palindromes. For some reason (I don't really know which) I got interested in them and decided to come up with a formula to generate the nth palindrome. I was only capable to come up with an algorithm to generate palindromes. Below is a better version of it. It is easy to prove its correctness. I leave this as homework!

# Python3 code
# Algorithm to recursively generate all palindromes progressively,
# starting from a given 'base' palindrome (1, 11, 101, 1001...).
# k is the number of digits of the palindrome.
# l is about the algorithm, not explained here though!

def palindromes(k, l):
global palindrome    # to keep things simple!

if(k>5): return      # remove this line so to go to infinity!

a=(k+1)//2           # a is about the algorithm
if(l==a): return     # base case reached

if(l==a-1 and k%2):
inc = 1*(10**l)  # I got trouble with odd values of k
else: inc = 11*(10**l)

for i in range(9):   # Ok, these 4 lines are the most important
palindromes(k, l+1)
print(palindrome)
palindrome+=inc

if(l!=0): palindromes(k, l+1)

else:                # base case for changing the number of digits
palindrome=palindrome-inc+2
palindromes(k+1, l)

palindrome=1
palindromes(1, 0)

-