A Rule of Divisibility by 13

Question

A Rule of Divisibility by 13

When you divide the successive powers of 10 by 13 you get the following remainders of the integer divisions:

1, 10, 9, 12, 3, 4.

Then the whole pattern repeats.

Hence the following method: Multiply the right most digit of the number with the left most number in the sequence shown above, the second right most digit to the second left most digit of the number in the sequence. The cycle goes on and you sum all these products. Repeat this process until the sequence of sums is stationary.

Input Format

An integer greater than or equal to 0 into a function thirt contained within a class Thirteen.

Output Format

Returns an integer value: the stationary number described above.

To complete the all my test cases one hundred thousand times, it takes 4.7181s on average of 10 tries. Although this is a decent result for 1.1 million calls of my function, which gives an average of 4.28918μs per function call, but I'm still a beginner, and I think there is a lot I could do to improve the style, consistency, readability, and efficiency of my code.

I've included many additional comments expressing my main concerns in the code below, though any constructive criticism would be very appreciated.

I wrote this code some time back - uncommented - so there is a section around the middle where I feel things are very dirty, and I don't really understand it, if anyone could shed some light on that it would be great.

Any and all comments would be very appreciated, I want to know exactly what I should do to improve my skills, even if it involves rewriting the entire code.

#include <vector>
#include <cassert>


class Thirteen {
    public:
        static long long thirt (long long number);
        static const std::vector<int> set;
};

// Given set of remainder numbers when powers of 10
// starting from 10^2 are divided by 9, repeating at 10^8.
const std::vector<int> Thirteen::set = {1, 10, 9, 12, 3, 4};

long long Thirteen::thirt (long long number) {
    // Set the original for use later, is there a cleaner way of doing this?
    long long original = number;

    // Organize the numbers into a vector of its digits in reverse order.
    std::vector<int> digits = {};
    while (number > 0) {
        // Get final digit.
        int digit = number % 10;
        // Insert final digit into the end of the vector.
        digits.push_back (digit);
        // Remove final digit from the number.
        number /= 10;
    }

    // Create a vector of the products of each digits by their respective multiplier.
    std::vector<int> products = {};
    int iteration = 0;
    // Keep on multiplying until the set runs out.
    while (digits.size() > 0) {
        // Add the multiplied digit to the products vector:
        // - get the digit from the vector set by the iteration number
        // - get the multiplier from the iteration modulo the multiplier set size
        // - multiply them together and push them to the products vector
        products.push_back (digits[iteration] * set[iteration % set.size()]);

        // I have no idea how this part works, it just does, and I need help.
        // I'm removing the last digit even though I'm iterating from
        // the front to the end, and checking the size it is sometimes less
        // than the iteration variable, yet the underlying digits vector
        // does not throw an out of range exception, it works, but how?
        digits.pop_back();

        // Iterate to continue to the next digit.
        iteration++;
    }

    // Calculate the total through iterating through the products vector,
    // and adding all the products together
    int total = 0;
    for (int product : products) {
         total += product;
    }

    // Check if the total is equal to the original set before,
    // end the function and return the value if it is,
    // otherwise, go through another iteration of the function.
    // This area seems dirty, I feel like there are much better ways of doing this, any help?
    if (total == original) {
        return original;
    } else {
        return Thirteen::thirt (total);
    }
}

// TEST CASES BELOW
void Test (int ans, int sol) {
    assert(ans == sol);
}

int main () {
    for (int i = 0; i < 100000; i++) {
        Test(Thirteen::thirt(87), 87);
        Test(Thirteen::thirt(0), 0);
        Test(Thirteen::thirt(8529), 79);
        Test(Thirteen::thirt(85299258), 31);
        Test(Thirteen::thirt(5634), 57);
        Test(Thirteen::thirt(1111111111), 71);
        Test(Thirteen::thirt(987654321), 30);
        Test(Thirteen::thirt(1314050335), 39);
        Test(Thirteen::thirt(1140681280), 37);
        Test(Thirteen::thirt(1449166222), 49);
        Test(Thirteen::thirt(1069756634), 11);
    }
}

Answer 1

You don't need additional memory. You can traverse the number and get your result at the same time:

long long Thirteen::thirt (long long number) {
    const long long original = number;

    long long result    = 0;
    std::size_t set_pos = 0;

    while (number > 0) {
        const auto qr = std::lldiv(number, 10);
        result += qr.rem * set[set_pos];
        set_pos = (set_pos + 1) % set.size();

        number = qr.quot;
    }

    return result == original ? result : third(result);
}

This doesn't need the additional memory and uses std::lldiv to calculate both number % 10 and number / 10 at the same time, although you could check whether your compiler optimizes both variants to the same assembler.

Note that your digits.pop_back() actually yields undefined behaivour. The digits.size() has decreased, but digits.capacity() hasn't, so the memory is still allocated. But the index is out of bound. operator[] will never throw an exception, though, that's std::vector::at's job.

However, there are two general things off with your code. First of all, you're using a class for just a single function. Don't. Just write that function. I guess this is part of the assignment, but unless you have some template parameter quirks or other circumstances, using a function is a lot simpler:

long long thirteen(long long number){
   ...
}

Next, use std::array instead of std::vector if you know the size of the collection at compile time:

static const std::array<int,6> thirteen_set = {1, 10, 9, 12, 3, 4};

If you don't want to pollute the global namespace, use a namespace instead.