login
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

%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&amp;t=46118&amp;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