Algorithm for digit summing?

Question

I'm searching for an algorithm for Digit summing. Let me outline the basic principle:

Say you have a number: 18268.

1 + 8 + 2 + 6 + 8 = 25

2 + 5 = 7

And 7 is our final number. It's basically adding each number of the whole number until we get down to a single (also known as a 'core') digit. It's often used by numerologists.

I'm searching for an algorithm (doesn't have to be language in-specific) for this. I have searched Google for the last hour with terms such as digit sum algorithm and whatnot but got no suitable results.

See also: http://stackoverflow.com/questions/478968/sum-of-digits-in-c — e.James, Apr 21 '10 at 22:09
No, not homework. Although I can see how you would mistake it. The hardest thing we do in college to do with programming is file handling. :P — Joe, Apr 21 '10 at 22:11
And this one: http://stackoverflow.com/questions/2115731/i-want-a-function-in-vb-script-to-calculate-numerology — ire_and_curses, Apr 21 '10 at 22:14
Thanks very much ire :) And no problem aaa, I should have said it wasn't homework in the question. — Joe, Apr 21 '10 at 22:19
Your "core" is aka "digital root" http://en.wikipedia.org/wiki/Digital_root — polygenelubricants, Apr 21 '10 at 22:38

score 31 · Accepted Answer · answered Apr 21 '10 at 22:12

31

Because 10-1=9, a little number theory will tell you that the final answer is just n mod 9. Here's code:

ans = n%9;
if(ans==0 && n>0) ans=9; 
return ans;

Example: 18268%9 is 7. (Also see: Casting out nines.)

answered Apr 21 '10 at 22:12

ShreevatsaR

38,402
17
102
126

2

@Timmy: No, you don't need to loop. Get pen and paper, and work it out for yourself. (It works because the sum of digits is an invariant modulo 9.) – ShreevatsaR Apr 21 '10 at 22:18
Thanks for reminding me to analyze the problem *before* I code the obvious solution. – Noah Lavine Apr 21 '10 at 22:35
1

The "obvious" solution took most of the people here less than 5 minutes, and the running time isn't too high, so perhaps you could've done that anyhow! ;P – Larry Apr 21 '10 at 22:37
@Larry: Yes, but we could have spent those 5 minutes thinking, and finally coming to THE correct answer (which is also obvious, in a way). It's the "fastest gun in the west problem", see http://meta.stackexchange.com/questions/9731/fastest-gun-in-the-west-problem – Federico A. Ramponi Apr 21 '10 at 22:42
A much easier solution. Thank you Shree :) – Joe Apr 21 '10 at 22:45
1

I think it's important to analyze algorithms itself -- sure the brute force algorithm is slower, but how much of a factor? f(10^x-1) = 9*(x-1). So even if you have a number with a million digits it will take fractions of a second. Now, of course the numbers changes with Stack Overflow (and Google), where you can just ask someone and get it in 5 minutes, but I don't know if I would've came up with it in 5 minutes without a nudge in what I should do -- I happened to know it as trivia from experience. (A long way of saying, don't prematurely optimize if you don't have to!) – Larry Apr 21 '10 at 22:48

Grimmy · Answer 2 · 2010-04-21T22:14:15.953

3

I would try this:

int number = 18268;
int core = number;
int total = 0;

while(core > 10)
{
   total = 0;
   number = core;
   while(number > 0)
   {
      total += number % 10;
      number /= 10;
   }

   core = total;
}

edited Apr 21 '10 at 22:14

answered Apr 21 '10 at 22:08

Grimmy

836
6
16

you'll want to do this over and over until abs(total) is less than 10 and then you'll have your core number. – Chad Apr 21 '10 at 22:11
that does not seemed right. you are doing only one summation. you need another loop or recursion – Anycorn Apr 21 '10 at 22:11

score 2 · Answer 3 · answered Apr 21 '10 at 22:11

Doesn't work with negative numbers, but I don't know how you would handle it anyhow. You can also change f(x) to be iterative:

sum( x ) =
    while ( ( x = f( x ) ) >= 10 );
    return x;

f( x ) = 
    if ( x >= 10 ) return f( x / 10 ) + x % 10
    return x

You can also take advantage of number theory, giving you this f(x):

f( x ) =
    if ( x == 0 ) return 0
    return x % 9

score 1 · Answer 4 · answered Apr 21 '10 at 22:09

1

Mod the whole number by 10.
Add the number to an array.
Add the whole array.

answered Apr 21 '10 at 22:09

Jacob Saylor

2,371
1
31
46

2

+1 for providing a good starting point but not doing the OP's homework. – Bob Kaufman Apr 21 '10 at 22:10
It's not homework, Bob. :) And thank you for the starting point, I can work out in the head where it's going ;) – Joe Apr 21 '10 at 22:12

score 0 · Answer 5 · answered Apr 21 '10 at 22:14

0

int number = 18268;
int total = 0;

while(number > 0)
{
   total += number % 10;
   total = total%10;
   number /= 10;
}

answered Apr 21 '10 at 22:14

Kasturi

3,335
3
28
42

score 0 · Answer 6 · answered Oct 12 '16 at 15:07

this is from a really long time ago, but the best solution i have for this is:

int digitSum(int num){
    if (num < 10) return num;
    else return (n-1)%9+1;
}

I don't know how much better this is,but it will account for the divisible by 9 numbers easily. Just a cool algorithm.

score 0 · Answer 7 · answered Aug 27 '18 at 18:57

    private static int sum(long number) {
    int sum = 0;
    if (number == 0) {
        return 0;
    }
    do {
        int last = (int) (number % 10);
        sum = (sum + last) % 9;
    } while ((number /= 10) > 0);

    return sum == 0 ? 9 : sum;
}

score 0 · Answer 8 · answered Dec 18 '18 at 05:54

0

public int DigitSum(long n)
  {
     return (int)(1 + (n - 1) % 9);
  }

answered Dec 18 '18 at 05:54

Itay Tur

683
1
15
40

Algorithm for digit summing?

8 Answers8

Linked