0
$\begingroup$

I wrote a program that finds the sequence of such integers and was surprised to find that is https://oeis.org/A217856 (Numbers with three prime factors, not necessarily distinct, except cubes of primes.) I imagined that as $n$ grew larger the number of such composite divisors would slowly grow, but this appears not to be the case. I have checked up to n=500000.

For example, 12 is the first number in the sequence because the divisors of 12 are 2,3,4 and 6. Now ignore the prime divisors and examine the composites that remain, 4 and 6. 4 does not divide 6, so 12 is in the sequence.

Why can't a number with more prime divisors have more such composite divisors?

$\endgroup$
  • $\begingroup$ If a number has three prime factors, it has at most eight total divisors at all. $\endgroup$ – Elliot G Sep 2 '19 at 18:29
  • $\begingroup$ Maybe I'm misunderstanding the question. Is $n$ any number such that there is no prime factor which appears three times? $\endgroup$ – Elliot G Sep 2 '19 at 18:30
  • $\begingroup$ @Elliot G Does the example I added help? In the case of 12, 2*2*3 are the three primes. $\endgroup$ – jnthn Sep 2 '19 at 18:39
  • $\begingroup$ So are you only considering number of the form $p_1p_2p_3$ or $p_1^2p_2$ for distinct primes $p_1,p_2,p_3$? $\endgroup$ – Elliot G Sep 2 '19 at 18:41
  • 1
    $\begingroup$ If for (not necessarily distinct) primes $p_1,\ldots,p_4$ the product $p_1p_2p_3p_4$ divides $n$ then $p_1p_2$ and $p_1p_2p_3$ are composite divisors of $n$ and $p_1p_2 \mid p_1p_2p_3$. $\endgroup$ – WimC Sep 2 '19 at 18:43
2
$\begingroup$

Suppose $n$ has at least four prime factors. Then there are primes $p,q,r,s$ (not necessarily distinct) such that $pqrs$ is a divisor of $n$. Then $pq$ is a proper composite divisor of $n$, and so is $pqr$. Moreover, $pq$ divides $pqr$.

That is, if $n$ has at least four prime factors, we can always find two composite proper divisors of $n$ such that one is a multiple of the other. In other words, if we cannot find two such divisors, then $n$ can have at most three prime factors.

On the other hand, if $n$ has fewer than three prime factors, then $n$ has no proper composite divisors. So the condition you've given implies that $n$ has exactly three prime factors.

If $n=pqr$ where $p,q,r$ are prime, and $p \ne q$, then the numbers $pr$ and $qr$ are distinct composite proper divisors and not multiples of each other. But the only other possibility is that $n=p^3$, in which case $n$ has only the single proper composite divisor $p^2$.

So, if $n$ satisfies the following conditions:

  • $n$ has at least two distinct composite proper divisors
  • No two composite proper divisors of $n$ are multiples of each other.

then $n$ is the product of exactly three prime factors, and is not the cube of a prime. Conversely, any product of three prime factors which is not the cube of a prime has these properties.

$\endgroup$
1
$\begingroup$

If I understand you correctly, then it should easily be possible to construct such a number. But it's quite possible such a number is bigger than 500.000. A relatively small example is given by $n = d_0 \cdot d_1 \cdot d_2 \cdot d_3$ where

\begin{align} d_0 &= 3 \cdot 5 = 15 \\ d_1 &= 5 \cdot 7 = 35 \\ d_2 &= 7 \cdot 13 = 91 \\ d_3 &= 13 \cdot 17 = 221 \\ \end{align}

In other words, $n = 10.558.275$. You can easily extend the construction to an arbitrary number of divisors.

$\endgroup$
  • $\begingroup$ Divisors of number 10558275: 1, 3, 5, 7, 13, 15, 17, 21, 25, 35, 39, 49, 51, 65, 75, 85, 91, 105, 119, 147, 169, 175, 195, 221, 245, 255, 273, 325, 357, 425, 455, 507, 525, 595, 637, 663, 735, 833, 845, 975, 1105, 1183, 1225, 1275,..., and 15 divides 75, among others. $\endgroup$ – jnthn Sep 2 '19 at 18:33

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.