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.

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, 10, 10, 11, 12, 12, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 17, 17, 18, 18, 18, 18, 19

Offset: 1

Author

Bernard Schott, Dec 28 2020

Keywords

• nonn
• base
• easy

Comments

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).

This sequence is increasing because there are only these two possibilities:

-> a(n+1) - a(n) = 1 if n has exactly two 1's in its binary representation (A018900);

-> a(n+1) - a(n) = 0 otherwise.

Consequence, for any positive integer m, a(x) = m has at least one solution (answer to the 1st Olympiad question).

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).

Examples

			a(2) = 0 because in {3, 4}, 3 = 11_2 and 4 = 100_2.
a(4) = 1 because in {5, 6, 7, 8, 9, 10} only 7 = 111_2 has 3 digits in its binary representation.
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.
		

References

• Marcin E. Kuczma, International Mathematical Olympiads, 1986-1999, The Mathematical Association of America, 2003, pages 10 and 92-93.

Links

• The IMO Compendium, Problem 3, 35th IMO 1994.
• Index to sequences related to Olympiads.

Crossrefs

Cf. A000120, A014311, A018900, A057168, A151774 (first differences).

Programs

Mathematica

a[n_] := Count[Range[n + 1, 2*n], ?(DigitCount[#, 2, 1] == 3 &)]; Array[a, 100] (* _Amiram Eldar, Dec 28 2020 *)

PARI

a(n) = sum(k=n+1, 2*n, hammingweight(k) == 3); \\ Michel Marcus, Dec 28 2020

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

Python

def a(n): return sum(bin(k)[2:].count("1")==3 for k in range(n+1, 2*n+1))
print([a(n) for n in range(1, 68)]) # Michael S. Branicky, Dec 28 2020

Python

def A340068(n): return sum(1 for k in range(n) if k.bit_count()==2) # Chai Wah Wu, Mar 11 2025

Formula

a(2^k+2) = k*(k-1)/2 + 1 for k >= 2.

Extensions

More terms from David A. Corneth, Dec 28 2020