

A123663


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


8



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


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. AdamsWatters, 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_{n1}, 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, 18 (1976).


LINKS

Peter Kagey, Table of n, a(n) for n = 1..10000
Hung Phuc Hoang and Torsten Mütze, Combinatorial generation via permutation languages. II. Lattice congruences, arXiv:1911.12078 [math.CO], 2019.


FORMULA

a(n) = 2n  ceiling(2*sqrt(n)).  Julian F. Fleron, Nov 29 2016
a(n) = a(n1) + 2  [n1 is a square or a pronic number], where [] stands for the Iverson bracket.  Luc Rousseau, Dec 28 2019


MAPLE

A[1]:= 0:
for n from 2 to 100 do
if issqr(2*A[n1]+1) or issqr(2*A[n1]+2) then A[n]:= A[n1]+1
else A[n]:= A[n1]+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 *)


PROG

(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}
(PARI) a(n)=2*n  sqrtint(4*n1)  1 \\ Charles R Greathouse IV, Nov 29 2016
(Python)
from math import isqrt
def A123663(n): return (m:=n<<1)1isqrt((m<<1)1) # Chai Wah Wu, Jul 28 2022


CROSSREFS

Cf. A002620.
Sequence in context: A195126 A047496 A223735 * A174131 A014248 A174799
Adjacent sequences: A123660 A123661 A123662 * A123664 A123665 A123666


KEYWORD

easy,nonn


AUTHOR

Zacariaz Martinez, Nov 15 2006


EXTENSIONS

Extended by Robert G. Wilson v, Jan 19 2007


STATUS

approved



