%I #21 Mar 06 2014 03:41:48
%S 1,4,11,23,43,71,103
%N 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.
%C 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.)
%C a(6) = 71 is equal to the lower bound and is attained, for example, by
%C {{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
%H "mobel", <a href="http://mymathforum.com/viewtopic.php?f=40&t=46118&p=193328">Board n x n and coprimality</a>, 2014.
%H Charles R Greathouse IV, <a href="/A237586/a237586.txt">Conjectured terms up to 1000</a>
%F n^2 <= a(n) < prime(n^2).
%e The unique 2 X 2 grid, up to symmetries:
%e 1 2
%e 4 3
%e A 3 X 3 grid:
%e 1 2 3
%e 4 9 5
%e 7 11 8
%e These demonstrate that a(2) <= 4 and a(3) <= 11.
%e A 7 X 7 grid:
%e 2 9 95 77 71 73 79
%e 13 4 27 85 11 83 89
%e 17 23 8 81 65 97 101
%e 19 29 91 16 93 55 103
%e 61 31 1 43 32 87 35
%e 5 49 37 47 53 64 69
%e 3 25 41 59 7 67 94
%o (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
%o (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
%K nonn,more
%O 1,2
%A _Charles R Greathouse IV_, Feb 09 2014
%E a(6) from _Giovanni Resta_, Feb 09 2014
%E a(7) from _Charles R Greathouse IV_, Feb 19 2014