aliquote.org

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)
      null
      (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.

[2024-01-19]
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