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