login
Number of minimal rectangular envelopes (up to rotation) that enclose n contiguous squares.
2

%I #20 Oct 31 2023 12:44:21

%S 1,1,1,2,3,4,6,8,11,14,17,21,26,30,36,42,48,54,62,69,78,86,95,105,116,

%T 125,136,148,160,172,186,198,213,227,242,258,274,288,306,324,342,359,

%U 379,397,418,438,458,480,503,523,546,569,593,617,643,667,693,718,745

%N Number of minimal rectangular envelopes (up to rotation) that enclose n contiguous squares.

%C Equivalently, number of distinct envelopes up to rotation of the polyominoes of order n, n >= 0. - _Francois Alcover_, Feb 28 2017

%C a(n) is the number of times that the statement "x + y <= n + 1 and x * y >= n" is true, for x taking values from 1 to n, and y taking values from x to n. - _John Mason_, Feb 25 2022

%H K. S. Brown, <a href="http://www.mathpages.com/home/kmath039.htm">More info</a>

%F a(n) = (1/2)*( A000217(n) + A008619(n)- A000196(n-1) - A006218(n-1) ).

%F Recurrence : a(n) = a(n-1) + {n/2} - {tau(n-1)/2} where {x} signifies the least integer greater than or equal to x, tau(x) the number of divisors of x.

%e From _Francois Alcover_, Feb 28 2017: (Start)

%e a(3) = 2:

%e The two possible envelopes are

%e |*|

%e |*|

%e |*| [3,1]

%e and

%e |*| |

%e |*|*| [2,2] (End)

%t a[0] = 1; a[n_] := (1/2)*(Floor[(n+1)/2] - Floor[Sqrt[n-1]] + n*(n+1)/2 - Sum[Floor[(n-1)/i], {i, 1, n}]); Table[a[n], {n, 0, 58}] (* _Jean-François Alcover_, Feb 01 2018, from PARI *)

%o (PARI) for(n=1,100,print1(1/2*(n*(n+1)/2+floor((n+1)/2)-floor(sqrt(n-1))-sum(i=1,n,floor((n-1)/i))),","))

%o (Python)

%o from math import isqrt

%o def A071764(n): return ((s:=isqrt(n-1))*(s-1)+1+(n>>1)+(n*(n+1)>>1)>>1)-sum((n-1)//k for k in range(1,s+1)) if n else 1 # _Chai Wah Wu_, Oct 31 2023

%K easy,nonn

%O 0,4

%A _Benoit Cloitre_, Jun 04 2002