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

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.

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

Formula

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

a(n) <= n+1.

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A084371 A025476 A347731 * A078773 A151663 A162753

Adjacent sequences: A331529 A331530 A331531 * A331533 A331534 A331535

Keyword

nonn,base

Author

Rémy Sigrist, Jan 19 2020

Status

approved