Duncan's blog

November 8, 2008

Project Euler: problem 36

After struggling for several days with another Project Euler problem, I decided to give up and tackle something easier. This one took about five minutes to work out.

Problem 36:

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

So I reused the IsPalindrome function I wrote for Problem 4. The only new part here is working out a number in base 2. Coldfusion conveniently has a FormatBaseN function, allowing you to convert a number from base 10 to any other base. The inverse of that is InputBaseN, converting a number from any base back to base 10.

<cfset sum = 0>

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

<cfloop index="i" from="1" to="999999">
	<cfif isPalindrome(i) AND isPalindrome(FormatBaseN(i, 2))>
		<cfoutput>#i# #FormatBaseN(i, 2)#<br></cfoutput>
		<cfset sum = sum + i>
	</cfif>
</cfloop>

<cfoutput><strong>#sum#</strong></cfoutput>

2 Comments »

  1. this is my fast solution in python

    
    MAX = 1000000
    
    def nextPalin(n):
        strn = str(n)
        dn = len(strn)
        strn = str(int(strn[:(dn+1)/2]) + 1) + strn[(dn+1)/2:]
        dn = len(strn)
        strl = strn[:(dn+1)/2]
        if dn & 1: strr = ''.join(reversed(strl[:-1]))
        else: strr = ''.join(reversed(strl))
        return int(strl + strr)
    
    def isBinPalin(n):
        r, bbin = n, ''
        while n > 0:
            bbin += str(n & 1)
            n >>= 1
        rbin = ''.join(reversed(bbin))
        if rbin == bbin: return r
        return 0
    
    def main():
        n, ans = 1, 0
        while n < MAX:
            ans += isBinPalin(n)
            n = nextPalin(n)
        print ans
    
    main()
    

    Comment by zobayer2009 — December 13, 2010 @ 9:32 pm | Reply

  2. […] previously blogged about this Project Euler puzzle nearly 6 years ago, using ColdFusion.  This is my approach using PHP as a simple practical exercise for myself, and […]

    Pingback by Project Euler: problem 36 (PHP) | Duncan's blog — October 11, 2014 @ 8:01 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: