3
$\begingroup$

A positive integer with exactly four positive factors is called "quadly". Compute the least $n$ for which each of $n,n+1$ and $n+2$ is quadly. (ARML 2008)

My method of attacking this problem started by first noting that for each quadly number the prime factorisation must be of the form $pq$ ($p$ and $q$ are unique prime factors) or $m^3$ (where $m$ is prime). Then I also noted since the 3 numbers are consecutive, one of them must have a factor of 3 and atleast 1 of them must have a factor of 2. We start off by assuming that $n$ is even and so it is of the form $2q$. Then $n+2$ must also be even and be of the form $2p$. Subtracting the two equations we get $2p-2q=2 \implies p=q+1$. This means that $p$ and $q$ are consecutive and they're both primes. This only gives the possibility that $(p,q)=(3,2)$. Plugging this back in we get that the three numbers are $4,5,6$ but $4$ and $5$ are clearly not quadly. Hence we have a contradiction and so $n$ must be odd which means that $n+1$ must be even. We also know that one of the three integers is also a multiple of 3. From here I kind of brute-forced my way by finding prime multiples of 2, i.e. finding $2p$, where $p$ is an odd prime and checking $2p-1$ and $2p+1$ to see if they were quadly or not. Doing so I found that for $p=17$ yields the first solution of three consecutive quadly numbers which is $33,34,35$.

However, I'm looking for a more systematic approach which instead of using brute force for the rest of the problem, actually derives the answer mathematically. I'm sure there is a way to do but I can't think of one. Any help would be appreciated.

$\endgroup$
1
$\begingroup$

Restrictions for numbers a , a+1 and a+2 all having exactly 4 divisors :

$n^3+1=(n+1)(n^2-n+1)$

$n^3-1=(n-1)(n^2+n+1)$

If n is an odd prime, then n-1 and n+1 are even numbers and $n^2-n+1 \ge 2$, so neither $n^3-1$ nor $n^3+1$ can have exactly 4 divisors, if n>3. Since 27 and 8 are also not involved in a triple, the 3rd powers do not need to be considered.

The remaining cases lead to the equation

$$3u - 2v = 1$$

or

$$3u - 2v = -1$$

where u and v are primes greater than 3.

The first equation has the solution

$$u=2n+1 , v = 3n+1$$

for some natural number n.

The second equation has the solution

$$u = 2n+1 , v = 3n + 2$$

for some natual number n.

Maybe these restrictions help you.

$\endgroup$
0
$\begingroup$

No matter how you do the search, you may probably cut corner before that.

Excluding the possibility of very small numbers ($<5$), as you mentioned, 3 consecutive numbers have at least 1 of them even. So it must be the format of $2p$, where $p$ is a prime. Since $4|2p-2, 2p+2$, the only possibility is $2p-1, 2p, 2p+1$.

During the search, you can also rule out the pair ($2p, 2p+1$) of safe primes.

$\endgroup$
0
$\begingroup$

As you said one of the numbers must be divisible by $2$ and one must be divisible by $3$. You argued that they have to be different. And you argued that $2$ cannot divide more than one of the numbers.

The third number has to be of the form $p^3$ or $pq$. The smallest values $p$ respectively $p,q$ can take are $5$ and $7$.

So the smallest possible value the third number can take is $5 \cdot 7$ as $5^3 >> 5 \cdot 7$. Thus the largest of the numbers has to be at least 35, you can start your search here.

$\endgroup$

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.