rickyboy wrote:Hi Ted!

Actually, there is a way to make your program even faster -- a lot faster. The idea is that there is a way to determine the number of divisors of a (natural) number which is a lot cheaper than computing the unique sub-groupings of its prime factors. Here is a routine that does just that.

...

Wow. Your Number Theory-fu is excellent!

http://www.cut-the-knot.org/blue/NumberOfFactors.shtmlAlso, your algorithm does the standard count of the number of factors. My count doesn't allow 1 as a factor, which offsets them by one. And you know what I found? 60% of the antiprimes, have a prime number of factors. If we don't allow 1 as a factor. Shift by 1, and suddenly only the first 2 antiprimes have a prime number of factors.

Now, call it from `antiprime` like this:

...

It flies now! :)

That is an understatement... 4 and 1/2 hours of computing cut down to 41 seconds. Nice!

Why curry rather than (fn (x) (+ 1 x)) in the map? Performance, or just the code looks nicer?

The combinations function is useful for other things; can you advise? I tried to shorten it a little, but it gives an error. I've tried tracing the code and it is really puzzling me.

I'm replacing this code:

- Code: Select all
`(let (rlst '())`

(dolist

(extend rlst ...))

rlst)

With this:

- Code: Select all
`(let (rlst '())`

(dolist

(extend rlst ...)))

Should work... but it errors with the error

ERR: list expected : (combinations ((+ 1 $idx) n) k (append r (list x)) true (+ 1 lvl))

called from user function combinations

called from user function all-factors

called from user function antiprime

Here is the instrumented code:

- Code: Select all
`#!/usr/bin/newlisp -n`

# Anti-primes are highly composite numbers

# Print each number that is more composite than all the numbers before it.

(define start-time (date-value))

(define maxiter 4)

(define lastn 1)

(define (prime? n) (= 1 (length (factor n))))

(define (combinations n k (r '()) (mysilent nil) (lvl 0))

(unless mysilent (println "combinations " n " " k " " r ":" (if (list? r) "list" "not-a-list") " level " lvl))

(if (= (length r) k)

(list r)

(let (rlst '())

(dolist (x n)

(unless mysilent (println "extend yields list? " (list? (extend (copy rlst) (combinations ((+ 1 $idx) n) k (append r (list x)) true (+ 1 lvl))))))

(extend rlst (combinations ((+ 1 $idx) n) k (append r (list x)) nil (+ 1 lvl))))

)))

; rlst)))

(define (all-factors lst)

(let (r '())

(for (j 1 (length lst))

(extend r (unique (sort (combinations lst j)))))))

(define antiprime

(lambda ()

(for (i 4 maxiter)

(let (f (length (all-factors (factor i))))

(when (> f lastn)

(println i ": " f (if (prime? f) " (prime)" ""))

(setq lastn f))))))

(antiprime)

(exit)

Cavemen in bearskins invaded the ivory towers of Artificial Intelligence. Nine months later, they left with a baby named newLISP. The women of the ivory towers wept and wailed. "Abomination!" they cried.