3
$\begingroup$

There's a similar question on here already but I don't think the answers are applicable in this case.

Question: Find the smallest three consecutive integers for which the first integer is divisible by the square of a prime; the second integer by the cube of a prime; and the third integer by the fourth power of a prime.

My attempt: Let the three consecutive integers be a, b and c. Then

$a\equiv 0\pmod{d^2}$

$a+1\equiv 0\pmod{e^3}$

$a+2\equiv 0\pmod{f^4}$

where $d,e,f$ are prime. This is equivalent to

$a\equiv 0\pmod{d^2}$

$a\equiv -1\pmod{e^3}$

$a\equiv -2\pmod{f^4}$

Then after applying the Chinese Remainder Theorem,

$e^3f^4a\equiv 1\pmod{d^2}$

$d^2f^4a\equiv 1\pmod{e^3}$

$d^2e^3a\equiv 1\pmod{f^4}$

I don't think this is getting me anywhere. Is this sort of general approach going to work or am I wasting my time?

$\endgroup$
3
$\begingroup$

Hint: It's a good idea to think about which primes these primes could be. For example, since you're looking for small numbers, you probably want to see what happens if you stipulate that the prime $p$ so $p^4$ divides your largest number is $2$ -- then try for $3$, $5$, etc. until you find that your result ends up being too big. I'll show you a worked example for the simpler problem of finding two consecutive numbers the first of which has a perfect square of a prime as a factor and the second of which has the perfect cube of a prime as a factor:

Let our integers be $a$ and $a+1$. We know that either $8|a+1$ (so $2$ is our prime) or $a+1\geq 27$. Let's first try the case $8|a+1$. Then we want to find a number that the perfect square of a prime divides in the sequence

$$7, 15, 23, 31, 39, 47, 55, 63, 71...$$

and we find that the first one occurs at $63$, so ($63,64$) is a solution. Now let's try when $27|a+1$. We get that $a$ is in

$$26, 53, 80...$$

and then everything above $53$ is too big, since we've already found the example $(63,64)$. Now, if our prime is any bigger than $3$, we get that $a+1\geq 125$, which is going to give us something much larger than $(63,64)$, and thus $(63,64)$ is our answer.

$\endgroup$
1
$\begingroup$

Hmm...

Well, by CRT $n \equiv 1 \pmod {p^2}$

$n \equiv 0 \pmod {q^3}$

$n \equiv-1 \pmod {r^4}$ will have unique solutions for any the primes $p, q, r$.

If I blanketly choose $r=2; q=3;p=5$ I will get.

$n\equiv 1 \pmod {25}$ and $n\equiv 0 \pmod 27$. $n= 27j = 1 + 25k = 1-2k + 27k$. If $k=14$ we have $j= 13$. This gives us $n\equiv 351 \pmod {675}$.

$n \equiv 351 \pmod{675}$ and $n\equiv -1 \pmod {16}$ gives us

$351+ 675m\equiv -1 + 3m \equiv -1 \pmod{16}$.

so $n = 351$ gives us $n-1 = 14*5^2; n = 13*3^2; n+1 =44*2^4$.

Is that the least possible?

Well $3^4< 352 <5^4$ so $r=2,3$ if we are to find any lower.

And $7^3< 351 < 11^3$ so $q=3,5,7$ if we are to find any lower.

And $17^2 < 351 < 19^2$ so $p = 7,11,13,17$ if we are to find any lower.

If worse comes to worse we can solve them all.... Or we could write a program to check all numbers less than $351$.

I doubt there is any lower but I'm not betting anything valuable on it.

$\endgroup$
0
$\begingroup$

I wrote a Python code to try to find these $3$ consecutive numbers, and I searched up to $100$ million or $10^8$, and couldn't find them. So if they exist, they're definitely larger than $10^8$.

If you want to continue the search, here is my code (it's for Python 3.7, to be exact, but it should work for Python 3.0+):

import math

lookup_range = 100000000

def isPrime(a):

    if(a <= 1):
        return False

    for i in range(2,a-1):
        if a % i == 0:
            return False
    return True

R = int(math.sqrt(lookup_range+1))+1

primelist = [a for a in range(R) if isPrime(a)]

for a in range(1,lookup_range+1):

    if(a % 1000000 == 0):
        print('Looked up to ' + str(a) + ', ' + str(round(100*a/lookup_range,2)) + '%')

    passedTestOne = False
    passedTestTwo = False
    passedTestThree = False

    p1 = 0
    p2 = 0
    p3 = 0

    for i in primelist:
        if(a % pow(i,2) == 0):
            passedTestOne = True
            p1 = i
        else:
            break

    for i in primelist:
        if((a+1) % pow(i,3) == 0):
            passedTestTwo = True
            p2 = i
        else:
            break

    for i in primelist:
        if((a+2) % pow(i,4) == 0):
            passedTestThree = True
            p3 = i
        else:
            break

    if(passedTestOne and passedTestTwo and passedTestThree):

        print(str(a) + ' = ' + str(p1) + '^2')
        print(str(a+1) + ' = ' + str(p2) + '^3')
        print(str(a+2) + ' = ' + str(p3) + '^4')
        break
$\endgroup$
  • $\begingroup$ An upper bound for the smallest solution is $2^43^35^2=10800$, so there is something wrong with your code. $\endgroup$ – Ross Millikan Mar 25 at 19:34
  • $\begingroup$ Why is that? I'm genuenly curious, and I want to fix my code then. $\endgroup$ – Daniel P Mar 25 at 19:35
  • 1
    $\begingroup$ By the Chinese Remainder Theorem the solutions to any set of equations $\bmod 16, \bmod 27, \bmod 25$ recur every $10800$, so there will be one in the range $[0,10799]$ There might be a smaller one from permuting the primes, but we are guaranteed one this way. This is in the spirit of Carl Schildkraut's answer $\endgroup$ – Ross Millikan Mar 25 at 19:36
  • $\begingroup$ Where does $\bmod 16, \bmod 27$ and $\bmod 25$ come from? It seems from the problem that there is no upper bound to the primes $d, e, f$. Sorry to ask, but I still can't see why. :( $\endgroup$ – Daniel P Mar 25 at 19:42
  • 1
    $\begingroup$ I just chose $2$ to be the prime to a fourth power, $3$ to be the prime to be a third power, and $5$ to be the square. That keeps the moduli as small as possible. It doesn't prove that there is no smaller solution but it gives us a hard upper bound. A little hand playing finds the solution is much smaller than $10800$ and I would be surprised if there were one any smaller. $\endgroup$ – Ross Millikan Mar 25 at 19:44

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.