login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A071764
Number of minimal rectangular envelopes (up to rotation) that enclose n contiguous squares.
2
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
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
KEYWORD
easy,nonn
AUTHOR
Benoit Cloitre, Jun 04 2002
STATUS
approved