|
|
A261176
|
|
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.
|
|
1
|
|
|
0, 9, 126, 802, 3158, 10040, 25464, 58837, 123422, 238203, 429467, 733923, 1200319, 1912928, 2945116, 4369570, 6338678, 9053512, 12622814, 17359779, 23503546, 31347788, 41161317
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
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.
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).
All terms beyond a(5) are conjectured based on numerical results. Terms up to a(17) have at least 5 independent verifications.
Upper bounds for the next terms are a(24)<=53670478, a(25)<=68938808, a(26)<=87777189, a(27)<=110759499.
|
|
LINKS
|
|
|
EXAMPLE
|
a(2)=9, because the matrix ((1 2)(3 4)) has Delacorte Number
D(1,2) + D(1,3) + D(1,4) + D(2,3) + D(2,4) + D(3,4) =
gcd(1,2)*(1^2 + 0^2) +
gcd(1,3)*(0^2 + 1^2) +
gcd(1,4)*(1^2 + 1^2) +
gcd(2,3)*(1^2 + 1^2) +
gcd(2,4)*(0^2 + 1^2) +
gcd(3,4)*(1^2 + 0^2) = 1*1 + 1*1 + 1*2 + 1*2 + 2*1 + 1*1 = 9.
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.
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)).
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,hard
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|