|
| |
|
|
A237586
|
|
Arrange n^2 distinct positive integers in an n X n grid so that numbers on a given row or column are pairwise coprime. a(n) gives the smallest number which can be the maximal value on such a grid.
|
|
1
|
| |
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
By definition at most n elements in the grid can be divisible by any given prime. This can be used to show that a(3) >= 11 with p = 2, a(4) >= 23 with p = 2, and a(5) >= 43 with p in {2, 3}. Is it true that this lower bound over {2}, {2, 3}, {2, 3, 5}, and so on is equal to a(n) for n > 2? (It should suffice to go up to the primes below n^2.)
a(6) = 71 is equal to the lower bound and is attained, for example, by
{{69, 68, 65, 67, 61, 59}, {62, 63, 71, 55, 53, 47}, {35, 43, 58, 57, 41, 37}, {29, 31, 51, 52, 49, 25}, {19, 23, 11, 17, 50, 39}, {13, 5, 7, 1, 33, 46}}. - Giovanni Resta, Feb 09 2014
|
|
|
LINKS
|
|
|
|
FORMULA
|
n^2 <= a(n) < prime(n^2).
|
|
|
EXAMPLE
|
The unique 2 X 2 grid, up to symmetries:
1 2
4 3
A 3 X 3 grid:
1 2 3
4 9 5
7 11 8
These demonstrate that a(2) <= 4 and a(3) <= 11.
A 7 X 7 grid:
2 9 95 77 71 73 79
13 4 27 85 11 83 89
17 23 8 81 65 97 101
19 29 91 16 93 55 103
61 31 1 43 32 87 35
5 49 37 47 53 64 69
3 25 41 59 7 67 94
|
|
|
PROG
|
(PARI) lower(n)=if(n==2, return(4)); my(P=1, pi, s, t, best); forprime(p=2, n^2, t=1; P*=p; s=n^2-1-n*pi++; while(s>0, while(gcd(t++, P)>1, ); s--); best=max(t, best)); best \\ Gives a lower bound
(PARI) check(M)=for(i=1, #M[, 1], for(j=1, #M[1, ], if(#select(n->gcd(M[i, j], n)>1, M[, j])>1 || #select(n->gcd(M[i, j], n)>1, M[i, ])>1, return([i, j])))); 0 \\ Checks if a matrix is valid; Charles R Greathouse IV, Feb 19 2014
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
