# Project Euler #12 in Racket

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

(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)
2))

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


An answer is obtained via a call like:

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


# 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)


(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
(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) * ...


(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.

• I like that your answer is a critique, rather than a complete reimplementation, of the OP's program. Of course I still think my solution has less reinvention (which was what the OP asked for), but within the framework of what the OP coded, your comments are spot on. – Chris Jester-Young Sep 20 '15 at 18:28
• Thanks! It's often sometimes hard to know what people are expecting when they post in this forum :-) – ErikR Sep 20 '15 at 20:07
• Thanks for the elaborate review, I'll read it more carefully today. – user29120 Sep 21 '15 at 9:37

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. :-(

• Whoa :O That's pretty awesome! – user29120 Sep 20 '15 at 18:28