login
a(n) is the least k > 0 such that the binary representation of n appears as a substring in the binary representation of at least half of the numbers in the range 1..k.
1

%I #15 Dec 08 2019 09:53:12

%S 1,2,14,38,110,62,1006,2206,5072,21504,7114,3704,13868,4058,4067254,

%T 4384886,9535340,39157714,20466206,5565048,732167206,47755164,

%U 24722194,12837030,27081364,14017192,231845728,15111866,32273342,16292028,17478178355102

%N a(n) is the least k > 0 such that the binary representation of n appears as a substring in the binary representation of at least half of the numbers in the range 1..k.

%C The sequence is well defined as for any n > 0, the proportion of numbers in the range 1..k whose binary representation contains that of n tends to 1 as k tends to infinity.

%C For any n > 0, the binary representation of n appears as a substring in the binary representation of a(n).

%C Apparently, records occur at indices n such that the representation of n in base 2^w contains only the digit 2^k for some w and k such that 0 <= k < w (see A330220).

%H Rémy Sigrist, <a href="/A329735/b329735.txt">Table of n, a(n) for n = 1..512</a>

%H Rémy Sigrist, <a href="/A329735/a329735.gp.txt">PARI program for A329735</a>

%e For n = 3:

%e - the binary representation of 3 is "11",

%e - the binary representation of the first numbers, alongside the proportion p of those containing "11", is:

%e k bin(k) p

%e -- ------ ----

%e 1 1 0

%e 2 10 0

%e 3 11 1/3

%e 4 100 1/4

%e 5 101 1/5

%e 6 110 1/3

%e 7 111 3/7

%e 8 1000 3/8

%e 9 1001 1/3

%e 10 1010 3/10

%e 11 1011 4/11

%e 12 1100 5/12

%e 13 1101 6/13

%e 14 1110 1/2

%e - we first reach a proportion p >= 1/2 for k = 14,

%e - hence a(3) = 14.

%o (PARI) See Links section.

%Y Cf. A330220.

%K nonn,base

%O 1,2

%A _Rémy Sigrist_, Nov 20 2019