3
$\begingroup$

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?

  • 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.2012-01-10
  • 0
    @Lopsy good answer...why is it a comment?2012-01-10
  • 0
    See http://meta.math.stackexchange.com/questions/1090/re-project-euler-questions2012-01-10
  • 0
    @MarianoSuárez-Alvarez if someone wanted to [cheat off of my answer](http://codereview.stackexchange.com/questions/7615/project-euler-4-incorrect-results-on-7-digit-numbers), I would say more power to them. Hopefully they'd learn something and get the fifth one right!2012-01-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 :)2012-01-10

2 Answers 2

3

Mathematically producing palindromes is not necessarily faster than using strings.

3

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

  • 0
    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.2012-01-10
  • 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$.2012-01-10