Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
    
    
@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
1  
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

3 Answers 3

up vote 3 down vote accepted

Mathematically producing palindromes is not necessarily faster than using strings.

share|improve this answer

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$.

share|improve this answer
    
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
1  
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)
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.