|
%I #17 Aug 27 2015 16:54:12
%S 0,9,126,802,3158,10040,25464,58837,123422,238203,429467,733923,
%T 1200319,1912928,2945116,4369570,6338678,9053512,12622814,17359779,
%U 23503546,31347788,41161317
%N Minimum value of (1/2)*Sum_{i=1..n} Sum_{j=1..n} Sum_{k=1..n} Sum_{l=1..n} gcd(b(i,j),b(k,l)) * ((i-k)^2+(j-l)^2) for an n X n matrix b filled with the integers 1 to n^2.
%C In one of his programming contests, Al Zimmermann coined the term "Delacorte Numbers" (after G. T. Delacorte, Jr., a New York City philantropist and benefactor) for the sum of D(a,b) = gcd(a,b) * distance^2(a,b), taken over all distinct pairs of integers (a,b) in a rectangular matrix.
%C The challenge in the contest was to find two kinds of arrangements of 1 to n^2, one minimizing the combined sum (this sequence) and the other maximizing the combined sum (A261177).
%C All terms beyond a(5) are conjectured based on numerical results. Terms up to a(17) have at least 5 independent verifications.
%C Upper bounds for the next terms are a(24)<=53670478, a(25)<=68938808, a(26)<=87777189, a(27)<=110759499.
%H Al Zimmermann's Programming Contests, <a href="http://azspcs.com/Contest/DelacorteNumbers">Delacorte Numbers</a>, Description, October 2014.
%H Al Zimmermann's Programming Contests, <a href="http://azspcs.com/Contest/DelacorteNumbers/FinalReport">Delacorte Numbers</a>, Final Report, January 2015.
%H The New York Community Trust: <a href="http://www.nycommunitytrust.org/Portals/0/Uploads/Documents/Public/GeorgeTDelacorte.pdf">George T. Delacorte.</a>
%H Arch D. Robison, <a href="https://software.intel.com/en-us/articles/computing-delacorte-numbers-with-julia">Computing Delacorte Numbers with Julia</a>, January 21, 2015.
%e a(2)=9, because the matrix ((1 2)(3 4)) has Delacorte Number
%e D(1,2) + D(1,3) + D(1,4) + D(2,3) + D(2,4) + D(3,4) =
%e gcd(1,2)*(1^2 + 0^2) +
%e gcd(1,3)*(0^2 + 1^2) +
%e gcd(1,4)*(1^2 + 1^2) +
%e gcd(2,3)*(1^2 + 1^2) +
%e gcd(2,4)*(0^2 + 1^2) +
%e gcd(3,4)*(1^2 + 0^2) = 1*1 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 = 9.
%e Putting (2,4) in a row or column gives the minimum value of the matrix, whereas putting this pair in one of the diagonals gives the maximum.
%e a(3)=126, because no arrangement of the matrix elements exists that produces a smaller Delacorte Number than e.g. ((1 2 4)(3 6 8)(5 9 7)).
%Y Cf. A261177, A003989, A018782.
%K nonn,hard
%O 1,2
%A _Hugo Pfoertner_, Aug 15 2015
| 