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,4

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

Links

Table of n, a(n) for n=0..58.

K. S. Brown, More info

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.

Example

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

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

Prog

(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

Crossrefs

Sequence in context: A371069 A056829 A211536 * A238381 A290743 A059291

Adjacent sequences: A071761 A071762 A071763 * A071765 A071766 A071767

Keyword

easy,nonn

Author

Benoit Cloitre, Jun 04 2002

Status

approved