2

I'm trying to make a function that returns a list of perfect numbers:

A perfect number is a positive integer that is equal to the sum of its proper positive divisors

For instance, 28 is perfect because its factors are 1, 2, 4, 7, 14 and 1 + 2 + 4 + 7 + 14 = 28.

My initial code was:

(defun factors (n)
  "Return a list of the factors of N, except N itself."
  (let ((factors (list 1))
        (i 2))
    (while (<= i (/ n 2))
      (if (zerop (% n i))
          (setq factors (cons i factors)))
      (setq i (1+ i)))
    factors))

(defun is-perfect (n)
  "Return `t` is N is a perfect number, `nil` otherwise."
  (and (/= 1 n)
       (let* ((factors (factors n))
              (factors-sum (seq-reduce '+ factors 0)))
         (= n factors-sum))))

(defun perfect-numbers (n)
  "Return the perfect numbers smaller than or equal to N."
    (seq-filter 'is-perfect (number-sequence 2 n)))

It works, but gets noticeably slow for 10000. Remembering that I recently had trouble with a self modifying function I thought I'd try to exploit this to optimize perfect-numbers. The idea is to keep the list of the perfect numbers we already computed. I tried this:

(defun perfect-numbers (n)
  "Return the perfect numbers smaller than or equal to N."
  (let* ((perfect-numbers '(6)) ; my hope was that this list would get updated each time I call the function
         (highest (car (last perfect-numbers)))
         (new-perfect-numbers (seq-filter 'is-perfect (number-sequence (1+ highest) n))))
    (setq perfect-numbers (append perfect-numbers new-perfect-numbers))
    (seq-filter (apply-partially '>= n) perfect-numbers)))

However in this case, perfect-numbers does not seems to be updated, and I don't understand why:

ELISP> (perfect-numbers 1000)
(6 28 496)
ELISP> (symbol-function 'perfect-numbers)
(lambda
  (n)
  "Return the perfect numbers smaller than or equal to N."
  (let*
      ((perfect-numbers
        '(6)) ; the list did not get updated :(
       (highest
        (car
         (last perfect-numbers)))
       (new-perfect-numbers
        (seq-filter 'is-perfect
                    (number-sequence
                     (1+ highest)
                     n))))
    (setq perfect-numbers
          (append perfect-numbers new-perfect-numbers))
    (seq-filter
     (apply-partially '>= n)
     perfect-numbers)))
  • 2
    Little-known fact: "self-modifying code" is a synonym for "maddening to debug". Better use explicit memoization. – wasamasa May 23 at 17:26
4

This is because you modify the variable binding, not the data structure. append creates a fresh list, while nconc modifies its argument. Replace (setq perfect-numbers (append perfect-numbers new-perfect-numbers)) with (nconc perfect-numbers new-perfect-numbers) and you will get the behavior you think you want.

I must advise against this though because

  1. modifying quoted lists is not a good idea.
  2. You have to seed your variable with (6) which is poor style.

I suggest a more standard way to encapsulate the data (see Lexical-Binding):

;; -*- lexical-binding:t -*-
(let ((perfect-numbers ()))
  (defun perfect-numbers (n)
    "Return the perfect numbers smaller than or equal to N."
    (let ((new-perfect-numbers
           (seq-filter 'is-perfect (number-sequence
                                    (if perfect-numbers
                                        (1+ (car (last perfect-numbers)))
                                        2)
                                    n))))
      (setq perfect-numbers (append perfect-numbers new-perfect-numbers))
      (seq-filter (apply-partially '>= n) perfect-numbers))))

Now (perfect-numbers 100) returns (6 28) as expected.

  • Thank you, nconc does solve the problem. However the better solution you provide does not work for me, I get *** Eval error *** Symbol’s value as variable is void: perfect-numbers. I did set lexical-binding to t in ielm. – little-dude May 23 at 15:28
  • Oh, it works if I copy paste the code in the interpreter actually, but not if I put it in my source file and then do C-x C-e or M-x eval-buffer. – little-dude May 23 at 15:30
  • Nevermind: things work well if I do M-: (setq lexical-binding t), and then re-evaluate the form. Setting it only in ielm does not seem to work. – little-dude May 23 at 15:38
  • 1
    My understanding is that having ;; -*- lexical-binding:t -*- as a file-local variable in the library which defines your function is the only dependable way to enable lexical binding. (Although ielm and M-: and *scratch* will default to lexical binding starting from Emacs 27.) – phils May 23 at 21:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.