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