OFFSET
1,6
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).
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.
FORMULA
a(2^k+2) = k*(k-1)/2 + 1 for k >= 2.
EXAMPLE
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.
MATHEMATICA
a[n_] := Count[Range[n + 1, 2*n], _?(DigitCount[#, 2, 1] == 3 &)]; Array[a, 100] (* Amiram Eldar, Dec 28 2020 *)
PROG
(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
(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
CROSSREFS
KEYWORD
nonn,base,easy
AUTHOR
Bernard Schott, Dec 28 2020
EXTENSIONS
More terms from David A. Corneth, Dec 28 2020
STATUS
approved