Project Euler #12 in Racket

Question

Problem here.

It's not exactly the brute force approach but I'm not using any sort of pre-calculated primes table, and I'm definitely not using the coprimality trick shown in the PE pdf. I'm finding the divisor count for each triangle number via its representation as a product of primes. More on it here.

I've written a bunch of similarly sized programs in Chicken Scheme before, and this is my 2nd Racket program.

Is there anything that I'm doing that isn't something a Racketeer would do? Am I reinventing anything that's already implemented?

#lang racket

(define (prime? n)
  (if (<= n 1)
      #f
      (not (ormap (lambda (x) (= (modulo n x) 0))
                  (stream->list (in-range 2 (add1 (truncate (sqrt n)))))))))

(define (next-prime start)
  (define (search candidate)
    (if (prime? candidate)
        candidate
        (search (add1 candidate))))
  (search (add1 start)))

(define (prime-factors n)
  (define (decompose num prime factors)
    (cond
      ([prime? num] (append factors (list num)))
      ([not (= 0 (modulo num prime))] (decompose num (next-prime prime) factors))
      (else (decompose (quotient num prime) prime (append factors (list prime))))))
  (if (= n 1)
      empty
      (decompose n (next-prime 1) empty)))

(define (remove-duplicates numbers)
  (define (remove numbers result)
    (cond
      ([empty? numbers] result)
      ([not (member (first numbers) result)]
       (remove (rest numbers) (append result (list (first numbers)))))
      (else
       (remove (rest numbers) result))))
  (remove numbers empty))

(define (divisor-count n)
  (let* ([factors (prime-factors n)]
         [no-duplicates-factors (remove-duplicates factors)])
    (apply * (map add1 (map (lambda (x)
                              (count (lambda (y) (= x y)) factors))
                            no-duplicates-factors)))))

(define (number->triangle-number n)
  (quotient (* n (add1 n))
            2))

(define (first-triangle-num-with property)
  (define (search candidate)
    (let ([triangle-candidate (number->triangle-number candidate)])
      (if (property triangle-candidate)
          triangle-candidate
          (search (add1 candidate)))))
  (search 1))

An answer is obtained via a call like:

(first-triangle-num-with (lambda (x) (>= (divisor-count x) 10)))

Answer 1

stream->list

Avoid stream->list on large lists. In your prime? function it will create a (large) list before passing it on to ormap.

There is a stream version of ormap - namedly stream-ormap, and this will process the stream lazily - i.e. it will only generate as many elements of the stream which are needed.

next-prime

Another way to eliminate the recursion here is to combine stream-first with stream-filter and in-naturals with your prime? predicate, e.g.:

(stream-first (stream-filter prime? (in-naturals ...) ))

Not that recursion is bad, but using streams results in a more declarative definition.

append

I would avoid append in a Lisp or a Scheme. I'm sure it's not efficient for use on lists. cons, however, is always efficient, so in prime-factors you should use:

(cons num factors)

instead of:

(append factors (list num))

You build the list in reverse order, but it won't matter in this case.

remove-duplicates

You are also using append here which should be avoided. The standard definition again uses cons:

(define (remove-duplicates xs)
   -- if xs is empty, return xs
   -- else return x followed by remove-duplicates on the tail elements not equal to x
     (cons (head x)
           (remove-duplicates (filter (lambda (y) (not (eq? x y))) (tail xs))))
)

For short lists this is fine - but note that its running time is O(n^2). If you need a better one, there is one available in the standard library: remove-duplicates in the standard library. On longer lists it uses a hash - you can view the source here: (link)

divisor-count

Honestly I had trouble understanding your prime-factors and divisor-count routines.

The conventional way of computing the number of divisors of a number n is:

1. find a prime divisor p of n
2. find the exponent e of the prime p in the factorization of n
3. repeat this process with n / p^e until n = 1

Then you have a list of primes and their exponents: (p1, e1), (p2, e2), etc. and the number of divisors is:

(1+e1) * (1 + e2) * ...

How about this approach:

(define (divisor-count n)
  (apply * (map add1 (prime-exponents n))))

(define (prime-exponents n)
   -- if n == 1 return the empty list
   -- otherwise, find the first prime p dividing n
   -- find largest e s.t. p^e divides n
   -- return e and recurse on n / p^e   )

first-triangle-number

This is another place where using streams can help:

1. Create a stream of triangle numbers
2. Filter the stream keeping only those with large divisor counts
3. Take the first element of the stream

i.e.:

(stream-first (stream-filter ... (stream-map ... (in-naturals 1))))
                                                 \___ 1, 2, ... __/
                                 \__ 1, 3, 6, 10, ...          __/
              \___ triangular numbers having #divisors >= 50  __/
\___ answer to the problem                                   __/

Note that (in-naturals 1) is an infinite stream.

for, for/list

When you get comfortable using the stream- functions, look into Racket's sequence comprehensions: for, for/list, for/vector, etc.

See http://docs.racket-lang.org/guide/for.html for more info.

Answer 2

The main thing you're reimplementing is divisors. Also, you can generate triangle numbers using SRFI 41 streams. Using these two things together, we have:

#lang racket
(require srfi/41 math/number-theory)
(define naturals (stream-cons 1 (stream-map add1 naturals)))
(define triangles (stream-cons 0 (stream-map + naturals triangles)))
(for/first ((n (in-stream triangles))
            #:when (> (length (divisors n)) 500))
  (display n))

I'm sorry that this is nothing like your original program, but your question asked "Am I reinventing anything that's already implemented?", and it seems that pretty much everything in your program is indeed a reinvention. :-(