Duncan's blog

December 9, 2009

Project Euler problem 55

Filed under: Project Euler,Python — duncan @ 12:00 am
Tags: , , , ,

Problem 55:


If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,

349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337

That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. A number that never forms a palindrome through the reverse and add process is called a Lychrel number. Due to the theoretical nature of these numbers, and for the purpose of this problem, we shall assume that a number is Lychrel until proven otherwise. In addition you are given that for every number below ten-thousand, it will either (i) become a palindrome in less than fifty iterations, or, (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

Yet another problem which was easy to code in ColdFusion, but it couldn’t deal with the large numbers generated. So rewrote it in Python.

Just for interest, here’s what I did in CFML. NB: there’s a logic error here, which I fixed once I moved to Python:

<cfscript>
function isPalindrome(x)
{
	if (x EQ Reverse(x))
		return true;
	else
		return false;
}
</cfscript>

<cfset Lychrel = ArrayNew(1)>

<cfloop index="i" from="1" to="9999">
	<cfset k = i>
	
	<cfloop index="j" from="1" to="50">
		
		<cfset temp = k + Reverse(k)>
		
		<cfif IsPalindrome(temp)>
			<cfoutput>#k# + #Reverse(k)# = #temp#</cfoutput><br>
			<cfset ArrayAppend(Lychrel, i)>
			<cfbreak>
		</cfif>
		
		<cfset k = temp>
	</cfloop>	
</cfloop>

<cfoutput><strong>#ArrayLen(Lychrel)#</strong></cfoutput>

Running this it quickly throws an error:
‘The value 210+E11200002108.1 cannot be converted to a number.’

Python doesn’t seem to have a built-in Reverse function like ColdFusion, so you have to write your own.

def Reverse(x):
        num = str(x)
        newnum = ''
        
        for i in range(len(num)-1, 0, -1):
                newnum += num[i]

        newnum += num[0]
        
        return newnum


Lychrel = []
limit = 10000

for i in range(1, limit):
	k = i

	for j in range(50):		
		temp = k + int(Reverse(k))

		if str(temp) == str(Reverse(temp)):
			break
		
		k = temp

	if j == 49:
	      Lychrel.append(i)
              
print(len(Lychrel))

This code is pretty fast, but it could be better. For instance I’m casting everything to a string or an int as required, but that could maybe be tidied up somehow.
Also in my Reverse function, I somehow couldn’t work out how to properly loop backwards through the string, so ended up having to add on the first character outside of the loop.

Initially I was appending to my Lychrel array at the point where I break out of the loop. However on reading the question again I realised the Lychrel numbers are the numbers which aren’t solved within 50 iterations, not the other way around. I don’t even need an array, I could just have a counter that I increment. But having it in the array gives us the advantage of being able to output the array contents to make sure we’re on the right track.

6 Comments »

  1. That’s because you are running it in the ColdFusion Server, and it’s lazy to do maths. Run it on a Railo instance, and it takes just over a quarter of a second to run, and produces the following results:

    Put it on pastebin so it doesn’t swamp your post with the hundreds results🙂

    http://pastebin.com/f551b069d

    Comment by Marcos Placona — December 9, 2009 @ 10:27 am | Reply

  2. Couldn’t the body of the isPalindrome function be written as “return (x EQ Reverse(x))” to avoid redundancy?

    Comment by Rabo — March 9, 2010 @ 8:11 pm | Reply

  3. “But having it in the array gives us the advantage of being able to output the array contents to make sure we’re on the right track.”

    Just print them as you find them, copying them to the array serves no purpose at all

    Comment by ardnew — March 31, 2010 @ 5:06 am | Reply

  4. ColdFusion, like every web language, sucks at doing math. I personally use C# to solve the project euler problems, because it’s easy and quick.

    I blog about project euler too!

    Comment by Ssmm987 — December 26, 2010 @ 3:56 pm | Reply

  5. python can use the following code to reverse a number.

    int(str(num)[::-1]) #for num is a number

    Comment by Cestial — February 26, 2011 @ 10:02 am | Reply

  6. […] previously blogged about this Project Euler puzzle over 5 years ago, using Coldfusion and Python.  This is my approach using PHP as a simple practical exercise for […]

    Pingback by Project Euler: problem 55 (PHP) – Lychrel numbers | Duncan's blog — October 19, 2014 @ 8:03 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: