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

0, 1, 2, 4, 8, 16, 27, 32, 41, 54, 64, 82, 108, 128, 145, 164, 165, 256, 283, 290, 328, 487, 512, 545, 566, 580, 974, 1024, 1090, 1132, 1160, 1773, 1948, 2048, 2113, 2180, 2320, 2701, 3546, 3896, 4096, 4226, 4261, 4360, 4757, 5402, 7092, 7625, 8079, 8192

Offset: 1

Author

David W. Wilson

Keywords

• nonn
• base

Comments

Complement of A136492. - Reinhard Zumkeller, Jan 01 2008

A136510(a(n)) = 2 for n>0. - Reinhard Zumkeller, Jan 03 2008

From Robert Israel, Jul 11 2018: (Start)

Contains A000079.

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)

Examples

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

Links

• Giovanni Resta, Table of n, a(n) for n = 1..700 (first 200 terms from Robert Israel)

Crossrefs

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

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).

Programs

Maple

filter:= proc(n) local S,S2;
    S:= convert(convert(n,binary),string);
    S2:= convert(convert(n^2,binary),string);
    StringTools:-Search(S,S2)<>0
end proc:
select(filter, [$0..10000]); # Robert Israel, Jul 11 2018

Mathematica

Select[Range[0, 8192], {} != SequencePosition @@ IntegerDigits[{#^2, #}, 2] &] (* Giovanni Resta, Aug 20 2018 *)
Select[Range[0,10000],SequenceCount[IntegerDigits[#^2,2],IntegerDigits[#,2]]>0&] (* Harvey P. Dale, May 03 2022 *)

PARI

issub(b, bs, k) = {for (i=1, #b, if (b[i] != bs[i+k-1], return (0));); return (1);}
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));}
lista(nn) = for (n=0, nn, if (a076141(n) == 1, print1(n, ", "))); \\ Michel Marcus, Mar 15 2015

Python

def ok(n): return bin(n)[2:] in bin(n**2)[2:]
print([k for k in range(9999) if ok(k)]) # Michael S. Branicky, Apr 04 2024