A123663 Number of shared edges in a spiral of n unit squares.

0, 1, 2, 4, 5, 7, 8, 10, 12, 13, 15, 17, 18, 20, 22, 24, 25, 27, 29, 31, 32, 34, 36, 38, 40, 41, 43, 45, 47, 49, 50, 52, 54, 56, 58, 60, 61, 63, 65, 67, 69, 71, 72, 74, 76, 78, 80, 82, 84, 85, 87, 89, 91, 93, 95, 97, 98, 100, 102, 104, 106, 108, 110, 112, 113, 115, 117, 119

Offset: 1

Author

Zacariaz Martinez, Nov 15 2006

Keywords

• easy
• nonn

Comments

If one constructs a square (square 1) and then draws another square of identical size beside it (square 2), the squares share 1 edge. If one then places an identical square above square 2 (instead of continuing in a straight path), there are now 2 shared edges. Continuing this pattern in an outward spiral, one finds that the number of shared edges is 4, 5, 7, ...

Numbers a(n) such that a(n+1) = a(n) + 1 are (except for the leading zero) A074148. Otherwise a(n+1) = a(n) + 2. - Franklin T. Adams-Watters, Oct 17 2014.

This sequence is also the maximal number of shared edges among all polyominoes with n square cells. This is the result of Harary and Harborth cited in the references. Once this is known the formula 2n - ceiling(2*sqrt(n)) comes from geometrical considerations and A027709. Namely, the 4n sides of the n squares making up the polyomino form the perimeter and come together in pairs along shared edges. Hence, 4n = perimeter + 2*shared edges. Maximizing shared edges minimizes perimeter and so maximum shared edges = (4n - minimum perimeter)/2 = (4n - 2ceiling(2*sqrt(n)))/2 = 2n - ceiling(2*sqrt(n)). This interpretation is important to landscape ecologists and is called the aggregation index in the GIS program FRAGSTATS. - Julian F. Fleron, Nov 29 2016

a(n) is also the maximum degree of the cover graphs of lattice quotients of lattice congruences of the weak order on the symmetric group S_n. See Table 1 in the Hoang/Mütze reference in the Links section. - Torsten Muetze, Nov 28 2019

a(n) is also the number of pixels in H_{n-1}, where H_n (a pixelated piece of hyperbola x*y = n) is the set of the (x, y), ordered pairs of positive integers, such that x*y = n or (x*y < n and ((x+1)*y > n or x*(y+1) > n)). - Luc Rousseau, Dec 28 2019

References

• F. Harary and H. Harborth, Extremal Animals, Journal of Combinatorics, Information & System Sciences, Vol. 1, No 1, 1-8 (1976).

Links

• Peter Kagey, Table of n, a(n) for n = 1..10000
• Richard A. Brualdi and Geir Dahl, Frobenius-König theorem for classes of (0,+/-1)-matrices, Disc. Math. (2024) Vol. 347, Issue 6, 113951.
• Hung Phuc Hoang and Torsten Mütze, Combinatorial generation via permutation languages. II. Lattice congruences, arXiv:1911.12078 [math.CO], 2019.

Crossrefs

Cf. A002620.

Programs

Maple

A[1]:= 0:
for n from 2 to 100 do
  if issqr(2*A[n-1]+1) or issqr(2*A[n-1]+2) then A[n]:= A[n-1]+1
  else A[n]:= A[n-1]+2
  fi
od:
seq(A[n],n=1..100); # Robert Israel, Oct 21 2014

Mathematica

FoldList[Plus, 0, t = Table[2, {72}]; t[[ Table[ Ceiling[n/2] Floor[n/2], {n, 2, 16}] ]]--; t] (* Robert G. Wilson v, Jan 19 2007 *)

PARI

a(n)=2*n - sqrtint(4*n-1) - 1 \\ Charles R Greathouse IV, Nov 29 2016

Python

from math import isqrt
def A123663(n): return (m:=n<<1)-1-isqrt((m<<1)-1) # Chai Wah Wu, Jul 28 2022

Ruby

a123663 = [0]; k = 0; a_n = 0; (1..N).to_a.each{ |i| 2.times{ k.times{ a_n += 2; a123663 << a_n }; a_n += 1; a123663 << a_n; }; k += 1}

Formula

a(n) = 2n - ceiling(2*sqrt(n)). - Julian F. Fleron, Nov 29 2016

a(n) = a(n-1) + 2 - [n-1 is a square or a pronic number], where [] stands for the Iverson bracket. - Luc Rousseau, Dec 28 2019

Extensions

Extended by Robert G. Wilson v, Jan 19 2007