The "nearly perfect number" problem

[Nhân Trần]

Hey guys,
I will head to the problem right now.
N is a natural number. K is one of the divisors of N satisfied K<N.
Then, S is the sum of all K.

For example: S(18) = 1+3+6+9 = 21

The problem is: given 2 number L and D (2<=L<=1000, 0<=D<=10000). Find the number of natural numbers (<L) such that the difference between each natural number and its S can't be greater than D.

For example: L = 10, D = 1. Then we obtain 5 numbers satisfied: 1, 2, 4, 6 and 8.

Any ideas???
Many thanks.

[Nominal Animal]

No. Your definitions and your example do not match; the puzzle is ill-defined. Contradictory.

Let's redefine the variables.

Let K_i(N) be the divisors of N, with 1 ≤ K_i(N) < N.
Let A(N) be the sum of K_i, i.e. the sum of the divisors of N.
Let S_i(N) be A(N) - K_i(N), i.e. the sum of the divisors of N except one divisor. Then,

N is a perfect number if and only if N = A(N)

and

N is a nearly perfect number if N = S_i(N) exists
(it does not matter for which i, as long as it exists)

Note that each N corresponds to a single value A(N), but one or more S_i(N).

(The number of i for S_i(N) is the number of divisors in N, including 1 as a divisor.)

The issue with your problem statement is that you treat S_i(N) as if it was unique. It isn't. Therefore, "S_i(N) can't be greater than D" is ambiguous.

As an example, the divisors of 18 are 1, 2, 3, 6, and 9. So,

K₁(18) = 1
K₂(18) = 2
K₃(18) = 3
K₄(18) = 6
K₅(18) = 9
A(18) = 1 + 2 + 3 + 6 + 9 = 21
S₁(18) = 21 - 1 = 20
S₂(18) = 21 - 2 = 19
S₃(18) = 21 - 3 = 18
S₄(18) = 21 - 6 = 15
S₅(18) = 21 - 9 = 12

I suspect that you are trying to:

Count the number of natural numbers N, 2 ≤ N ≤ L, for which ∥S_i(N) - N∥ ≤ D exists.
The problem is limited to 2 ≤ L ≤ 1000 and 0 ≤ D ≤ 10000.

There are other interpretations, too -- in particular, you might be looking at combinations with 0 to D K_i's subtracted from A instead --, so you do need to redefine your problem before any help is possible.

[Nhân Trần]

I'm sorry I didn't make it clear. You can look at the following example:
Given L = 10, D = 1.
Then we obtain 5 numbers: 1, 2, 4, 6 and 8 because:
- all of them are < 10
+ with N = 1: it has no such divisor K like that so S = 0 -> N - S = 1 - 0 = 1 = D (satisfied)
+ with N = 2: it has only one divisor K = 1 -> S = 1 -> N - S = 2 - 1 = 1 = D (satisfied)
+ with N = 4: K= 1; 2 -> S = 1+2 = 3 -> N - S = 4 - 3 = 1 = D (satisfied)
,...etc

What i want is only to find the number of natural numbers N satisfied. That means, in above example, 5

[Nominal Animal]

I'm sorry I didn't make it clear.

You didn't make it any clearer, though.

Let me put it simply. Your example for S, "S(18) = 1+3+6+9 = 21", makes no sense, because the divisors of 18 are 1, 2, 3, 6, and 9.

[Nhân Trần]

That's my typo mistake. Can u just concentrate on the example with given L and D

[Nominal Animal]

It is not a typo; if it were, then we'd be talking about perfect numbers, not nearly perfect numbers.

A perfect number is one whose divisors (including 1 but excluding the number itself) add up to the number itself.

A nearly perfect number is one whose divisors (including 1 but excluding the number itself), if you omit one of those divisors, add up to the number itself. Check out this PDF about nearly perfect numbers.

Your problem as is is ill-defined; like asking how many blue apples you have, if you have two deflated balloons. It does not make sense, because it is self-contradictory. You need to first fix your problem definition, before we can help you.