# 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. Sep 20, 2015 at 18:28
• Thanks! It's often sometimes hard to know what people are expecting when they post in this forum :-) Sep 20, 2015 at 20:07
• Thanks for the elaborate review, I'll read it more carefully today.
– user29120
Sep 21, 2015 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, 2015 at 18:28