Euler Solution 36

From ProgSoc Wiki

Jump to: navigation, search

Contents

Solutions for Problem 36

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

Ruby by tomchristmas

Runtime: 4681ms.

def to_bin(num)
   (num > 0) ? "#{(num % 2).to_s}#{to_bin(num/2)}" : ""
end

sum = 0
1.upto(999999){|x| sum += x if (x.to_s == x.to_s.reverse) && (to_bin(x) == to_bin(x).reverse)}
puts sum

C by SanguineV

Runtime: 82.818 ms

#include <stdio.h>

// Do the bitwise reversal and then shift to right justify
// NOTE: this is not strictly accurate, but works for palindromes!
unsigned long bitrev(unsigned long n) {
  n = ((n >> 1) & 0x55555555) | ((n << 1) & 0xaaaaaaaa);
  n = ((n >> 2) & 0x33333333) | ((n << 2) & 0xcccccccc);
  n = ((n >> 4) & 0x0f0f0f0f) | ((n << 4) & 0xf0f0f0f0);
  n = ((n >> 8) & 0x00ff00ff) | ((n << 8) & 0xff00ff00);
  n = ((n >> 16) & 0x0000ffff) | ((n << 16) & 0xffff0000);
  while (!(n & 1)) {
    n = n >> 1;
  }
  return n;
}

// Do the decimal reversal
unsigned long decrev(unsigned long n) {
  unsigned long res = n % 10;
  while (n > 10) {
    n = n / 10;
    res = (res * 10) + (n % 10);
  }
}

// Start at 1 and go through all the odd positive ints less than 1 million
int main( void )
{
  unsigned long n = 1;
  unsigned long tot = 0;
  while (n < 1000000) {
    if (n == bitrev(n) && n == decrev(n)) {
      tot += n;
    }
    n += 2;
  }
  printf("Total: %u\n",tot);
  return 0;
}

Just a little faster when you can do bitwise operations.

Python by Althalus

Runtime: 3.93 seconds

import time
start_time = time.time()

def dec2bin(n):
        #convert decimal  to binary
        bin = 
        if n == 0: return '0'
        while n > 0:
                bin = str(n % 2) + bin
                n = n >> 1
        return bin

def isPalindrome(number):
        #Same as from problem 4
        number = str(number)
        for i in range (0,int(len(number)//2)):
                if number[i] != number[-(i+1)]:
                        return False
        return True

sum = 0
for i in range(1,1000001):
        if isPalindrome(i) and isPalindrome(dec2bin(i)):
                sum += i
print sum

run_time = time.time() - start_time
print run_time
Personal tools