A362706 Number of squares formed by first n vertices of the infinite-dimensional hypercube.

0, 0, 0, 1, 1, 2, 3, 6, 6, 7, 9, 13, 16, 21, 27, 36, 36, 37, 40, 45, 50, 57, 66, 78, 85, 94, 106, 121, 136, 154, 175, 200, 200, 201, 205, 211, 219, 229, 242, 258, 271, 286, 305, 327, 351, 378, 409, 444, 463, 484, 510, 539, 571, 606, 646, 690, 729, 771, 819

Offset: 1

Author

Hugo van der Sanden, Jun 22 2023

Keywords

• nonn

Comments

We can take the coordinates of a vertex to represent a binary number, so we define the n-th point to have coordinates represented by the binary expansion of n-1.

Let d(m) = a(m+1) - a(m) be the shifted first differences of a(n), so that d(m) represents the additional squares introduced by the (m+1)-th vertex. Then d(0) = d(2^x) = 0; when m = 2^x + 2^y, x > y, d(m) = A115990(x - 1, x - y - 1); generally, d(m) = sum d(k) for all k formed by selecting two 1's from the binary expansion of m. Thus d(7) = d(3) + d(5) + d(6).

a(n) is a lower bound for an infinite-dimensional extension of A051602. Peter Munn notes that it is not an upper bound: for example, the vertices of a regular {k-1}-simplex duplicated at unit distance in any orthogonal direction gives T_k squares from 2k+2 points, which exceeds a(n) at 6, 10 and 12 points.

Examples

			The 6 points (0,0,0), (1,0,0), (0,1,0), (1,1,0), (0,0,1), (1,0,1) give the squares (0,0,0), (1,0,0), (0,1,0), (1,1,0) and (0,0,0), (1,0,0), (0,0,1), (1,0,1). So a(6) = 2.
		

Crossrefs

Cf. A345340, A115990, A051602.

Formula

a(2^k) = A345340(k).