Checking for harshad numbers

[jjordan33]

Hi,

I'm trying to write a program that will take in an integer N, then, starting from N, loop to a limit of 1 billion, printing the first harshad number that is greater than or equal to N.

A quick explanation of a harshad number is any number than is divisible by the sum of its digits. e.g. 156 (1+5+6)= 12 (156/12)= 13.

e.g.
24 would output 24 since 24 / 6 = 4.
25 would output 27 since 27 / 9 = 3 and it's the next harshad number after 25.

However, my code only checks to see if N is a harshad number. If it is, it will print it out, otherwise it's in an infinite loop.

I'm dealing with unsigned long long ints and converting back and forth from strings, which, I'm very unfamiliar with. I've provided some comments, but I am sure I am not explaining things properly, so I'll address any confusion.

Can anyone help me see why my code won't loop until it finds the next number that's a harshad number?

#include <iostream>
#include <string>

using namespace std;

int main(){

    unsigned long long int sumofdigits = 0; // this will add up the digits of 
    
                                        //number. e.g. 24 = 6
    string numtostring;
    unsigned long long int tot;
    
    cin >> tot;


    for (unsigned long long int k = tot; k < 1000000000 + 1; k++) {
        string g = to_string(k); // i don't know how to add integer digits 
                                 //together so I turn it into a temp string
        
        string pw[g.length()]; //create an array to store the individual 
                               //elements of the integer to string
        
        for (unsigned long long int i = 0; i < g.length(); i++){
            pw[i] = g[i]; // filling the array with the digits separated
        }
        
        unsigned long long int yy[g.length()]; // an array to turn them back 
                                               //into separate integers

        for (unsigned long long int i = 0; i < g.length(); i++) {
            yy[i] = stoull(pw[i]); // converting them and storing them
        }
        
        for (unsigned long long int i = 0; i < g.length(); i++) {
            sumofdigits += yy[i]; // e.g. turning 24 into 2 + 4 = 6
        }
       
        if (k % sumofdigits == 0){ // checking to see if harshad number. e.g. 
                                   //24 % 6 = 0
            cout << k;
            return 0;
        }
    }
}

**This is not homework.It's not a ranked competition. It's a practice challenge from a programming challenge site designed to help students learn to think the way they will need to think in the workforce.**

[JLBorges]

Brute force:

#include <iostream>

unsigned int sum_digits( unsigned int number )
{
    if( number < 10 ) return number ;
    else return number%10 + sum_digits( number/10 ) ;
}

bool is_harshad_number( unsigned int number )
{ return number % sum_digits(number) == 0 ; }

int main()
{
    unsigned int n ;
    // std::cout << "number? " ;
    std::cin >> n ;

    while( !is_harshad_number(n) && n < 1'000'000'000 ) ++n ;

    std::cout << n << '\n' ;
} 

[dutch]

The harshad numbers seem to be dense enough that a brute force algorithm is perhaps best. Even in the final million of the billion range there are 45282, or about 1 in 22; the density of the first million is about 1 in 10. Discovering a "clever" algorithm is complicated by the "sum of the digits" being difficult to relate to prime factors (which play into the modulus being 0, which occurs when the prime factors of rhs are a subset of those of lhs).

The only simple speed-up I can think of is to note that since we are processing numbers in sequence, 9 times out of 10 the sums simply increment by 1, which is a lot less work than calculating the sum from scratch. Every 10th time you need to deal with the weird rollover (which seems to involve a cascade of rollover points, one for each digit level, if you see what I mean).

If the task is to find the next harshad number then it's possible that even the most efficient implementation of the above wouldn't be a net gain.

However if the task is to count the number of harshad's from 1 to a billion it might be worthwhile (but is it really? you could run your current code in a few minutes; and it could be easily sped up by eliminating the non-tailwise recursion). The speed-up of the above is presumably quite a bit since no matter how much work (within reason) the rollover is, 9 iterations out of 10 the summation is just an increment and test.

This code goes up to (but not including!) 100. To go above that (up to but not including 1000) you can add a second-level rollover -- or is there a simpler way? Since you need a rollover level for each digit level, presumably an array is the way to go.

#include <iostream>
#include <iomanip>

int main()
{
    int count = 0;
    int sum = 0, rollover = 9;

    for (int n = 1; n < 100; ++n)
    {
        if (++sum > rollover)
        {
            sum -= 9;
            ++rollover;
        }

        std::cout << std::setw(6) << n << std::setw(10) << sum << '\n';

        if (n % sum == 0) ++count;
    }
    std::cout << count << '\n';
}

[dutch]

Code I came up with to generalize the digit sum code above.

#include <iostream>
#include <iomanip>
#include <algorithm>

template<typename T, size_t N> size_t Size(T(&)[N]) { return N; }

// For testing
int sum_digits(unsigned n) {
    int sum = 0;
    for ( ; n; n /= 10) sum += n % 10;
    return sum;
}

int main()
{
    int limits[ 11 ] = { 0 }; // limits[0] is the digit sum
    for( int i = 1; i < int(Size(limits)); ++i ) limits[ i ] = 9 * i;

    for( int n = 1; n <= 100000000; ++n ) // one hundred million
    {
        ++limits[ 0 ];
        for( int i = 1; limits[ i - 1 ] > limits[ i ]; ++i )
        {
            std::move_backward( limits, limits + i, limits + i + 1);
            limits[ 0 ] -= 9;
        }

#if 1 // deactivate this to test speed
        if( limits[ 0 ] != sum_digits( n ) )
        {
            std::cerr << "mismatch: "
                      << n             << ", "
                      << limits[ 0 ]   << ", "
                      << sum_digits(n) << "\n";
            return 1;
        }
#endif

#if 0
        std::cout << std::setw(6) << n << std::setw(10) << limits[ 0 ] << '\n';
#endif
    }
}

[highwayman]

What if instead you just check whether any digit is a zero and if not you do the add? Wouldn’t that work for all types of roll over? Because it always adds to the sum until one thing turns zero. But if it’s multiple digits it is relative to the number digit it is. So.

9 to 10, (or any tens digit), - 0 to count.
99 to 100(or and hundreds digit) - 1 to count.

So minus 1 per digit over one digit.

Edit >> maybe I’ll send an actual example at some point but don’t expect it.(sry?)

[dutch]

You need to implement it. The devil's in the details.

[highwayman]

Yup... 😓 currently working on it, but honestly the OP seems smart, this is a directed at a person yes? I’m working on it currently, but why wouldn’t they work on it too, ya know?

[dutch]

Don't worry about it. If you actually get your algorithm working and tested, post it.

[JLBorges]

#include <iostream>
#include <ctime>
#include <cassert>

unsigned int sum_digits( unsigned int number ) // brute force
{
    if( number < 10 ) return number ;
    else return number%10 + sum_digits( number/10 ) ;
}

unsigned int num_trailing_zeroes( unsigned int n )
{
    if( n%10 != 0 ) return 0 ;
    else return 1 + num_trailing_zeroes(n/10) ;
}

// sum digits using sum digits of the previous number
unsigned int sum_digits( unsigned int n, unsigned int sum_digits_nm1 )
{ return sum_digits_nm1 + 1 - 9 * num_trailing_zeroes(n) ; }

int main()
{
   const unsigned int N = 1'000'000'000 ;
   const unsigned int M = N + 100'000'000 ;
   
   // compule sum digits for numbers in [N,M)     

   unsigned long long v1 = 0 ;
   unsigned long long v2 = 0 ;

   {
       unsigned int s = sum_digits(N-1) ;

       const auto start = std::clock() ;
       for( unsigned int i = N ; i < M ; ++i )
       {
           s = sum_digits( i, s ) ;
           v1 += s ;
       }
       const auto finish = std::clock() ;
       std::cout << "  formulaic: " << (finish-start) * 1000.0 / CLOCKS_PER_SEC
                 << " millisecs\n" ;
   }

   {
       const auto start = std::clock() ;
       for( unsigned int i = N ; i < M ; ++i ) v2 += sum_digits(i) ;
       const auto finish = std::clock() ;

       std::cout << "brute force: " << (finish-start) * 1000.0 / CLOCKS_PER_SEC
                 << " millisecs\n" ;
   }

   assert( v1 == v2 ) ; // sanity check
   std::cout << v1 << ' ' << v2 << '\n' ;
} 

http://coliru.stacked-crooked.com/a/cfb6f2e9fb7b564d

[dutch]

One wonders if you are cheating by not counting the time required to calculate the starting sum (which you could of course use your new "trailing zeroes" algo to calculate instead of the brute force one).

As my algo cannot yet deal with a starting value > 1, I set N to 1. That way the initial sum for your algo is 0 and the initial limits array for mine is also simple.

Running the algos separately (to eliminate any difference order might make) for N = 1, M = 500'000'000 shows mine to be 20 to 30% faster.

[JLBorges]

I began with a starting value of greater than one for two reasons:

a. That is what the original problem 'the first harshad number that is greater than or equal to N' requires.
b. The brute force method is more biased in favour of numbers with fewer digits.

[dhayden]

Regarding the original question. The problem with your code is that you don't reset sumofdigits to zero inside the loop. To fix this, just move lines 8-10 after line 17.

You can greatly simplify the code by getting the sum of digits in a simple loop:

        unsigned long long int sumofdigits = 0; 
        for (num=k; num; num /= 10) {
            sumofdigits += num % 10;
        }

Each time through the loop we peel of the last digit of num with num%10 and add that digit to sum of digits. Then we divide num by 10 to get rid of that digit and repeat the process.

With this change your program becomes:

#include <iostream>
#include <string>

using namespace std;

int
main()
{

    string numtostring;
    unsigned long long int tot;

    cin >> tot;

    for (unsigned long long int k = tot; k < 1000000000 + 1; k++) {
        unsigned long long int sumofdigits = 0; // this will add up
                                                // the digits of
                                                // number. e.g. 24 = 6
        for (num = k; num; num /= 10) {
            sumofdigits += num % 10;
        }

        if (k % sumofdigits == 0) {              // checking to see if
                                                 // harshad
                                                 // number. e.g. 24 % 6 = 0
            cout << k;
            return 0;
        }
    }
}

[dutch]

I began with a starting value of greater than one for two reasons

I understand why you did it, I just didn't think it was fair to leave the calculation of the starting sum out of the timing. How is that a fair comparison?

Anyway, using your ranges of 1 billion to 1.1 billion and timing the whole algorithm (including the "run up" using that same algorithm), the timings of both our algorithms are about the same:

trailing_zeroes:
  g++    : 2933.96 ms
  clang++: 2426.29 ms
limits_array:
  g++    : 2721.33 ms
  clang++: 2424.66 ms
brute_force:
  g++    : 2785.43 ms
  clang++: 3285.41 ms

So apparently mine is faster than yours at smaller ranges, about equal around this point, and will be surpassed by yours as the range gets higher and higher. And brute force is even competitive here.

[lastchance]

Summing by brute force seems to be massively speeded up if you pre-compute the first 1000 (say) and then recurse on factors of 1000 rather than 10:

int sumnum[1000];
// pre-compute sumnum;

unsigned int sum_digits( unsigned int number ) // brute force
{
    if( number < 1000 ) return sumnum[number] ;
    else return sumnum[number%1000] + sum_digits( number/1000 ) ;
}

[highwayman]

That definitely seems a bit like cheating though doesn’t it? Shouldn’t we assume it’s the first time each time? Besides wouldn’t the pre calculation slow things down and possibly even double the work? Or are you saying that array is explicitly initialized with specific values?

[dutch]

Even including the precomputation in the timing, its about 4 times faster than the previous version, jumping into a solid lead.

[highwayman]

Huh.. okay yeah that is pretty sick