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

%I #36 Jul 16 2023 02:05:46

%S 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,

%T 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,

%U 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

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

%C 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

%H Reinhard Zumkeller, <a href="/A099244/b099244.txt">Table of n, a(n) for n = 1..10000</a>

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

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

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

%t a[n_] := GCD[BitLength[n], DigitCount[n, 2, 1]]; Array[a, 100] (* _Amiram Eldar_, Jul 16 2023 *)

%o (Haskell)

%o a099244 n = gcd (a070939 n) (a000120 n)

%o -- _Reinhard Zumkeller_, Oct 10 2013

%o (Python)

%o from math import gcd

%o def a(n): b = bin(n)[2:]; return gcd(len(b), b.count('1'))

%o print([a(n) for n in range(1, 106)]) # _Michael S. Branicky_, Jun 17 2021

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

%K base,easy,nonn

%O 1,3

%A _Reinhard Zumkeller_, Oct 08 2004