login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..23.

Al Zimmermann's Programming Contests, Delacorte Numbers, Description, October 2014.

Al Zimmermann's Programming Contests, Delacorte Numbers, Final Report, January 2015.

The New York Community Trust: George T. Delacorte.

Arch D. Robison, Computing Delacorte Numbers with Julia, January 21, 2015.

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

Cf. A261177, A003989, A018782.

Sequence in context: A224495 A064199 A092343 * A261743 A229283 A144073

Adjacent sequences:  A261173 A261174 A261175 * A261177 A261178 A261179

KEYWORD

nonn,hard

AUTHOR

Hugo Pfoertner, Aug 15 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 8 08:54 EDT 2020. Contains 333313 sequences. (Running on oeis4.)