A018826 - OEIS

%I #32 Apr 04 2024 10:06:47

%S 0,1,2,4,8,16,27,32,41,54,64,82,108,128,145,164,165,256,283,290,328,

%T 487,512,545,566,580,974,1024,1090,1132,1160,1773,1948,2048,2113,2180,

%U 2320,2701,3546,3896,4096,4226,4261,4360,4757,5402,7092,7625,8079,8192

%N Numbers n such that n is a substring of its square when both are written in base 2.

%C Complement of A136492. - _Reinhard Zumkeller_, Jan 01 2008

%C A136510(a(n)) = 2 for n>0. - _Reinhard Zumkeller_, Jan 03 2008

%C From _Robert Israel_, Jul 11 2018: (Start)

%C Contains A000079.

%C If x satisfies x^2 == 8*x + 1 (mod 2^m) and 0 < x < 2^(m-3) then x is in the sequence. Note that x^2 == 8*x + 1 has 4 solutions mod 2^m for m >= 3. Terms obtained in this way include 27, 283, 1773, 9965, 55579, 206573, .... (End)

%H Giovanni Resta, <a href="/A018826/b018826.txt">Table of n, a(n) for n = 1..700</a> (first 200 terms from Robert Israel)

%e 27 in binary is 11011 and 27^2 = 729 in binary is 1011011001 which has substring 11011. - _Michael Somos_, Mar 16 2015

%p filter:= proc(n) local S,S2;

%p     S:= convert(convert(n,binary),string);

%p     S2:= convert(convert(n^2,binary),string);

%p     StringTools:-Search(S,S2)<>0

%p end proc:

%p select(filter, [$0..10000]); # _Robert Israel_, Jul 11 2018

%t Select[Range[0, 8192], {} != SequencePosition @@ IntegerDigits[{#^2, #}, 2] &] (* _Giovanni Resta_, Aug 20 2018 *)

%t Select[Range[0,10000],SequenceCount[IntegerDigits[#^2,2],IntegerDigits[#,2]]>0&] (* _Harvey P. Dale_, May 03 2022 *)

%o (PARI) issub(b, bs, k) = {for (i=1, #b, if (b[i] != bs[i+k-1], return (0));); return (1);}

%o a076141(n) = {if (n, b = binary(n), b = [0]); if (n, bs = binary(n^2), bs = [0]); sum(k=1, #bs - #b +1, issub(b, bs, k));}

%o lista(nn) = for (n=0, nn, if (a076141(n) == 1, print1(n, ", "))); \\ _Michel Marcus_, Mar 15 2015

%o (Python)

%o def ok(n): return bin(n)[2:] in bin(n**2)[2:]

%o print([k for k in range(9999) if ok(k)]) # _Michael S. Branicky_, Apr 04 2024

%Y Cf. A000079, A076141, A136490, A136492, A136510.

%Y Cf. A018827 (base 3), A018828 (base 4), A018829 (base 5), A018830 (base 6), A018831 (base 7), A018832 (base 8), A018833 (base 9), A018834 (base 10).

%K nonn,base

%O 1,3

%A _David W. Wilson_