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$
11
  • $\begingroup$ If a number has three prime factors, it has at most eight total divisors at all. $\endgroup$
    – pancini
    Sep 2, 2019 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$
    – pancini
    Sep 2, 2019 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, 2019 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$
    – pancini
    Sep 2, 2019 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, 2019 at 18:43

2 Answers 2

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$
1
  • $\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, 2019 at 18:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .