Problems & Puzzles: Conjectures
Conjecture 26. The Calendar-like square Conjecture
Julio Cesar Aguilar, from México, has the following double-conjecture:
For example if p=5, this is the calendar-like square and the primes inside:
1. Can you find a counterexample?
Luis Rodríguez wrote (17/11/01):
As a matter of fact, The Sierpinski's Conjecture (S), in the Ribenboim book says:
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:
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 column-conjecture 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:
Enoch has gotten - by trial an error - the minimal solutions for squares 11x11, 13x13, 17x17 and obviously has made the following conjecture:
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:
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:
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 p-square (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
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 p-square. 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 p-quare is composite (and a multiple of q).
[Example: 7 = 2 mod 5, so n(1-p) = 1 mod 5 has a solution: n = 4. So D(4) = 25 is composite in the 7-square and 5|25]
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 (p-1)/2 < q < p-1. So:
(p-1)/2 < q
q < p-1
All together now:
q+1 < p < 2q+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:
This is the "heuristic algorithm" devised by Daniel:
number of primes in every row and column:
2 3 3 1 3 2 1
-- 2 3 -- 5 -- 7 | 4
Now we start to take the "best" primes first. I used the criteria "minimal(row + column) value".
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
Because we've "lost" the prime 13, we must decrease the criteria values forall 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
Prime 23 was corrected because we've lost the 37. The best choice is now 23:
-- ## 3 ## 5 ## 7
3 6 (corrected)
We could take now the 7, the 29 or the 43. Let's take simply the first one:
## ## ## ## ## ## ##
17 4 <- (corrected)
Again the first one (17):
## ## ## ## ## ## ##
29 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 "Haga-minimal" solution for the 7-square: 7, 11, 17, 23, 29, 41, 47
Rudolph Knjzek sent the following contribution to this 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 (a-1)p and ab there are (p-1) consecutive numbers.
We don't know, if they are composite or not. (a-1)p and ap are
composite. If (a-1) is odd, (a-1)p-1 is composite, because it is even. If
(a-1) 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 (p-1)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)>(n-1)(n-3) for all n.
Cramer and Shanks conjectured:
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 (p-1)p=110. This is the most critical point, but 114>110 and the conjecture is true for p=11