Salvatore Ingala sent
the following conjecture:
I want
to propose you a conjecture related to prime numbers. I don't know if it
is a new one or it has been studied yet.
Let n >
2 be an integer and let p be his greatest prime factor; we call S(n) the
set of all positive integers relatively prime to n, and we call d(n) the
biggest difference between two _consecutive_ elements in S(n).
I conjecture that d(n) < 2p.
The
conjecture is probably more interesting when n = 2*3*...*p, because the
set S(n) is the result of the application of Erathostene's sieve deleting
all multiples of 2, 3, ..., p. But it is also more difficult, because the
set S(n) becomes more sparse.
I have
collected the results of some computations, which could be extended; here
p# means 2*3*...*p
n
d(n)
3# 4
5# 6
7# 10
11# 14
13# 22
17# 26
19# 34
23# 40
29# 46
31# 58
37# 66
Question:
What do you say about this conjecture?
This conjecture was disconfirmed for
several puzzlers Rudolph Knjzek, John Calligy & J. K. Andersen. Other
contributions came from Dan Lima and Farideh Firoozbakht.
Knjzek wrote:
If the conjecture were true, it would
proof that there is at least one prime number between two square numbers.
I have tried to proof this that way some years ago without success,
because I have found counterexamples. There is one of them:
n=2*3*5*7.....*47
All numbers between 456854489248342153
and 456854489248342249 are not coprime to n. The difference is 96 and this
is greater than 2*47=94.
...
You asked:
Can you show please the correspondence between
this conjecture and the other
you name "there is at least one prime number between two square
numbers"?
I tried to prove the conjecture "There is at least one
prime number between two square numbers" this way:
Between n^2 and (n+1)^2 are 2n numbers. If one of these
numbers is composite, it has at least one prime factor less or equal
than n or in other words, it is not coprime to p# =2*3*5*7*....*p, if p
is the greatest prime number less or equal than n. On the other hand are
all numbers between n^2 and (n+1)^2 prime numbers, if they are coprime
to p#, because the next prime greater p is greater than n.
If Lngala's conjecture were true, the distance of two
numbers coprime to p# would be less than 2p<=2n and we could follow,
that there must be at least one prime number between n^2 and (n+1)^2.
Unfortunately Ingala's conjecture doesn't hold for large values of p#.
You asked:
Can you show the smaller example you know of
failure of "there is at least
one prime number between two square numbers"?
I have no counterexample for this conjecture. It is an
heuristic fact, that the large composite series which disprove Ingala's
conjecture appear with numbers, much greater than n^2. Therefore they
don't disprove the existence of at least one prime number between two
square numbers. But I don't know how I could prove this.
***
John Calligy wrote:
Oh, wouldn't it be nice. If true, we
could prove with one stroke: 1) Bertrand's postulate; 2) Dirichlet's
theorem about primes in arithmetic sequences; and 3) the conjecture that
there is always a prime between n^2 and (n+1)^2.
Unfortunately, let n=
1 (mod 2)
1 (mod 3)
3 (mod 5)
3 (mod 7)
1 (mod 11)
7 (mod 13)
4 (mod 17)
10 (mod 19)
22 (mod 23)
24 (mod 29)
15 (mod 31)
26 (mod 37)
1 (mod 41)
7 (mod 43)
Then all of the numbers from n+1 to n+90 have a prime factor <= 43. n =
5766753709862113
***
Andersen wrote:
The conjecture is wrong. n = 43# has
d(n) >= 90:
The difference between 4838684447722067 and the next S(n) number is 90.
I don't know whether 90 is optimal.
n = 199# has d(n) >= 600, so d(p#) > 3p. The first of two S(n) numbers 600
apart:
5181309372967465210336887273838966764253333654241974751532320979638596377949742779
I have searched large prime gaps with a program which finds intervals with
unusually many small factors:
http://hjem.get2net.dk/jka/math/primegaps/megagap2.htm
Using the program, I have found d(n) >= 10^7 for p=1202689.
The S(n) number has 521984 digits so it is omitted here.
It gives d(p#) > 8.3p. I don't know how large the 8.3 ratio can become.
***
Faride wrote:
I think d(n) depends to the number of distinct prime
factors of n and also depends to this fact that if 2 or
3 divides n or not.
So d(n) doesn't depend to the largest prime factor of n.
It seems that the following table is true.
(ki>0 and p,q,r,s,t,... are prime numbers)
----------------------------------------------------------
n d(n)
----------------------------------------------------------
p 1
p^k (k>1) 2
p^k1*q^k2 (2<p<q) 3
2^k1*p^k2 (p>2) 4
p^k1*q^k2*r^k3 (3<p<q<r) 4
3^k1*p^k2*q^k3 (3<p<q) 5
p^k1*q^k2*r^k3*s^k4 (3<p<q<r<s) 5
2^k1*p^k2*q^k3 (2<p<q) 6
3^k1*p^k2*q^k3*r^k4 (3<p<q<r) 7
p^k1*q^k2*r^k3*s^k4*t^k5 (3<p<q<r<s<t) 7
2^k1*p^k2*q^k3*r^k4 (3<p<q<r) 8
2^k1*3^k2*p^k3*q^k4 (3<p<q) 10
2^k1*p^k2*q^k3*r^k4*s^k5 (3<p<q<r<s) 10
3^k1*p^k2*q^k3*r^k4*s^k5 (3<p<q<r<s) 11
...
we can extend this table.
Example: d(3^3*1087)=3
Q. Does there exist a number n such that d(n)=9?
***
Dan Lima wrote:
It's enough to prove the conjecture only for
primordials.
For any integer n take L(n) the product of all primes that occur in n -
L(n) divides n.
Then S_n is the same with S_L(n) so d(n)=d(L(n)) and both n and L(n) have
the same greatest prime factor.
So it's enough to prove the conjecture only for square free integers.
For any square free n take p the greatest prime factor and p# the
corresponding primordial - n divides p#.
Both n and p# have the same greatest prime factor p while S_n contains S_p#,
so d(p#)>=d(n).
That's why it's enough to prove the conjecture only for primordials:
d(p#(k))<2p(k)
Another trivial remark is: d(p#(k))=2p(k-1) for
k=2,3,4,5,6,7,8,10,11 and d(p#(k))<2p(k-1) for k=9,12.
The following stronger conjecture might be true:
d(p#(k))<=2p(k-1)
Equivalent if p(k) is the greatest prime involved in n
then:
d(n)<=2p(k-1)
***
