Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #13 Feb 27 2020 23:16:34
%S 1,0,1,-1,1,0,1,-2,1,1,1,-1,1,0,1,-3,1,4,1,0,1,0,1,-2,1,1,1,-1,1,0,1,
%T -4,1,5,1,7,1,0,1,-1,1,0,1,0,1,0,1,-3,1,2,1,0,1,0,1,-2,1,1,1,-1,1,0,1,
%U -5,1,5,1,-4,1,0,1,3,1,-3,1,1,1,0,1,-2,1,-2
%N Start with an empty stack S; for n = 1, 2, 3, ..., interpret the binary representation of n from left to right as follows: in case of bit 1, push the number 1 on top of S, in case of bit 0, replace the two numbers on top of S, say u on top of v, with u-v; a(n) gives the number on top of S after processing n.
%C This sequence is a variant of A308551.
%C After processing n, S has A268289(n) elements.
%C Every integer appears infinitely many times in the sequence:
%C - the effect of the binary string b(0) = "110" is to leave 0 on top of S,
%C - the effect of the binary string b(1) = "1" is to leave 1 on top of S,
%C - the effect of the binary string b(-1) = "11100" is to leave -1 on top of S,
%C - let "|" denote the binary concatenation,
%C - for any k > 0:
%C - the effect of b(k+1) = b(-1)|b(k)|"0" is to leave k+1 on top of S,
%C - the effect of b(-k-1) = b(1)|b(-k)|"0" is to leave -k-1 on top of S,
%C - for any k, for any n > 0, if the binary representation of n ends with b(k), then a(n) = k, QED,
%C - see A330264 for the values in order of appearance.
%H Rémy Sigrist, <a href="/A330261/b330261.txt">Table of n, a(n) for n = 1..8192</a>
%H Rémy Sigrist, <a href="/A330261/a330261.png">Scatterplot of the first 2^20 terms</a>
%H Rémy Sigrist, <a href="/A330261/a330261.gp.txt">PARI program for A330261</a>
%F a(2*k-1) = 1 for any k > 0.
%e The first terms, alongside the binary representation of n and the evolution of stack S, are:
%e n a(n) bin(n) S
%e -- ---- ------ ------------------------------------------------------------
%e 1 1 1 () -> (1)
%e 2 0 10 (1) -> (1,1) -> (0)
%e 3 1 11 (0) -> (0,1) -> (0,1,1)
%e 4 -1 100 (0,1,1) -> (0,1,1,1) -> (0,1,0) -> (0,-1)
%e 5 1 101 (0,-1) -> (0,-1,1) -> (0,2) -> (0,2,1)
%e 6 0 110 (0,2,1) -> (0,2,1,1) -> (0,2,1,1,1) -> (0,2,1,0)
%e 7 1 111 (0,2,1,0) -> (0,2,1,0,1) -> (0,2,1,0,1,1) -> (0,2,1,0,1,1,1)
%o (PARI) See Links section.
%Y Cf. A268289, A308551, A330261, A330264.
%K sign,base
%O 1,8
%A _Rémy Sigrist_, Dec 07 2019