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

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, 125, 136, 148, 160, 172, 186, 198, 213, 227, 242, 258, 274, 288, 306, 324, 342, 359, 379, 397, 418, 438, 458, 480, 503, 523, 546, 569, 593, 617, 643, 667, 693, 718, 745

Offset: 0

Author

Benoit Cloitre, Jun 04 2002

Keywords

• easy
• nonn

Comments

Equivalently, number of distinct envelopes up to rotation of the polyominoes of order n, n >= 0. - Francois Alcover, Feb 28 2017

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

Examples

			From _Francois Alcover_, Feb 28 2017: (Start)
a(3) = 2:
The two possible envelopes are
|*|
|*|
|*| [3,1]
and
|*| |
|*|*| [2,2] (End)
		

Links

• K. S. Brown, More info

Programs

Mathematica

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 *)

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))),","))

Python

from math import isqrt
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

Formula

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

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.