1
$\begingroup$

Determine whether $(1):$

$$p_i>\sigma(p_1^{a_1}p_2^{a_2}...p_{i-1}^{a_{i-1}})\hspace{2mm}\forall i \in [1,\omega(n)]$$ is logically equivalent to $(2):$

$$d_j>d_1+d_2+...+d_{j-1}\hspace{2mm}\forall j \in [1,\sigma_0(n)]$$

where $1=d_1<d_2<...<d_{\sigma_0(n)}=n$ are the divisors of $n$, $p_1^{a_1}p_2^{a_2}...p_{\omega(n)}^{a_{\omega(n)}}$ is the canonical prime factorization of $n$, and $\sigma(n)$ is the sum of divisors of $n$.

I came across $(1)$ following an interest in the practical numbers, which - for $n$ with prime factorization as above - satisfy the inequality

$$p_i\leq1+\sigma(p_1^{a_1}p_2^{a_2}...p_{i-1}^{a_{i-1}})\hspace{2mm}\forall i \in [1,\omega(n)]$$

First, I programmatically considered $(3):$

$$p_i>1+\sigma(p_1^{a_1}p_2^{a_2}...p_{i-1}^{a_{i-1}})\hspace{2mm}\forall i \in [1,\omega(n)]$$

for which all satisfactory $n$ must clearly be odd, since for $i=1$ we have $p_1>2$. But, having recently become familiar with the sequence referred to at least by the author of the OEIS page as "distended" numbers, those satisfying $(2)$, as well as the recently defined sequence A230492, which is suspected not to contain any distended numbers, I quickly noticed that the first odd term of A230492, $117$, was not present in $(3)$, and so proceeded to check whether any of the remaining terms given satisfied $(3)$. Finding none, I thought to consider whether $(3)$ was in fact a subset of the distended numbers, again finding no exceptions. Knowing, however, that not every distended number is odd, and now recognizing the similarity between $(2)$ and $(3)$, I relaxed the definition of $(3)$ to $(2)$ by subtracting $1$ from the R.H.S, which allows for some even terms (as well as some additional odd terms). It appears as if these additional terms are precisely the distended numbers not satisfying $(3)$ i.e. $(1) \iff (2)$. That is essentially how I came to $(1)$.

I can hardly see where to start proving sufficiency in either direction. It seems that an essential fact for proving $(1)$ is sufficient to imply $(2)$ would be that $\gcd(a,b)>1\implies \sigma(a)\sigma(b)>\sigma(ab)$, from which we can then obtain for each divisor $d$ an inequality of the form $$d>\sigma(r_1)^{e_1}...\sigma(r_{\omega(d)})^{e_{\omega(d)}}>\sigma(r_1^{e_1}...r_{\omega(d)}^{e_{\omega(d)}})$$ which may be sufficiently strong, but I can't figure out a way to state this more explicitly without the notation being overly cumbersome.

In the other direction the outlook is no better. It's obvious that the condition $(2)$ implies $n$ is deficient ($\sigma(n)<2n$), and therefore every divisor must be as well, but I'm not sure this will be significantly useful.

Remarks:

We could conceivably restrict the form of the factorization of $n$ based on the fact that the only integers which satisfy $(1)$ or $(2)$ and are practical numbers as well are the powers of two, but to what extent this would be useful I don't know. No product of primorials (products of the first $k$ primes) will work, for example, again excluding powers of two. Finally, both conditions obviously hold for all primes, which is of some interest in itself, as the sequence appears to be of considerable asymptotic density, but less so than the deficient numbers, for which a Goldbach analogue is easy to prove. In particular, $\approx 55.359$% of integers less than $10^6$ are found to satisfy $(1)$. Whether the density is greater or less than $1/2$ (if it exists, that is) is an interesting question in itself.

The following is from the previously mentioned OEIS sequence A230493.

"Consider the sums obtained by adding up divisors of $n$, ordered by the decimal value of the binary representation of the divisors used for a particular sum. Three cases can occur. On one hand the sums that are obtained are strictly increasing. For instance, with $n=3$, divisors are $(1,3)$, sums are $1,3,4$. It appears that this case might give distended numbers." (a better example is given on the sequence page)

This is a question of Michel Marcus, an editor and regular contributor to the OEIS, with whom I was in correspondence with during his authorship of the sequence. While I haven't been able to intuit a specific connection, it seems plausible that a proof of my observation might either lead to or depend upon the answer to his question.

The question could perhaps do with another tag or two, but I don't see anything along the lines of "logical equivalence" and haven't found anything else particularly fitting.

$\endgroup$
1
+100
$\begingroup$

If I understand the statement of the question correctly, your conjecture is false and $5^2 \cdot 11 = 275$ is a counterexample.

(If you don't want to walk through the cases where your equations do hold together, skip ahead to the last third where the counterexample conditions are given.)

I noted that if a number satisfies equation (1) then each number formed by building up the prime factors one by one must also satisfy (1), so I pursued the approach of trying to build up numbers one distinct factor at a time to see which sort meet the conditions of (1) and (2).

It is easy to show that not only the primes, but all powers of primes meet both conditions. I next considered semiprimes $q p$ with distinct factors and $p \gt q$. Equation (1) produces $$p \gt q+1$$ which is true for all primes except the pair $(2,3)$. With the divisors being $1, q, p, qp$ equation (2) also produces $$p \gt q+1$$ as well as $$p \gt \dfrac{q+1}{q-1}$$ which is also true for all primes besides $(2,3)$. Thus both your equations are satisfied by all semiprimes except $6$.

Next up was to consider numbers of the form $q p^2$ or $q^2 p$ with $p > q$. To cut to the chase, in the first case we get the same result as for semiprimes: all pairs besides $(2,3)$ satisfy both equations. In the second case, if $p \gt q^2 + q + 1$ then equation (2) is also satisfied is all cases. Thus, the two equations give consistent results up to this point.

However, in the case $q \lt p \lt q^2$ equation (1) will always fail, but equation (2) can sometimes be satisfied. The divisors, in order, are $1, q, p, q^2, qp, q^2p$. The condition $q^2 \gt p+ q+ 1$ rearranges to $$p \lt q^2 - q -1$$ which is somewhat more restrictive than $p \lt q^2$ but can be satisfied with $p \gt q$. The condition $pq \gt q^2 + p + q +1$ gives $$p \gt \dfrac{q^2 + q + 1}{q-1}$$ which simplifies to $$p \gt q + 2 + \dfrac3{q-1}.$$ For $q\ge 5$ the remaining fraction is less than one, so this becomes equivalent to $$p \gt q + 2$$ for integers.

The remaining possible conditions for equation (2) can be met without imposing further restrictions, so the net result is that for $q \ge 5$ and $p$ satisfying $$q + 2 \lt p \lt q^2 - q -1$$ we will have a $(q,p)$ pair where $q^2 p$ does not satisfy (1) but does satisfy (2).

As examples, for $q = 5$ we have $7 \lt p \lt 19$ and for $q=7$ we have $9 \lt p \lt 41$. Taking the first example, $5^2 \cdot 11 = 275$ fails (1) with $11 \not \gt 5^2 + 5 + 1$ but satisfies (2) as the divisors are $1, 5, 11, 25, 55, 275$ and the partial sums are $1, 6, 17, 42, 97$ which are each less than the next divisor.

Q.E.D? Did I miss anything?

$\endgroup$
  • $\begingroup$ Excellent. Does every number satisfying (1) also satisfy (2)? $\endgroup$ – Jaycob Coleman Nov 15 '13 at 2:44
  • 1
    $\begingroup$ I can't say for sure since I only looked at certain patterns of prime signatures. But it looks like it will hold for all numbers with exactly two distinct primes. I didn't find any cases in the patterns I looked at where (2) became more restrictive than (1). $\endgroup$ – half-integer fan Nov 15 '13 at 3:32
  • $\begingroup$ I have not worked through it all rigorously, but I note that if (1) holds then the divisors, in order, will run through the powers of the smallest prime uninterrupted, then the same sequence with a factor of the second prime included, and so on through all the combinations of the first two primes, then the pattern will repeat with the third prime, and so on. Obviously the divisor which is the second prime will meet (2) as this is the same condition as (1) - the same for the third, etc. prime. A quick survey looks like the other divisors will not have any more restrictive conditions. $\endgroup$ – half-integer fan Nov 18 '13 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.