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)
      (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)
        (search (add1 candidate))))
  (search (add1 start)))

(define (prime-factors n)
  (define (decompose num prime factors)
      ([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)
      (decompose n (next-prime 1) empty)))

(define (remove-duplicates numbers)
  (define (remove numbers result)
      ([empty? numbers] result)
      ([not (member (first numbers) result)]
       (remove (rest numbers) (append result (list (first numbers)))))
       (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))

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

(define (first-triangle-num-with property)
  (define (search candidate)
    (let ([triangle-candidate (number->triangle-number candidate)])
      (if (property 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)))

2 Answers 2



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.


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.


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.


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)


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   )


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


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

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

  • 1
    \$\begingroup\$ Whoa :O That's pretty awesome! \$\endgroup\$
    – user29120
    Commented Sep 20, 2015 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.