A summary of some algorithmic problems solved by mathematical analysis

The definition of “root” on Wikipedia is as follows:

In mathematics, a number root (also known as the digit root or Digital root) is a property of natural numbers, in other words, every natural number has a number root. The number root is the sum of the various bits of a positive integer (horizontal addition), if the value after the addition is greater than 10, then continue to add the numbers horizontally until the value is less than 10, or repeat the sum of a number until its value is less than 10, then the value is the number root of the number. For example, the number root of 54817 is 7, because 5+4+8+1+7=25. If 25 is greater than 10, add it again. 2+5=7, and 7 is less than 10, then 7 is the number root of 54817.

So what is the use of roots?

The congruence of modular operations can be computed by several roots, which can save a lot of time in the case of very large numbers. The numerical root can be used as a way to check the correctness of the calculation. For example, the number root of the sum of two numbers is equal to the sum of the number roots of the two numbers. In addition, a number root can also be used to judge the divisibility of a number. If a number root is divisible by 3 or 9, the original number is also divisible by 3 or 9.

Now let’s talk about how we can figure out the roots. Let’s list the roots from 1 to 30.

Original number: 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9Copy the code

It can be found that the number of roots in a group of 9, 1-9 cycle. All we have to do is map the original to the root of the tree, and when we loop, we think of mod. Combined with this, there are three cases for a given n.

• N is 0. The roots are 0.
• N is not a multiple of 9, the root is n mod 9, n mod 9.
• N is a multiple of 9, so the root is 9.

We can unify the two cases by subtracting the given number by 1, which shifts the original number to the left by 1, mod the resulting number by 9, and add the resulting number by 1. If the original number is n, the root can be expressed as (n-1) mod 9 + 1.

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 offset: 0 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9Copy the code

So, to find the root of a number, a single line of code can be achieved, i.e(num - 1) % 9 + 1;, here is a topic, just a line of code.

public int addDigits(int num) {
    return (num - 1) % 9 + 1;
}
Copy the code

The sum of four squares theorem means that any positive integer can be represented as the sum of four square numbers. If you have less than four squares, like 12, 12, 12, you could add a 0, 0, 0 or you could view it as four squares, 12 is 4 plus 4 plus 4 plus 0. 12 is 4 plus 4 plus 4 plus 0. 12 is 4 plus 4 plus 4 plus 0. So given this theorem, for the solution they’re looking for, it can only be one, two, three, four one, two, three, four.

Legendre’s three-square theorem states that n n n does not equal 4a∗(8b+7) 4^a*(8b+7) 4A ∗(8b+7) if the positive integer n is expressed as the sum of three squares, A, a, a and b, b, b are both non-negative integers. In other words, if n==4a∗(8b+7) n==4 ^a*(8b+7) n==4a∗(8b+7), it must not be expressed as the sum of three squares, and also as the sum of one or two squares, because if it can be expressed as the sum of two squares, So I add a 0, 0, 0, and I get the sum of three squares.

One, two, and three are excluded, so if n==4a∗(8b+7) n==4 ^a*(8b+7) n==4a∗(8b+7), then n n n can only be represented as the sum of four squares. So for code, we take the exclusion approach.

• So the first thing to think about is whether the answer is 1, 1, 1, which is whether the current number is a square.
• And then we want to see if the answer is 4, 4, 4, that is, if n is equal to 4a∗(8b+7) 4^a*(8b+7) 4a∗(8b+7).
• And then you take 2, 2, 2, and you subtract a square from the current number, and you see if the difference is a square.
• So if you eliminate all of those, the answer is 3, 3, 3.

public int numSquares(int n) {
    if (isSquare(n)) {
        return 1;
    }

    int temp = n;
    while (temp % 4= =0) {
        temp /= 4;
    }
    if (temp % 8= =7) {
        return 4;
    }

    for (int i = 1; i * i < n; i++) {
        if (isSquare(n - i * i)) {
            return 2; }}return 3;
}

private boolean isSquare(int n) {
    int sqrt = (int) Math.sqrt(n);
    return sqrt * sqrt == n;
}
Copy the code