Not eleven smooth (four consecutive integers >11))

[2M215856352p1]

Result: Let k be a positive integer >=101. If k,k+1,k+2 and k+3 are all 11-smooth, then exactly one of them is 3-smooth.

My attempted proof could be a major spoiler. If you don’t mind getting spoiled, you can try to poke holes into my proof. Criticism helps me improve.

Largest pair of consecutive 3-smooth numbers is 8 and 9. This can be shown by finding the three smallest solutions of the three relevant Pell’s equations.

Using the procedure and notation in https://en.m.wikipedia.org/wiki/St%C3%B8rmer%27s_theorem, P={2,3}


The possible squarefree q not equal to 2 are 1, 3 and 6.
The Pell’s equations to solve are x^2-2y^2=1, x^2-6y^2=1, x^2-12y^2=1


The smallest positive integer solution for x^2-2y^2=1 is (x,y)=(3,2).
(3+2sqrt(2))^2 = 9+12sqrt(2)+8 = 17+12sqrt(2)
(3+2sqrt(2))^3 = (3+2sqrt(2))(17+12sqrt(2)) = 51+48+34sqrt(2)+36sqrt(2) = 99+70sqrt(2)
The three smallest positive integer solutions are (3,2), (17,12) and (99,70).
The corresponding pairs to test for smoothness are (1,2), (8,9) and (49,50) but only (1,2), (8,9) are possible combinations.


The smallest positive integer solution for x^2-6y^2=1 is (x,y)=(5,2)
(5+2sqrt(6))^2 = 25+20sqrt(6)+24 = 49+20sqrt(6)
(5+2sqrt(6))^3 = (5+2sqrt(6))(49+20sqrt(6)) = 245+240+100sqrt(6)+98sqrt(6) = 485+198sqrt(6)
The three smallest positive integer solutions are (5,2), (49,20) and (485,198).
The corresponding pairs to test for smoothness are (2,3), (24,25) and (242,243) but only (2,3) is a possible combination.


The smallest positive integer solution for x^2-12y^2=1 is (x,y)=(7,2)
(7+2sqrt(12))^2 = 49+28sqrt(12)+48 = 97+28sqrt(12)
(7+2sqrt(12))^3 = (7+2sqrt(12))(97+28sqrt(12)) = 679+672+196sqrt(2)+194sqrt(2) = 1351+390sqrt(2)
The three smallest positive integer solutions are (7,2) (97,28) and (1351,390)
The corresponding pairs to test for smoothness are (3,4), (48,49) and (675,676) but only (3,4) is a possible combination.


Hence, the largest pair of consecutive 3-smooth numbers is 8 and 9.


Largest pair of consecutive even 3-smooth numbers is 16 and 18 because halving any pair of consecutive even numbers results in a pair of consecutive numbers.
Largest pair of consecutive odd 3-smooth numbers is 1 and 3 since odd 3-smooth numbers are necessarily a power of 3.
Hence, the largest pair of 3-smooth numbers which differ by 2 is 16 and 18.


Largest pair of 3-smooth numbers which are not multiples of 3 and differ by 3 is 1 and 4 since 3-smooth numbers which are not multiples of 3 are necessarily a power of 2.
Largest pair of consecutive 3-smooth multiples of 3 is 24 and 27 because dividing any pair of consecutive multiples of 3 by 3 results in a pair of consecutive integers.
Hence, the largest pair of 3-smooth numbers which differ by 3 is 24 and 27.


Suppose there exist k>=101 such that k,k+1,k+2 and k+3 are all 11-smooth.


Since k>=101, there cannot be two consecutive 3-smooth numbers.
Hence, at least one of k, (k+1) is not 3-smooth.
Hence, at least one of (k+1), (k+2) is not 3-smooth.
Hence, at least one of (k+2), (k+3) is not 3-smooth.


Since k>=101, there cannot be two 3-smooth numbers which differ by 2.
Hence, at least one of k, (k+2) is not 3-smooth.
Hence, at least one of (k+1), (k+3) is not 3-smooth.


Since k>=101, there cannot be two 3-smooth numbers which differ by 3.
Hence, at least one of k, (k+3) is not 3-smooth.


It is easy to verify that at most 1 of k,k+1,k+2 and k+3 can be 3-smooth since any two numbers taken from {k,k+1,k+2,k+3} cannot be both 3-smooth.
Since at most one of k,k+1,k+2 and k+3 can be divisible by any prime number >=5, if none of k,k+1,k+2 and k+3 are 3-smooth, at least one of k,k+1,k+2 and k+3 must be divisible by a prime number >=13, which is a contradiction. Hence, exactly one of k,k+1,k+2,k+3 must be 3-smooth. This result can be used to extend the computer search to say, 10^1000.

It is easy to verify that for 11<=k<=100, there are no such solutions. A brute force search would suffice, in fact it has been done up to 10^40.

[Dr Sardonicus]

Originally Posted by axn

Searching all 11-smooth numbers under 10^40, the largest run of 3 consecutive 11 smooth (above 11) is 98-100, and largest run of 2 consecutive 11 smooth is (still) 9800, 9801.

There are appr. 1 billion 11-smooth numbers under 10^100.

Regarding the number of numbers <= X with prime factors in a given finite set {p₁, p₂, ..., p_n}, it is clear that for one prime the answer is floor(log(X)/log(p₁)). For two primes, it is the number of points with integer coordinates in or on the triangle with vertices at (0,0), (log(X)/log(p₁),0), and (0, log(X)/log(p₂)). This is approximately the area of the triangle, 1/2*log(X)/log(p₁)*log(X)/log(p₂). The appropriate generalization is the n-dimensional volume of a simplex with vertices at the origin, and the points whose coordinates are 0, except the k^th, with coordinate log(X)/log(p_k), k = 1 to n. This gives an estimate

1/n! *log(X)/log(p₁)*log(X)/log(p₂)* ... *log(X)/log(p_n), with an error of order log^(n-1)(X)

Plugging in n = 5, set of 5 primes {2, 3, 5, 7, 11} and X = 10^100 gives a value of 943191898.27, which is close to a billion.

[Dr Sardonicus]

Originally Posted by 2M215856352p1

You could simply use the procedure described in https://projecteuclid.org/download/pdf_1/euclid.ijm/1256067456 and https://en.wikipedia.org/wiki/Størmer%27s_theorem. To be frank, I cannot understand all the math behind the proof of correctness of this procedure.

Thanks for posting these references. I was unaware of the method. I haven't gone through all the details, but it seems clear the method should work for determining all pairs of consecutive integers whose prime divisors are in a given finite set.

Luckily, there is a much simpler method of dealing with the problem I have posted.

[Dr Sardonicus]

Solution: We use the following result: If M is squarefree, an integer N > 1 is divisible only by the prime factors of M, and gcd(N,M) = p, one of the prime factors of M, then N is a power of p.

We claim: If all four integers n, n+1, n+2, n+3 are divisible only by the prime factors of M = 2*3*5*7*11, then at least one of them is a prime power. If none of them is a power of 2, then at least two of them are powers of odd primes.

Proof: Two of n, n+1, n+2, n+3 are divisible by 2. If either is a power of 2, we are done. If neither is a power of 2, each must be divisible by an odd prime; since the two even integers differ by 2, the odd primes must be different. This leaves at most two of 3, 5, 7, or 11 to divide the remaining two integers, which are odd and differ by 2; so each can only be divisible by one of these primes, and by the above result, is a power of that prime. So if none of n, n+1, n+2, or n+3 are powers of 2, and all are 11-smooth, then the two odd numbers are powers of odd primes. (This actually happens with [9, 10, 11, 12])

So assume one of the numbers n, n+1, n+2, n+3 is a prime power p^k. Then, p^k - 1 or p^k + 1 is also one of the numbers (and both may be).

It therefore remains only to check the numbers p^k - 1 and p^k + 1 for p = 2, 3, 5, 7, and 11, to see which are 11-smooth. Using basic facts about the factors of integer evaluations of cyclotomic polynomials, it isn't hard to show(*) that there are only a few cases where either p^k - 1 or p^k + 1 is 11-smooth. The only cases where both p^k - 1 and p^k + 1 are 11-smooth for k > 1 are p = 2, k = 2 or 3; and p = 7, k = 2.

The complete list [p, k, +/- 1] is

[[2, 1, -1], [2, 1, 1], [2, 2, -1], [2, 2, 1], [2, 3, -1], [2, 3, 1], [2, 4, -1], [2, 5, 1], [2, 6, -1], [3, 1, -1], [3, 1, 1], [3, 2, -1], [3, 2, 1], [3, 3, 1], [3, 4, -1], [3, 5, -1], [5, 1, -1], [5, 1, 1], [5, 2, -1], [5, 3, 1], [7, 1, -1], [7, 1, 1], [7, 2, -1], [7, 2, 1], [7, 4, -1], [11, 1, -1], [11, 1, 1], [11, 2, -1]]

It is easy to check that none of these give rise to 4 consecutive 11-smooth numbers, all greater than 11.

(*) See, e.g. The Cyclotomic Polynomials by G.J.O. Jameson

[R. Gerbicz]

Nice proof, there is only one minor mistake:
you can't get rid of q=3, because if for example n is divisible by 3 then n+3 is also in the set, and divisible by 3. But the proof is still valid, because you've only (at most) 3 primes for 2 integers.

Btw, a general and old result from Sylvester says that if n>=2*k, then binomial(n,k) is divisible by a prime greater than k. In our case it gives only the weaker bound that we'll have a prime divisor>=5.

[Dr Sardonicus]

Originally Posted by R. Gerbicz

Nice proof, there is only one minor mistake:
you can't get rid of q=3, because if for example n is divisible by 3 then n+3 is also in the set, and divisible by 3. But the proof is still valid, because you've only (at most) 3 primes for 2 integers.

Oops

Thanks for the kind words, and for the correction. I'm glad my little oopsadaisy didn't wreck the proof

[SmartMersenne]

Originally Posted by R. Gerbicz

Nice proof, there is only one minor mistake:
you can't get rid of q=3, because if for example n is divisible by 3 then n+3 is also in the set, and divisible by 3. But the proof is still valid, because you've only (at most) 3 primes for 2 integers.

Btw, a general and old result from Sylvester says that if n>=2*k, then binomial(n,k) is divisible by a prime greater than k. In our case it gives only the weaker bound that we'll have a prime divisor>=5.

+1 (for niceness)

I was thinking along the same lines.

I still need to look deep into it, in my spare time, but I think it looks elegant. Not that my appreciation will mean much next to Gerbicz's but I still want to say it

[MattcAnderson]

Hi again,

As was stated before in this thread, the largest consecutive pair of integers that
are 11-smooth are 9800 and 9801.

See - http://oeis.org/A117581/

Also, Stormer's Theorem shed's some light on this.
https://en.m.wikipedia.org/wiki/St%C...er%27s_theorem

If there are no consecutive pairs larger than 9801 that are both 11-smooth
then there connot be any sets of 4 integers larger than 9801.

We have to truest Online Encyclopedia of Integer Sequences (OEIS) and Stormer's Theorem.

For what it's worth,

Matt