Are the "distended" numbers precisely the numbers for which no two subsets of their divisors have the same sum?

83 Views Asked by At

The OEIS sequence A051772 defines the "distended" numbers as those positive integers $n$ for which each divisor of $n$ is greater than the sum of all smaller divisors.

Now, here's a question about such numbers:

Question: Are the "distended" numbers precisely the positive integers $n$ for which the "sum" function from subsets of the divisors of $n$ to the nonnegative integers is injective?

It is easy to show that any "distended" number $n$ satisfies the injectivity condition. Indeed, just write the divisors of $n$ in order from greatest to least as columns and below those columns, write all the binary numbers whose number of digits is at most the number of divisors of $n$, with leading zeros for binary numbers with fewer digits. Then, write a "sum" column that lists the sum of the divisors corresponding to the positions of the digit $1$ for each binary number. Finally, observe that each sum is less than the one below it because $n$ is a "distended" number. In particular, the "sum" column cannot contain any duplicates, so injectivity is satisfied.

What I could not prove is the converse. Perhaps, there might be a deficient counterexample for the converse. Also, any abundant counterexample for the converse would have to be a weird number, for injectivity would imply that the number could not be pseudoperfect. Of course, no abundant number could be a "distended" number.

1

There are 1 best solutions below

2
On BEST ANSWER

There are lots of counterexamples.

Let $p$ be a prime. Then each prime $q$ between $p^2 - p-1$ and $p^2$, with at most $2016$ exceptions, produces a counterexample $n = p^2 q$.

Proof:

The divisors of $n = p^2 q$ are $1, p, q, p^2, pq, p^2 q$, in that order if $q$ is in the given interval. Since $p^2 < 1 + p + q$, $n$ is not distended.

Now there are $64 \cdot 63/2 = 2016$ unordered pairs of distinct sets of divisors. The sum of the first set minus the sum of the second corresponds to a polynomial of degree $\le 1$ in $q$, which must be $0$ if these two sets have the same sum. The polynomial is never identically $0$, so there is at most one $q$ value where the two sets have the same sum. Thus, for each $p$, there are at most $2016$ exceptional $q$.

Hmm, too bad this didn't come up $4$ years ago.