A331532 a(n) is the number of nonnegative integers k such that (n^2) AND (k^2) = k^2 (where AND denotes the bitwise AND operator).

1, 2, 2, 3, 2, 5, 3, 4, 2, 5, 5, 9, 3, 4, 4, 4, 2, 4, 5, 7, 5, 12, 9, 4, 3, 9, 4, 11, 4, 7, 4, 6, 2, 5, 4, 7, 5, 12, 7, 15, 5, 7, 12, 13, 9, 17, 4, 3, 3, 7, 9, 4, 4, 20, 11, 15, 4, 8, 7, 12, 4, 5, 6, 6, 2, 4, 5, 7, 4, 11, 7, 14, 5, 12, 12, 29, 7, 8, 15, 5, 5

Offset: 0

Author

Rémy Sigrist, Jan 19 2020

Keywords

• nonn
• base

Comments

Equivalently, this is the number of nonnegative integers k such that (n^2) OR (k^2) = n^2 (where OR denotes the bitwise OR operator); this connects this sequence to A001316.

Examples

			For n = 7:
- we have:
  k  7^2 AND k^2
  -  -----------
  0  0 = 0
  1  1 = 1
  2  0 <> 4
  3  1 <> 9
  4  16 = 16
  5  17 <> 25
  6  32 <> 36
  7  49 = 49
- hence a(7) = 4.
		

Links

• Rémy Sigrist, Table of n, a(n) for n = 0..8192
• Rémy Sigrist, Scatterplot of (x, y) such that (x^2) AND (y^2) = y^2, with 0 <= x <= 1024

Crossrefs

Cf. A001316, A331533 (corresponding k's).

Programs

PARI

a(n) = sum(k=0, n, bitand(n^2, k^2)==k^2)

Formula

a(2^k) = 2 for any k >= 0.

a(n) <= n+1.