Project Euler | Incongruent Thoughts

May 05 2011

Project Euler – Problem 145

Analysis

Suprisingly enough the brute-force solution works. It takes a couple of minutes but it gets the job done. Suppose we have a function called is_reversible then the following algorithm can be used to count all the reversible numbers below one-billion.

count = 0
for i = 1 upto 1000000000 do
  if (is_reversible(i)) then count++
endfor
output count

Implementation

Uses the OCaml programming language.

(* a left fold over the digits of a positive integer *)
let rec nfoldl f v = function
    0 -> v
  | n -> nfoldl f (f v (n mod 10)) (n / 10)

let reverse = nfoldl (fun n d -> (n * 10) + d) 0

let odd n = n mod 2 = 1
let allodd = nfoldl (fun b d -> b && odd d) true

let is_reversible n =
  n mod 10 <> 0 && allodd (n + reverse n)

let naive_count n =
  let cnt = ref 0 in
    for i = 1 to n-1 do
      if is_reversible i then incr cnt;
    done;
    !cnt

The above code is elegant and it solves the problem but I’m not satisfied with its speed. In that regard I decided to improve on the algorithm a bit.

More Analysis

Notice that since the sum of a number, $n$ , and its reverse, $reverse(n)$ must yield a number with all digits odd, it must be the case that $n$ cannot begin and end with digits of the same parity (i.e. both even or both odd). Hence, a likely candidate must lie in one of these sets $A = \{n : n \,\text{begins with}\, 2, 4, 6, 8 \,\text{and}\, n \,\text{ends with}\, 1, 3, 5, 7, 9\}$ or $B = \{n : n \,\text{begins with}\, 1, 3, 5, 7, 9 \,\text{and}\, n \,\text{ends with}\, 2, 4, 6, 8\}$ . Now, $|A| = |B| = (4*5)*10^7 = 200000000$ , i.e. 200 million. Furthermore, if a number in $A$ is reversible then its reverse is in $B$ and is obviously reversible as well. This means we only need to generate the elements and count those in $A$ that are reversible. Our final answer must then be multiplied by $2$ to account for those in $B$ .

A Better Implementation

Uses the Haskell programming language. I switched languages when I realised that the list code I needed for this to work was not implemented using tail-recursion in the OCaml standard library. I did rewrite those pieces using tail recursion but in the end I still decided to switch languages just for the fun of it. Actually, the Haskell version below isn’t much better. Its still slow. But very elegant :D. At least I can use it for testing correctness on small cases since the solution is so simple and easy to read.

nfoldl _ v 0 = v
nfoldl f v n = nfoldl f (f v (n `mod` 10)) (n `div` 10)

nreverse = nfoldl (\n d -> (n * 10) + d) 0
allodd = nfoldl (\b d -> b && odd d) True
isReversible n = n `mod` 10 /= 0 && allodd (n + nreverse n)

countDigits = (+1) . floor . logBase 10 . fromIntegral

genCandidates n =
  let gen m i len = if i > len then
                      if m >= n then [] else [m]
                    else
                      if i == 1 then
                        concatMap (\d -> gen (m*10+d) (i+1) len) [1,3,5,7,9]
                      else if i == len then
                        concatMap (\d -> gen (m*10+d) (i+1) len) [2,4,6,8]
                      else
                        concatMap (\d -> gen (m*10+d) (i+1) len) [0..9]
  in concatMap (gen 0 1) [1..countDigits n]

betterCount = (*2) . length . (filter isReversible) . genCandidates

Finally, I bit my tongue and decided to code up a solution in everyone’s favorite system programming language, C.

#include <stdio.h>
#include <math.h>

#define FALSE 0
#define TRUE  1

#define even(n) ((n)%2==0)

int reverse(int n) {
  int m = 0;
  while (n > 0) { m = m*10 + (n%10); n /= 10; }
  return m;
}

int allodd(int n) {
  while (n > 0) {
    if (even(n%10)) return FALSE;
    n /= 10;
  }
  return TRUE;
}

#define is_reversible(n) ((n)%10>0 && allodd((n) + reverse(n)))
#define count_digits(n) ((int)(floor(log10(n) + 1)))

int __count;

void __better_count(int m, int i, int len, int n) {
  int j;
  if (i > len) {
    if (m < n && is_reversible(m)) __count += 2;
  } else {
    if (i == 1) {
      for (j = 1; j <= 9; j+=2) __better_count(m*10+j, i+1, len, n);
    } else if (i == len) {
      for (j = 2; j <= 8; j+=2) __better_count(m*10+j, i+1, len, n);
    } else {
      for (j = 0; j <= 9; j++) __better_count(m*10+j, i+1, len, n);
    }
  }
}

int better_count(int n) {
  int len;
  
  __count = 0;
  for (len = 2; len <= count_digits(n); len++) __better_count(0, 1, len, n);
  return __count;
}

int main(void) {
  printf("%d\n", better_count(1000000000));
  return 0;
}

In the end, the problem was easy and I had a lot of fun playing around with the various languages. I learned quite a lot, so it certainly wasn’t a waste of time.

Tagged c, haskell, ocaml, p145, programming, project euler

Nov 21 2010

2 Comments

Project Euler

Project Euler – Trinidad and Tobago Standings

Below is an image of the current standings in projecteuler.net as of 21/11/2010 for Trinidad and Tobago.

As you can see I’m 2nd in the standings. Damn you wallygold. Lol. I need to solve 10 more problems to reach Level 3. Hopefully, I will have time to do it before the year ends.

A note about the languages I use. Currently I’m using racket (a scheme based language) to solve the problems. However, in the past I’ve solved some of the problems using C, Java, Python, Haskell, Scala, LISP and of course the trusty old pencil and paper. I guess I tend to utilize whatever language I am currently into.

Tagged project euler

Nov 21 2010

Project Euler – Problem 71

The problem: Problem 71

Analysis

Let $d$ be some integer larger than $1$ , $F(d) = \{ \frac{a}{b} : 1 \leq a < b \leq d\}$ and $F_0(d) = \{0\} \cup F(d)$ . Let $prev_d$ be a function from $F(d)$ to $F_0(d)$ defined as follows:

$prev_d(t) = s$ ,

where $s$ is the largest fraction in $F_0(d)$ that is less than $t$ . As the example in the problem illustrates, $prev_8(\frac{3}{7}) = \frac{2}{5}$ . We need to find $prev_{1000000}(\frac{3}{7}).$

Let $t \in F(d)$ and $n$ be an integer between $1$ and $d$ inclusive. We now define $p_d(t,n)$ as follows:

$p_d(t,n) = s$ ,

where $s$ is the largest fraction with a denominator of $n$ in $F_0(d)$ that is less than $t$ .

Clearly then,

$prev_d(t) = max_{2 \leq n \leq d}\{ p_d(t,n) \}$ .

Thus it suffices to show how to compute $p_d(t,n)$ . The implementation which will be given below uses a modified binary search to compute $p_d(t,n)$ . The running time is $O(lg\,n)$ . Therefore, it takes

$lg\,2 + lg\,3 + \cdots + lg\,d = lg\,d! = O(d \cdot lg\,d)$

time to compute $prev_d(t)$ for any $t$ .

Implementation of $p_d(t,n)$

Uses the racket programming language.

;; finds the largest fraction with a denominator of n
;; that is less than t
(define (p t n) ;; assumes n <= d
  (let ([a (numerator t)]
        [b (denominator t)])
    (/ (let loop ([l 0] [h (- n 1)])
         (if (> l h)
             0
             (let ([m (quotient (+ l h) 2)])
               (if (< (* m b) (* a n))
                   (max m (loop (+ m 1) h))
                   (loop l (- m 1))))))
       n)))

An example showing how to use p to compute $prev_8(\frac{3}{7})$ .

> (p (/ 3 7) 2)
0
> (p (/ 3 7) 3)
1/3
> (p (/ 3 7) 4)
1/4
> (p (/ 3 7) 5)
2/5
> (p (/ 3 7) 6)
1/3
> (p (/ 3 7) 7)
2/7
> (p (/ 3 7) 8)
3/8

Since $\frac{2}{5}$ is the maximum of the values that were computed, we can conclude that $prev_8(\frac{3}{7}) = \frac{2}{5}$ .

Finally, we use the same idea to get $prev_{1000000}(\frac{3}{7})$ . The full implementation takes about 7 seconds to compute the answer.

Tagged p71, programming, project euler, racket

Incongruent Thoughts

My musings on programming, mathematics and life

Category Archives: Project Euler

Project Euler – Problem 145

Analysis

Implementation

More Analysis

A Better Implementation

Project Euler – Trinidad and Tobago Standings

Project Euler – Problem 71

Analysis

Implementation of $p_d(t,n)$

Follow “Incongruent Thoughts”