Triperfect Numbers

April 23, 2019

This is easy enough if we steal some number-theory code from previous exercises:

(define (triperfect)
  (do ((n 1 (+ n 1))) (#f)
    (when (= (apply + (divisors n)) (* 2 n))
      (display n) (newline))))
> (triperfect)
120
672
523776
...

It takes a while to find all six. While we are waiting, we can write a function to find k-multiperfect numbers where σn = k n:

(define (multi-perfect k)
  (do ((n 1 (+ n 1))) (#f)
    (when (and (pre-qualify n)
               (= (apply + (divisors n)) (* k n)))
      (display n) (newline))))

To make things go faster, and because all of the multiperfect numbers are highly composite, we pre-qualify n to discard obviously non-multiperfect numbers:

(define (pre-qualify n)
  (let ((wheel (vector 1 2 2 4 2 4 2 4 6 2 6)))
    (let loop ((n n) (f 2) (w 0))
      (cond ((< n (* f f)) #t)
            ((< 200 f) #f)
            ((zero? (modulo n f))
              (loop (/ n f) f w))
            (else (loop n (+ f (vector-ref wheel w))
                        (if (= w 10) 3 (+ w 1))))))))

The constant 200 can be modified as desired. We get a little bit farther this time:

> (multi-perfect 3)
120
672
523776
459818240
...

And here are some 4-multiperfect numbers:

> (multi-perfect 4)
30240
32760
2178540
...

You can run the program at https://ideone.com/H4dCfY. MathWorld has a good page at http://mathworld.wolfram.com/MultiperfectNumber.html.

Advertisements

Pages: 1 2

4 Responses to “Triperfect Numbers”

  1. Pascal Bourguignon said
    
    (ql:quickload :bordeaux-threads)
    
    (defun triperfectp (n)
      (= (reduce (function +) (divisors n))
         (+ n n n)))
    
    (defstruct triperfect
      (current 0)
      (numbers '())
      (start-time 0)
      (error nil))
    
    (defparameter *triperfects* (make-triperfect))
    
    (defun search-triperfect-numbers ()
      (bt:make-thread
       (lambda ()
         (handler-case
             (loop
               :for n :from (triperfect-current *triperfects*)
                 :initially (setf (triperfect-start-time *triperfects*) (get-universal-time))
               :do (setf (triperfect-current *triperfects*) n)
               :when (triperfectp n)
                 :do (push n (triperfect-numbers *triperfects*)))
           (error (err)
             (setf (triperfect-error *triperfects*) err))))
       :name "Triperfect Search"))
    
    (defun triperfect-numbers-found-so-far ()
      (let ((duration     (if (zerop (triperfect-start-time *triperfects*))
                              nil
                              (- (get-universal-time) (triperfect-start-time *triperfects*))))
            (n            (triperfect-current *triperfects*))
            (triperfects  (triperfect-numbers *triperfects*))
            (error        (triperfect-error *triperfects*)))
        (format t "~&~:[~;;; After ~:*~A second~:*~P, ~]scanning up to ~D, we have found ~A triperfect number~:*~P~:[~;: ~:*~{~A~^, ~}~].~%"
                duration n (length triperfects) triperfects)
        (if error
            (format t ";; The search aborted with the error ~A~%" error)
            (format t ";; The search continues.~%"))
        (finish-output)
        triperfects))
    
    (progn
      (search-triperfect-numbers)
      (sleep 60)
      (triperfect-numbers-found-so-far)
      (sleep 60)
      (triperfect-numbers-found-so-far))
    ;; After 60 seconds, scanning up to 855906, we have found 3 triperfect numbers: 523776, 672, 120.
    ;; The search continues.
    ;; After 120 seconds, scanning up to 1410357, we have found 3 triperfect numbers: 523776, 672, 120.
    ;; The search continues.
    ;; (523776 672 120)
    (triperfect-numbers-found-so-far)
    ;; After 258 seconds, scanning up to 2425768, we have found 3 triperfect numbers: 523776, 672, 120.
    ;; The search continues.
    (523776 672 120)
    
    
  2. Pascal Bourguignon said

    Oh, com.informatimago.common-lisp.arithmetic.primes:divisors is found in https://github.com/informatimago/lisp/blob/master/common-lisp/arithmetic/primes.lisp

  3. Daniel said

    Here’s a solution in C that uses trial division to find factors. It would seemingly take a long time using this implementation to find the six triperfect numbers.

    @programmingpraxis, can you elaborate on your “pre-qualify” filter? Your solution says “all of the multiperfect numbers are highly composite”, but the second triperfect number, 672, is not a highly composite number (according the the Wikipedia definition of highly composite, aka “anti-prime”, numbers).

    #include <stdint.h>
    #include <stdlib.h>
    #include <stdio.h>
    
    typedef uint64_t u64;
    
    int main(void) {
      for (u64 x = 1; ; ++x) {
        u64 sum = 0;
        for (u64 y = 1; y * y <= x; ++y) {
          if (x % y == 0) {
            sum += y;
            u64 z = x / y;
            if (z != y)
              sum += z;
          }
        }
        if (sum == 3 * x)
          printf("%lu\n", x);
      }
      return EXIT_SUCCESS;
    }
    

    Output:

    $ ./a.out
    120
    672
    523776
    ...
    
  4. Paul said

    @Daniel: I will answer for @programmingpraxis. All the triperfect numbers are similar to highly composite numbers. They all look like 2^nprime1prime2….. with all primes below 160. The triperfect numbers are no hcn though. Knowing this you can factorise the numbers with low prime numbers only (prequalify). Another trick is to search the sequence a, 2a, 3a, 4a, .. with a=2^n. In this way you can find even the highest triperfect numbers very quickly. I feel it is kind cheating though, as long as you cannot proof mathematically that triperfect numbers should behave like that.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: