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.

• C. K. Young: 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.
• ErikR: Thanks! It's often sometimes hard to know what people are expecting when they post in this forum :-)
• user29120: Thanks for the elaborate review, I'll read it more carefully today.

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

• user29120: Whoa :O That's pretty awesome!