Digit Sum

July 8, 2019

A lot of Euler problems amount to find the sum of digits in a given numbers. The digit sum is easy to compute using Lisp or Scheme, provided you convert the number at hand into a list or as a string, then as ascii-decoded character: (char->integer #\1) returns 49 in Racket so it is quite easy to write a little helper function to convert any character into its corresponding integer value.

However, if you prefer to keep working with numbers, here is a little function that will convert any number into a list of digits. It is then a matter of applying foldr or apply to this list to compute any quantity of interest, e.g., the sum of all digits:

(define (digits n)
  (if (zero? n)
      (cons (remainder n 10) (digits (quotient n 10)))))

A more general formula to compute the digit sum of $x$ in base $b=10$ is:

$$ \sum_{n=0}^{\lfloor\log_{10}x\rfloor}\frac{1}{10^n}(x, \textrm{mod}, 10^{n+1}-x, \textrm{mod}, 10^n). $$

This is widely used in checksum algorithms, for instance the Luhn number checksum, also called the mod-10 algorithm. Here it is in Scheme:

(define (mod-10 x n)
  (- (modulo x (expt 10 (add1 n))) (modulo x (expt 10 n))))

(define (digit-sum x)
  (for/list ([i (in-range (ceiling (log x 10)))])
    (* (/ 1 10) (mod-10 x i))))

A related idea can be found in the CRC error checking algorithm. There are various Lisp implementation of the CRC algorithm, here and there.

Mathematica 14 now has its own DigitSum function.

See Also

» Euler Problems 1-10 » On premature optimization » Petit précis à déguster » Quadratic Equation and the Evil of Floating Point » Category Theory