Problems & Puzzles:
Conjectures
Conjecture
26. The
Calendarlike square Conjecture
Julio Cesar Aguilar, from México, has the following
doubleconjecture:
In a calendarlike and square array of
numbers from 1 to p^{2}, being p any
prime number:
a) there is always at least one prime per
row
b) there is always at least one prime per column
For example if p=5, this is the calendarlike square and the primes
inside:
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
Questions:
1. Can you find a counterexample?
2. Otherwise, what can you argue on favor of each part of the conjecture?
3. How is this conjecture related to other known Conjectures?
Solution
Luis Rodríguez wrote (17/11/01):
"In reference to the rows, this conjecture is equivalent to
the Sierpinski conjecture (Ribenboim p. 397). The Sierpinski
conjecture can be expressed more succinctly: 'For any n>=2 and
any 1 <k <= n there exists a prime number between (k1)n and kn"
***
As a matter of fact, The Sierpinski's Conjecture (S), in the Ribenboim
book says:
"(S) For every integer n>1, let n^{2} integers 1,
2, 3, ... n^{2} be written in an array with n rows, each with
n integers, like an nxn matrix:
1
2
... n
n+1,
n+2
2n
.
.
.
(n1)n+1
(n1)n+2 n^{2}
Then, there exists a prime in each row"
***
Moreover, I found that two pages ahead, that Schinzel made the
"transposed from the Sierpinski Conjecture", or the
second part of the Aguilar's Conjecture:
"(S') For every integer n>1, let n^{2} integers 1,
2, 3, ... n^{2} be written in an array with n rows, each with
n integers (just like in S). If 1<=k<=n and gcd(k,n)=1, then the
kth column contains at least one prime"
***
Schinzel & Sierpinski wrote these Conjectures in 1958.
According to Ribenboim they added "We do not know what
will be the fate of our hypotheses, however we think that, even if they
are refutes, this will not be without profit for number theory".
Ribenboim comments "It's my impression that none of
the conventional present day methods of number theory will lead to a
proof of any of the conjectures (D), (B), (H), (S), (S'). Perhaps will
be the role of the logicians, investigating the inner structure of
arithmetic, to decide whether such statements are, or are not, provable
from the Peano axioms."
***
Jud McCranie wrote " I
tested it for p <= 23929, and it holds for those values. It is almost
certainly true".
Aguilar has tested the columnconjecture for p<790000.
***
Ribenboim adds that "In 1963 this
conjecture was spelled out once more by Kanold...(and) a
quantitative version of the Conjectures in the paper of Schinzel
and Sierpinski was formulated by Bateman and Horn
(1962)"
***
In short, we may say that while the Aguilar's
conjectures are not exactly equivalent to the Sierpinski and Schinzel
Conjectures, the truth of the falsity of both come together. Or as
Rodríguez says "it's a novelty that Aguilar's proposal
makes n=p because in such a case ALL the columns must have at least one
prime, not only these k coprimes with n, as Schinzel states".
***
Days ago Enoch Haga and me were discussing more
aspects from this double Aguilar's conjecture, in particular what a minimal
solution could be. I suggested that a minimal solution for a square
pxp must be one consisting of p primes along any of the diagonals.
Enoch corrected my statement replying that while p
primes are enough to have a complete solution to both conjectures the p
primes do not need to be along the diagonals but just in such a way that no
two of these primes share row and file. Very soon he sent me several
examples of these minimal solutions. I only provide two examples:
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
***
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 
24 
25 
26 
27 
28 
29 
30 
31 
32 
33 
34 
35 
36 
37 
38 
39 
40 
41 
42 
43 
44 
45 
46 
47 
48 
49 
Enoch has gotten  by trial an error 
the minimal solutions for squares 11x11, 13x13, 17x17 and obviously has
made the following conjecture:
Enoch's Conjecture:
The Aguilar double conjecture can always be satisfied with p primes such as
the needed in the minimal solutions.
And I have the opportunity to add two more
questions:
4. Can you disapprove the Enoch's
Conjecture?
5. Do
you devise an algorithm to obtain the minimal solutions
for a square pxp whenever the solution exists?
***
I have verified (with the help of a little
code) the Haga's solutions up to to 17x17 and found other up to the
31x31 squares. Enoch and myself  each one by his side, have devised
that some squares admit more than one minimal solution, preserving the same
mean.
***
Daniel Gronau makes two contributions to this
Conjecture:
1) regarding the algorithm asked in the
question 5:
If I understand question 4 of conjecture 26 right, there is an easy
answer: We are searching an 1:1 "assignment" from rows to columns,
and we want to use only some of the possible fields (the fields which are
prime) for this. If we treat the fields in the matrix as
"expenses" (and the prime fields are the cheap ones) we have an
optimization problem of the linear programming: the classical Assignment
Problem. All we have to do is to write 1 in every field containing a
composite number and 0 in every field containing a prime:
1 0 0 1 0
1 0 1 1 1
0 1 0 1 1
1 0 1 0 1
1 1 0 1 1
To get a minimal solution for an assignment with this "expense
matrix", we could use the Simplex or the Transport Algorithm, but there
is a special, easy and efficient algorithm only for this problem: the
Hungarian Method. It's an exact algorithm. If we got expenses equal 0, we
have a "Hagaminimal" solution.
I have asked to Daniel he to implement that
Hungarian method and advises to us if the Enoch Haga's conjecture
results confirmed or refuted
2) regarding my insinuation that a minimal
solution may be if p primes occur in the main diagonals he wrote:
... this is not right (how E.H. pointed out) this is also NOT POSSIBLE
for p>3. The main diagonal contains 1 and p², both not prime. And I sent
you the following proof that the other diagonal contains composites for
p>3:
There are p "diagonal numbers" D(n) = n*p  n + 1 in the
psquare (n = 1..p). Let q be prime and q < p. Then D(n) is composite if
D(n) = 0 mod q.
np  n + 1 = 0  mod q
np  n =  1  mod q
n(p  1) = 1  mod q
n(1  p) = 1  mod q
If p is not equal 1 mod q we can always find an n which solves the last
equation. The solution is smaller than q, hence smaller than p. So this D(n)
is IN the psquare. We have our first result:
(*) For every prime q smaller than p p must be 1 mod q or one of the D(n)
in the pquare is composite (and a multiple of q).
[Example: 7 = 2 mod 5, so n(1p) = 1 mod 5 has a solution: n = 4. So D(4)
= 25 is composite in the 7square and 525]
For every n >= 2 there is a prime p with n < p < 2n. Hence for
every prime p >= 5 there is a prime q with (p1)/2 < q < p1. So:
(p1)/2 < q
p1 < 2q
p < 2q + 1
And:
q < p1
q+1 < p
All together now:
q+1 < p < 2q+1
1 < pq < q+1
This means that p can never be 1 mod q. So for every prime p >= 5 we
can find a prime q violating the condition (*).
***
Daniel Gronau wrote:
I've tested the Hagaminimality for psquares (conjecture 26) up
to p = 2699. The "initial solution" found by a heuristic algorithm
was almost always the minimal solution. I try to speed up this part of code.
I think Enoch's conjecture is true, because growing p yields more and
more minimal solutions.
This is the "heuristic algorithm" devised by Daniel:
"...here is the the description of a heuristic for conjecture 26.
The algorithm is quite easy:
Let p = 7, so our square looks like (we can ignore composites):
 2 3  5  7
   11  13 
  17  19  
 23     
29  31    
 37    41 
43    47  
The trick is to get first "lonely" primes in the solution. We
count the number of primes in every row and column:
2 3 3 1 3 2 1
=====================
 2 3  5  7  4
   11  13   2
  17  19    2
 23       1
29  31      2
 37    41   2
43    47    2
Now we start to take the "best" primes first. I used the
criteria "minimal (row + column) value".
prime criteria
2 3+4=7
3 3+4=7
5 3+4=7
7 1+4=5
11 1+2=3 <
13 2+2=4
17 3+2=5
19 3+2=5
23 3+1=4
29 2+2=4
31 3+2=5
37 3+2=5
41 2+2=4
43 2+2=4
47 3+2=5
So we will take the prime 11, and cross out this row and column in the
matrix and the "lost" primes in our list:
 2 3 ## 5  7
####################
  17 ## 19  
 23  ##   
29  31 ##   
 37  ##  41 
43   ## 47  
prime criteria
2 7
3 7
5 7
7 5
17 5
19 5
23 4
29 4
31 5
37 5
41 3 < (corrected)
43 4
47 5
Because we've "lost" the prime 13, we must decrease the
criteria values for all primes in this row by 1. So
the 41 gets the new value 3. (This "correction" is only the short
way for counting the remaining primes in rows and columns again and making a
new list with criteria values) Now prime 41 is the best choice:
 2 3 ## 5 ## 7
####################
  17 ## 19 ## 
 23  ##  ## 
29  31 ##  ## 
## ## ## ## ## ## ##
43   ## 47 ## 
prime criteria
2 7
3 7
5 7
7 5
17 5
19 5
23 3 < (corrected)
29 4
31 5
43 4
47 5
Prime 23 was corrected because we've lost the 37. The best choice is now
23:
 ## 3 ## 5 ## 7
####################
 ## 17 ## 19 ## 
## ## ## ## ## ## ##
29 ## 31 ##  ## 
## ## ## ## ## ## ##
43 ##  ## 47 ## 
prime criteria
3 6 (corrected)
5 6 (corrected)
7 4 <(corrected)
17 5
19 5
29 4
31 5
43 4
47 5
We could take now the 7, the 29 or the 43. Let's take simply the first
one:
## ## ## ## ## ## ##
####################
 ## 17 ## 19 ## ##
## ## ## ## ## ## ##
29 ## 31 ##  ## ##
## ## ## ## ## ## ##
43 ##  ## 47 ## ##
prime criteria
17 4 < (corrected)
19 4 (corrected)
29 4
31 4 (corrected)
43 4
47 4 (corrected)
Again the first one (17):
## ## ## ## ## ## ##
####################
## ## ## ## ## ## ##
## ## ## ## ## ## ##
29 ## ## ##  ## ##
## ## ## ## ## ## ##
43 ## ## ## 47 ## ##
prime criteria
29 3 (corrected)
43 4
47 3 (corrected)
In the next two steps we would take 29 and 47. We had luck, all rows and
columns were deleted. So we got a "Hagaminimal" solution for the
7square: 7, 11, 17, 23, 29, 41, 47
***
Rudolph Knjzek sent the following
contribution to this conjecture:
"... Let p be the given prime number. I enumerate the rows of the
calendar from 1 to p and the numbers of the lines from 0 to p1. Row p
contains only one prime, namely p. Line 0 contains all primes q<=p. All
the other numbers can be written in the form n=a+bp with natural numbers a,b
less than p. a is the number of the row and b the number of the line.
Now the doubleconjecture can be written that way:
a) For all natural numbers a<p exists at least one natural number
b<p so that a+bp is prime.
b) For all natural numbers b<p exists at least one natural number
a<p so that a+bp is prime.
(what an amazing symmetry!)
How can we find the primes in a given line b?
I calculate all residues r of bp modulo q<p. The rownumber a must not
have the residues qr. Therefore I cut out all these numbers from the set
{1...(p1)}, similar to the Euclidean prime sieve.
The remaining numbers are the rows, containing primes, because all
numbers are less than p^2.
There is an example:
p=11
b=2
bp=22
22=0 (mod_2) => a!=0...cuts out 2,4,6,8,10
22=1 (mod_3) => a!=2...cuts out 2,5,8
22=2 (mod_5) => a!=3...cuts out 3,8
22=1 (mod_7) => a!=6...cuts out 6
The remaining values for row a are 1,7,9 and we find the primes 23,29,31.
How can we find the primes in a given row a?
There is a little more work to be done, but we also get one forbidden
remainder of b(mod_q) for every prime q<p. I'll show this in a small
example:
p=11
a=4
4+11b!=0 (mod_2) => b!=0...cuts out 2,4,6,8,10
4+11b!=0 (mod_3) => b!=1...cuts out 1,4,7
4+11b!=0 (mod_5) => b!=1...cuts out 1,6
4+11b!=0 (mod_7) => b!=6...cuts out 6
The remaining values for line b are 3,5,9 and we find the primes
37,59,103.
Clearly, this is no proof, but the probability that the set of p1
numbers gets empty when cutting out the numbers with the forbidden residues
is very small and it seems, the conjecture holds.
Maybe this is helpful for anybody, who tries to proof the conjecture.
***
One more time, Rudolph Knjzek contributed to this
conjecture with another argument:
I send you a contribution to conjecture 26 a). It is almost a
proof, but at least a heavy argument. I write this email in HTML and hope, you
can post the two diagrams on your site, because they are an essential part.
Between (a1)p and ab there are (p1) consecutive numbers.
We don't know, if they are composite or not. (a1)p and ap are
composite. If (a1) is odd, (a1)p1 is composite, because it is even. If
(a1) is even, a is odd and ap+1 is composite, because it is even. We have got
now a serie of (p+2) numbers, starting and ending with a save composite. Aguilar's
conjecture a) holds, if there are no composite series of length n>=(p+2)
starting with or before (p1)p.
There are computed values of c(n), the first number of the
first composite serie of length n. Aguilar's conjecture a) is true, if
c(n)>(n1)(n3) for all n.
Cramer and Shanks conjectured:
c(n) ~ exp(sqrt(n))
I'll better write this as an inequation:
c(n) > exp(sqrt(n))
Wolf conjectured:
c(n) ~ sqrt(n)exp(sqrt(n))
The two diagrams show the logarithm of these values and (n1)(n3).
If c(n)>exp(sqrt(n)) holds for all the
larger values of n  and there is no doubt looking at the diagrams  ,
Aguilar's conjecture holds for p>69. For p<69 the computed values show,
that Aguilar' conjecture is true. For p=11 and n=13 c(n)=114 and
(p1)p=110. This is the most critical point, but 114>110 and the conjecture
is true for p=11
***
