How can I find the sum of the digits of a positive integer in GAP?

Question

(I eventually found the answer to this question after writing it. But just in case anyone finds this useful, or has an alternative or better answer, I'll ask and answer my own question.)

After seeing slick Mathematica code for the question Probability of random integer's digits summing to 12, I found myself stumped as to how to sum the digits of a positive integer in GAP.

Question: How can I find the sum of the digits of a positive integer in GAP?

Thus far, I've used my own code when required:

DecimalDigits:=function(n)
  if(n=0) then
    return [];
  else
    return Concatenation(DecimalDigits(Int(n/10)),[n mod 10]);
  fi;
end;;

In this format, e.g. DecimalDigits(1234) returns the array [ 1, 2, 3, 4 ] which can be summed by Sum(DecimalDigits(1234)). But, I'm hoping there is a better way to do this (particularly in the newer versions of GAP).

The DigitsNumber function returns a string, on which Sum doesn't work.

Answer 1

Thank you, Douglas. I would like to add some remarks, but it seems like I can't include GAP code conveniently in comments, and can't fit them in the length limit. Thus, let me post them as an answer :)

1) I think that ListOfDigits is meant to be a utility function for small inputs. If one really wants to compute sums of digits more efficiently, one could start with looking what ListOfDigits is doing and then write an own SumOfDigits function.

In the following GAP session we compare the performance of SumOfDigits vs.Sum(ListOfDigits(...)) approach:

gap> SumOfDigits:=function(a)
> local s, b;
> if not a in NonnegativeIntegers then 
>   Error("a must be a non-negative integer");
> fi;
> s:=0;
> while a<>0 do
>   b:=a mod 10;
>   s:=s+b;
>   a:=(a-b)/10;
> od;
> return s;
> end;
function( a ) ... end
gap> ForAll([1..10000],i->SumOfDigits(i)=Sum(ListOfDigits(i)));
true
gap> for i in [1..1000000] do x:=SumOfDigits(i); od; time;
1426
gap> for i in [1..1000000] do x:=Sum(ListOfDigits(i)); od; time;
3560
gap> for i in [1..10000000] do x:=SumOfDigits(i); od; time;
16364
gap> for i in [1..10000000] do x:=Sum(ListOfDigits(i)); od; time;
38255

Clearly, SumOfDigits doesn't have to store an intermediate list of digits, handling which becomes more and more expensive with larger inputs.

2) The new version of GAP indeed may show better performance in this example if compared with GAP 4.4.12, since starting from GAP 4.5 by default the GAP kernel uses the GMP library for faster integer arithmetic.

3) I haven't compared the performance of the DecimalDigits function given above, but I have observed that it will not work for large inputs:

gap> Length(DecimalDigits(10^4997));
4998
gap> DecimalDigits(10^4998);;
Error, recursion depth trap (5000)
 in
  return Concatenation( DecimalDigits( Int( n / 10 ) ), [ n mod 10 ] ); called from 
DecimalDigits( Int( n / 10 ) ) called from
DecimalDigits( Int( n / 10 ) ) called from
DecimalDigits( Int( n / 10 ) ) called from
DecimalDigits( Int( n / 10 ) ) called from
DecimalDigits( Int( n / 10 ) ) called from
...  at line 57 of *stdin*
you may 'return;'
brk> 

where SumOfDigits will work. (The recursion depth trap error is a special error in GAP preventing it from running into an infinite recursion). Also please note that the GAP Tutorial chapter on Functions says: "Regardless of the recursive structure of an algorithm it is often cheaper (in terms of computing time) to avoid a recursive implementation if possible (and it is possible in this case), because a function call is not very cheap."

4) Of course, in the last example with 10^n one does not need to ask any system what the sum of digits is :)

Answer 2

The ListOfDigits function in GAP converts a positive integer into the corresponding list of decimal digits.

For example ListOfDigits(1234); returns [ 1, 2, 3, 4 ]. After which the sum of the digits can be found as usual: Sum(ListOfDigits(1234));.

Here's the result of ?ListOfDigits (ref.; 14.2-11):

  14.2-11 ListOfDigits

  ‣ ListOfDigits( n ) ────────────────────────────── function

  For  a  positive  integer n this function returns a list l,
  consisting of the digits of n in decimal representation.

  ────────────────────────  Example  ────────────────────────
    gap> ListOfDigits(3142);   
    [ 3, 1, 4, 2 ]
  ───────────────────────────────────────────────────────────