cp's OEIS Frontend

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

%I A018826 #32 Apr 04 2024 10:06:47
%S A018826 0,1,2,4,8,16,27,32,41,54,64,82,108,128,145,164,165,256,283,290,328,
%T A018826 487,512,545,566,580,974,1024,1090,1132,1160,1773,1948,2048,2113,2180,
%U A018826 2320,2701,3546,3896,4096,4226,4261,4360,4757,5402,7092,7625,8079,8192
%N A018826 Numbers n such that n is a substring of its square when both are written in base 2.
%C A018826 Complement of A136492. - _Reinhard Zumkeller_, Jan 01 2008
%C A018826 A136510(a(n)) = 2 for n>0. - _Reinhard Zumkeller_, Jan 03 2008
%C A018826 From _Robert Israel_, Jul 11 2018: (Start)
%C A018826 Contains A000079.
%C A018826 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 A018826 Giovanni Resta, <a href="/A018826/b018826.txt">Table of n, a(n) for n = 1..700</a> (first 200 terms from Robert Israel)
%e A018826 27 in binary is 11011 and 27^2 = 729 in binary is 1011011001 which has substring 11011. - _Michael Somos_, Mar 16 2015
%p A018826 filter:= proc(n) local S,S2;
%p A018826     S:= convert(convert(n,binary),string);
%p A018826     S2:= convert(convert(n^2,binary),string);
%p A018826     StringTools:-Search(S,S2)<>0
%p A018826 end proc:
%p A018826 select(filter, [$0..10000]); # _Robert Israel_, Jul 11 2018
%t A018826 Select[Range[0, 8192], {} != SequencePosition @@ IntegerDigits[{#^2, #}, 2] &] (* _Giovanni Resta_, Aug 20 2018 *)
%t A018826 Select[Range[0,10000],SequenceCount[IntegerDigits[#^2,2],IntegerDigits[#,2]]>0&] (* _Harvey P. Dale_, May 03 2022 *)
%o A018826 (PARI) issub(b, bs, k) = {for (i=1, #b, if (b[i] != bs[i+k-1], return (0));); return (1);}
%o A018826 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 A018826 lista(nn) = for (n=0, nn, if (a076141(n) == 1, print1(n, ", "))); \\ _Michel Marcus_, Mar 15 2015
%o A018826 (Python)
%o A018826 def ok(n): return bin(n)[2:] in bin(n**2)[2:]
%o A018826 print([k for k in range(9999) if ok(k)]) # _Michael S. Branicky_, Apr 04 2024
%Y A018826 Cf. A000079, A076141, A136490, A136492, A136510.
%Y A018826 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 A018826 nonn,base
%O A018826 1,3
%A A018826 _David W. Wilson_