Consecutive integers divisible by prime powers

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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