OFFSET
1,2
COMMENTS
Rectangles can be placed in any orientation and in particular their sides are not required to be parallel to the sides of the square.
Condition for rectangles L X W which have length L > n: n - L/sqrt(2) > W/sqrt(2) where L/sqrt(2) and W/sqrt(2) are projections on the n X n square's sides.
EXAMPLE
For n = 3 there are 6 distinct sizes of rectangle that can be placed into a 3 X 3 square:
... ... ... ... ... ###
... ... ... ##. ### ###
#.., ##., ###, ##., ###, ###
For n = 8 there are 36 distinct sizes of rectangle that can be placed with their sides parallel to the sides of the square; in addition, 9 X 1, 9 X 2 and 10 X 1 rectangles can also be placed. Hence a(8) = 39.
PROG
(C++)
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int main() {
int n;
cin>>n;
vector <int> v;
for (int i=1; i<=n; i++)
{int count=0;
for (int j=1; j<=i; j++)
for (int k=j; k<=i; k++)
{count++; }
//Diagonally placed ii-length, jj-width of diagonal rectangle
for (int ii=i+1; ii<=int(sqrt(2)*i); ii++)
for (int jj=1; jj<=i; jj++)
if ((double(i)-double(ii)/sqrt(2))-double(jj)/sqrt(2)>0)
{ count++; }
v.push_back(count);
}
for (int i=0; i<v.size(); i++) cout << v[i] << ", ";
return 0;
}
CROSSREFS
KEYWORD
nonn
AUTHOR
Kirill Ustyantsev, Aug 23 2019
STATUS
approved