507. The perfect number

1, dry

For a positive integer, we call it a “perfect number” if it is equal to the sum of all the positive factors except itself.

Given an integer n, return true if it is perfect, false otherwise

Example 1:

Input: num = 28 Output: true Explanation: 28 = 1 + 2 + 4 + 7 + 14 1, 2, 4, 7, and 14 are all positive factors of 28.

Example 2:

Input: num = 6 Output: true

Example 3:

Input: num = 496 Output: true

Example 4:

Input: num = 8128 Output: true

Example 5:

Input: num = 2 Output: false

Tip:

  • 1 <= num <= 10^8

2

[1, num\ SQRT {num}num] =1, num\ SQRT {num}num] =1, num\ SQRT {num}num] =1

3, code,

var checkPerfectNumber = function (num) {
    let sum = 1;
    for (let i = 2; i * i <= num; i++) {
        if (num % i === 0) sum += i + num / i;
    }
    return num === 1 ? false : sum === num;
};
Copy the code


4, confused

The problem is simple, finding all the positive integer factors of a positive integer just goes all the way to n\ SQRT {n}n and keeps that in mind. If you use mathematical induction, you can easily derive this conclusion from a few examples.

If n{n}n has a factor DDD greater than n\ SQRT {n}n, then it must have a factor nd\dfrac{n}{d}dn less than n\ SQRT {n}n. That is, n{n}n factors always come in pairs.

However, there are two key questions that always make people confused: 1, why is the end of the traversal n\ SQRT {n}n, 2, whether there is a special case whose factor is greater than n\ SQRT {n}n and has not been found. You can actually solve these puzzles by doing a derivation in high school math. The process is a little bit tedious, so if you’re not interested in the process you can just look at the final conclusion.

5, derived

Suppose you want to find all the positive integer factors XXX and yyy of the positive integer NNN. (Note: the following deduction only considers cases in the positive integer range.)

Xy =nxy=nxy=n, transpose y=nxy=\dfrac{n}{x}y=xn.

Inverse proportional function

If this function looks familiar, it’s the inverse of a high school math textbook. Taking y=4xy=\dfrac{4}{x}y=x4 as an example, the graph is as follows:



It is easy to see from the figure above that the integers x’x ‘x ‘x ‘and y’y ‘y’ corresponding to any coordinate (x’,y’)(x ‘,y’) on the inverse proportional function are factors of 444. This is consistent with the official solution that n{n}n’s factors always come in pairs. So if you find one factor x’x ‘x ‘, you must find another factor y’y ‘y ‘.

Symmetry of the inverse proportional function

The image of inverse proportional function is an axisymmetric graph with y=xy=xy=x symmetry (symmetry characteristics of inverse proportional function). Taking y=4xy=\dfrac{4}{x}y=x4 as an example, the graph is as follows:

About y = y = y = x symmetrical two points, they are the coordinates of XXX and yyy swaps, namely arbitrary coordinates (x ‘, ‘) y (x, y ‘) (x ‘, ‘y) symmetric point to (y’, ‘) x (y, x ‘) (y ‘, x ‘). For example: it’s easy to see from the above graph coordinates (4, 1) (4, 1) (4, 1) symmetrical about y = y = y = x point is (1, 4) (1, 4) (1, 4).

Any factors on the available NNN (x ‘, ‘y) (x, y’) (‘ x, y ‘) is about y = y = y = x symmetry properties.

And y = y = y = x and y = nxy = \ dfrac {n} {x} : QQQ y = xn node (n, n) are the coordinates of (\ SQRT {n}, \ SQRT {n}) (n, n).

Finally, assuming that traverse the factor when access from XXX axis, the intersection of the arbitrary point appeared: QQQ left upper (x ‘, ‘) y (x, y ‘) (x ‘, ‘) y (where x ‘< nx’ < \ SQRT {n} ‘x and y’ > < n ny ‘> \ SQRT {n} y’ > n), Both appear on the lower right side of the intersection as (y’,x’)(y ‘,x’)(y ‘,x’).

That is to say, iterating over factors greater than n\ SQRT {n}n is essentially iterating over factors less than n\ SQRT {n}n, only XXX, YYy transpose the pair of factors found when less than n\ SQRT {n}n.

Therefore, all factors can be found by traversing n\ SQRT {n}n, and there is no special factor greater than n\ SQRT {n}n that has not been found, which explains the two puzzles mentioned above.

For example

N = n = 36 n = 36 36 factors on is 4 (1) (1, 4) 4 (1) (2), 16 (2), 16 (2), 16 (3, 12) (3, 12) (3, 12) (4, 9) (4, 9) (4, 9) (6, 6) (6, 6) (6, 6) (9, 4) (9, 4) (9, 4) (12, 3) (12, 3) (12, 3) (18, 2) (18, 2) (18, 2) (36, 1) (36, 1) (36, 1)

N = n = n = 81 81 81 is the factor of (1,) (1,) (1,) (3), 27 (3), 27 (3), 27 (9, 9) (9, 9) (9, 9) (27), 3 (27), 3 (27), 3 (81, 1) (81, 1) (81, 1)

It can be found that factor pairs have palindromic characteristics, which is also the reflection of symmetry of inverse proportional function. In addition, it’s easy to see that both 363636 and 818181 can be found by iterating through n\ SQRT {n}n.

6, summary

The reason why we only need to traverse n\ SQRT {n}n to find the factor is that:

  • The factors are inversely proportional y=nxy=\dfrac{n}{x}y=xn, so the factors always come in pairs
  • The inverse proportional function is symmetric with respect to y=xy=xy=x, so all pairs of factors are symmetric with respect to y=xy=xy=x
  • And inverse function y = nxy = \ dfrac {n} {x} y = xn graphics and symmetric axis y = y = y = x is the intersection of (n, n) (\ SQRT {n}, \ SQRT {n}) (n, n)
  • So on the inverse function of graphics, arbitrary at the intersection (n, n) (\ SQRT {n}, \ SQRT {n}) (n, n) of the upper left point (x ‘, ‘) y (x, y ‘) (‘ x, y ‘), Will be in the lower right side of the intersection (y ‘, ‘) x (y, x ‘) the form of (y ‘, ‘x) (x’ < nx ‘< \ SQRT {n}’ x and y ‘> < n ny’ > \ SQRT {n} y ‘> n)
  • So if you walk through n\ SQRT {n}n, you can find all the factors and there is no special case factor greater than n\ SQRT {n}n that is not found

In other words, it is only necessary to iterate over n\ SQRT {n}n, because iterating over factors greater than n\ SQRT {n}n is essentially iterating over factors less than n\ SQRT {n}n, Just swap the XXX and YYy positions of the factor pairs found when less than n\ SQRT {n}n. Since the numbers on the number line are continuous (non-discrete), this result holds for decimals as well.


Original link: leetcode-cn.com/problems/pe…