login
Number of n-digit nonnegative integers m whose first n digits of their binary expansion are equal to m.
3

%I #38 Mar 30 2024 21:19:25

%S 2,1,1,0,1,1,0,1,1,0,1,2,0,1,2,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,2,0,1,1,

%T 0,1,1,0,1,2,0,1,2,1,1,2,1,1,2,1,1,1,1,1,1,1,1,1,1,0,2,1,0,1,1,0,1,1,

%U 0,1,2,0,1,2,1,1,2,1,1,1,1,1,1,1,1,1,1,1,1,1

%N Number of n-digit nonnegative integers m whose first n digits of their binary expansion are equal to m.

%C This sequence comes from a problem proposed on the French math site Diophante.

%C The corresponding numbers m are in A181929.

%C Question: does some k exist such that a(k) >= 3?

%C Yes, the first occurrence is a(770) = 3. See attached file. - _Scott R. Shannon_, Feb 25 2021

%H Michel Marcus, <a href="/A341281/b341281.txt">Table of n, a(n) for n = 1..499</a> (using A181929 b-file).

%H Diophante, <a href="http://www.diophante.fr/problemes-par-themes/arithmetique-et-algebre/a1-pot-pourri/37-a107-binaire-decimal">A107, Binaire = décimal</a> (in French).

%H Scott R. Shannon, <a href="/A341281/a341281.txt">The three numbers for a(770) = 3</a>.

%F a(n) > 0 iff length(A305213(n)) = n.

%e a(1) = 2 because 0 and 1 have same expansion in base 2 and in base 10.

%e a(3) = 1 because 110_10 = 1101110_2 and 110 is the only 3-digit integer with this property.

%e a(4) = 0 because there is no 4-digit number whose binary expansion's first 4 digits are the base-10 digits of m. Indeed, the 5-digit integer 10010_10 = 10011100011010_2 is the smallest integer whose binary and decimal expansions coincide through the first 4 digits (1001), but 10010 is not a 4-digit integer.

%e a(12) = 2 because 101111000101_10 = 1011110001010101011110110110000100101_2 and 110011001110_10 = 1100110011101001010101010100100010110_2; there are no other 12-digit integers with this property.

%o (PARI) lista(nn) = {my(list = List()); for (n=0, nn, if (n==0, listput(list, n), my(b = binary(n), db = fromdigits(b), bb = binary(db)); if (vector(#b, k, bb[k]) == b, listput(list, db)););); my(lens = apply(x->#Str(x), list)); vector(vecmax(Vec(lens)), k, #select(x->(x==k), lens));} \\ _Michel Marcus_, Feb 10 2021

%Y Cf. A181929, A305213.

%K nonn,base

%O 1,1

%A _Bernard Schott_, Feb 08 2021