aliquot

< a quantity that can be divided into another a whole number of time />

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 Lips implementation of the CRC algorithm, here and there.

math scheme euler

See Also

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