cp's OEIS Frontend

A340068 a(n) is the number of integers in the set {n+1,n+2, . . . ,2n} whose representation in base 2 contain exactly three digits 1’s.

%I A340068 #31 Mar 11 2025 17:31:51
%S A340068 0,0,0,1,1,2,3,3,3,4,5,5,6,6,6,6,6,7,8,8,9,9,9,9,10,10,10,10,10,10,10,
%T A340068 10,10,11,12,12,13,13,13,13,14,14,14,14,14,14,14,14,15,15,15,15,15,15,
%U A340068 15,15,15,15,15,15,15,15,15,15,15,16,17,17,18,18,18,18,19
%N A340068 a(n) is the number of integers in the set {n+1,n+2, . . . ,2n} whose representation in base 2 contain exactly three digits 1’s.
%C A340068 This sequence is inspired by the 3rd problem, proposed by Romania, during the 35th International Mathematical Olympiad in 1994 at Hong Kong (see the link IMO).
%C A340068 This sequence is increasing because there are only these two possibilities:
%C A340068 -> a(n+1) - a(n) = 1 if n has exactly two 1's in its binary representation (A018900);
%C A340068 -> a(n+1) - a(n) = 0 otherwise.
%C A340068 Consequence, for any positive integer m, a(x) = m has at least one solution (answer to the 1st Olympiad question).
%C A340068 Only when m = k*(k-1)/2 + 1 with k >= 2 (A000124 \ {1}), there exists only one n such that a(n) = m, and then n = 2^k+2 where k >= 2 (A052548 \ {3, 4}) (answer to the 2nd Olympiad question).
%D A340068 Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 10 and 92-93.
%H A340068 The IMO Compendium, <a href="https://imomath.com/othercomp/I/Imo1994.pdf">Problem 3</a>, 35th IMO 1994.
%H A340068 <a href="/index/O#Olympiads">Index to sequences related to Olympiads</a>.
%F A340068 a(2^k+2) = k*(k-1)/2 + 1 for k >= 2.
%e A340068 a(2) = 0 because in {3, 4}, 3 = 11_2 and 4 = 100_2.
%e A340068 a(4) = 1 because in {5, 6, 7, 8, 9, 10} only 7 = 111_2 has 3 digits in its binary representation.
%e A340068 a(6) = 2 because in {7, 8, 9, 10, 11, 12}, there are 7 = 111_2 and 11 = 1011_2 that have 3 digits in their binary representation.
%t A340068 a[n_] := Count[Range[n + 1, 2*n], _?(DigitCount[#, 2, 1] == 3 &)]; Array[a, 100] (* _Amiram Eldar_, Dec 28 2020 *)
%o A340068 (Python)
%o A340068 def a(n): return sum(bin(k)[2:].count("1")==3 for k in range(n+1, 2*n+1))
%o A340068 print([a(n) for n in range(1, 68)]) # _Michael S. Branicky_, Dec 28 2020
%o A340068 (Python)
%o A340068 def A340068(n): return sum(1 for k in range(n) if k.bit_count()==2) # _Chai Wah Wu_, Mar 11 2025
%o A340068 (PARI) a(n) = sum(k=n+1, 2*n, hammingweight(k) == 3); \\ _Michel Marcus_, Dec 28 2020
%o A340068 (PARI) first(n) = {my(res = vector(n), t = 0); for(i = 1, n, res[i] = t; if(hammingweight(i) == 2, t++)); res} \\ _David A. Corneth_, Dec 29 2020
%Y A340068 Cf. A000120, A014311, A018900, A057168, A151774 (first differences).
%K A340068 nonn,base,easy
%O A340068 1,6
%A A340068 _Bernard Schott_, Dec 28 2020
%E A340068 More terms from _David A. Corneth_, Dec 28 2020