A099244 Greatest common divisor of length of n in binary representation and its number of ones.

1, 1, 2, 1, 1, 1, 3, 1, 2, 2, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 1, 2, 2, 3, 2, 3, 3, 2, 2, 3, 3, 2, 3, 2, 2, 1, 2, 3, 3, 2, 3, 2, 2, 1, 3, 2, 2, 1, 2, 1, 1, 6, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Author

Reinhard Zumkeller, Oct 08 2004

Keywords

• base
• easy
• nonn

Comments

For k >= 2, n in the range [2^(k-1)..2^k - 2] have binary length k but fewer than k 1's, thus a(n) is a proper divisor of k, and if k is a prime then a(n) = 1. - Ctibor O. Zizka, Jun 19 2021

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to binary expansion of n.

Crossrefs

Cf. A000120, A000225, A007088, A070939, A099245, A099246, A099247, A099248, A099249.

Programs

Haskell

a099244 n = gcd (a070939 n) (a000120 n)
-- Reinhard Zumkeller, Oct 10 2013

Mathematica

a[n_] := GCD[BitLength[n], DigitCount[n, 2, 1]]; Array[a, 100] (* Amiram Eldar, Jul 16 2023 *)

PARI

a(n) = {my(b = binary(n)); gcd(#b, vecsum(b));} \\ Amiram Eldar, Jul 26 2025

Python

from math import gcd
def a(n): b = bin(n)[2:]; return gcd(len(b), b.count('1'))
print([a(n) for n in range(1, 106)]) # Michael S. Branicky, Jun 17 2021

Formula

a(n) = gcd(A070939(n), A000120(n)).

a(A000225(n)) = n and a(m) < n for m < A000225(n).