|
%I #60 Mar 08 2024 09:45:13
%S 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,
%T 41,43,45,47,49,50,52,54,56,58,60,61,63,65,67,69,71,72,74,76,78,80,82,
%U 84,85,87,89,91,93,95,97,98,100,102,104,106,108,110,112,113,115,117,119
%N Number of shared edges in a spiral of n unit squares.
%C 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, ...
%C 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.
%C 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
%C 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
%C 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
%D F. Harary and H. Harborth, Extremal Animals, Journal of Combinatorics, Information & System Sciences, Vol. 1, No 1, 1-8 (1976).
%H Peter Kagey, <a href="/A123663/b123663.txt">Table of n, a(n) for n = 1..10000</a>
%H Richard A. Brualdi and Geir Dahl, <a href="https://doi.org/10.1016/j.disc.2024.113951">Frobenius-König theorem for classes of (0,+/-1)-matrices</a>, Disc. Math. (2024) Vol. 347, Issue 6, 113951.
%H Hung Phuc Hoang and Torsten Mütze, <a href="https://arxiv.org/abs/1911.12078">Combinatorial generation via permutation languages. II. Lattice congruences</a>, arXiv:1911.12078 [math.CO], 2019.
%F a(n) = 2n - ceiling(2*sqrt(n)). - _Julian F. Fleron_, Nov 29 2016
%F 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
%p A[1]:= 0:
%p for n from 2 to 100 do
%p if issqr(2*A[n-1]+1) or issqr(2*A[n-1]+2) then A[n]:= A[n-1]+1
%p else A[n]:= A[n-1]+2
%p fi
%p od:
%p seq(A[n],n=1..100); # _Robert Israel_, Oct 21 2014
%t 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 *)
%o (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}
%o (PARI) a(n)=2*n - sqrtint(4*n-1) - 1 \\ _Charles R Greathouse IV_, Nov 29 2016
%o (Python)
%o from math import isqrt
%o def A123663(n): return (m:=n<<1)-1-isqrt((m<<1)-1) # _Chai Wah Wu_, Jul 28 2022
%Y Cf. A002620.
%K easy,nonn
%O 1,3
%A _Zacariaz Martinez_, Nov 15 2006
%E Extended by _Robert G. Wilson v_, Jan 19 2007
|
