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. 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.
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
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 *)
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*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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Zacariaz Martinez, Nov 15 2006
EXTENSIONS
Extended by Robert G. Wilson v, Jan 19 2007
STATUS
approved