login
Carryless binary square of n; also Moser-de Bruijn sequence written in binary.
4

%I #39 Dec 07 2022 09:11:09

%S 0,1,100,101,10000,10001,10100,10101,1000000,1000001,1000100,1000101,

%T 1010000,1010001,1010100,1010101,100000000,100000001,100000100,

%U 100000101,100010000,100010001,100010100,100010101,101000000,101000001

%N Carryless binary square of n; also Moser-de Bruijn sequence written in binary.

%C Numbers that are sums of distinct powers of 100. - _David Wasserman_, Feb 26 2008

%H Michael De Vlieger, <a href="/A063010/b063010.txt">Table of n, a(n) for n = 0..8191</a>

%H David Applegate, Marc LeBrun and N. J. A. Sloane, <a href="http://neilsloane.com/doc/carry1.pdf">Carryless Arithmetic (I): The Mod 10 Version</a>

%H Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, <a href="https://arxiv.org/abs/2210.10968">Identities and periodic oscillations of divide-and-conquer recurrences splitting at half</a>, arXiv:2210.10968 [cs.DS], 2022, p. 45.

%F a(n) = A062033(n)/10, i.e., with final zero removed.

%F a(n) = Sum_{k>=0} A030308(n,k)*A098608(k). - _Philippe Deléham_, Oct 15 2011

%F G.f.: (1/(1 - x))*Sum_{k>=0} 100^k*x^(2^k)/(1 + x^(2^k)). - _Ilya Gutkovskiy_, Jun 04 2017

%e a(11)=1000101, since 11 in binary is 1011 and binary carryless sum of 1011000, 0, 10110 and 1011 is 1000101.

%t With[{k = 100}, Map[FromDigits[#, k] &, Tuples[{0, 1}, 5]]] (* _Michael De Vlieger_, Oct 29 2022 *)

%o (PARI) a(n) = fromdigits(binary(n),100); \\ _Ruud H.G. van Tol_, Dec 05 2022

%Y Cf. Moser-de Bruijn sequence A000695, carryless decimal squares A059729, pre-carry binary squares A063009.

%K base,easy,nonn

%O 0,3

%A _Henry Bottomley_, Jul 03 2001

%E More terms from _David Wasserman_, Feb 26 2008