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.shtml
Also, 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.