cp's OEIS Frontend

A353150 a(n) is the number of distinct pairs that can be made in exactly n iterations of either of the two maps (x, y) -> (x OR (2^y), 0) or (x, y) -> (x, y+1), starting from (0,0).

%I A353150 #41 May 02 2023 07:14:42
%S A353150 1,2,4,7,12,18,28,40,58,80,110,147,198,259,338,434,558,706,892,1114,
%T A353150 1389,1715,2115,2588,3163,3836,4647,5593,6725,8042,9600,11413,13551,
%U A353150 16014,18907,22230,26112,30573,35750,41667,48514,56332,65326,75577,87343,100677
%N A353150 a(n) is the number of distinct pairs that can be made in exactly n iterations of either of the two maps (x, y) -> (x OR (2^y), 0) or (x, y) -> (x, y+1), starting from (0,0).
%C A353150 In the definition, OR refers to the bitwise OR operator.
%C A353150 When the bitwise OR operator is replaced with the bitwise XOR operator, this appears to be A096914.
%C A353150 a(n) is the number of states in the following process after exactly n moves. A lamplighter starts at the rightmost lamp in an infinite line of lamps. At each step, she can either (a) take a step to the left or (b) turn on the lamp at her current position and return to the rightmost lamp. (If the lamp is already on, (b) would just return her to the rightmost lamp.)
%C A353150 The number of configurations of the lights themselves (ignoring the position of the lamplighter) appears to be given by A036469.
%H A353150 Alois P. Heinz, <a href="/A353150/b353150.txt">Table of n, a(n) for n = 0..100</a>
%F A353150 a(n) = Sum_{i=0..n} A088314(i). - _Alois P. Heinz_, May 01 2022
%e A353150 For n = 3, the a(3) = 7 pairs are:
%e A353150 (1, 0) via (0,0) -> (1,0) -> (1,0) -> (1,0);
%e A353150 (1, 1) via (0,0) -> (1,0) -> (1,0) -> (1,1);
%e A353150 (3, 0) via (0,0) -> (1,0) -> (1,1) -> (3,0) or
%e A353150        via (0,0) -> (0,1) -> (2,0) -> (3,0);
%e A353150 (1, 2) via (0,0) -> (1,0) -> (1,1) -> (1,2);
%e A353150 (2, 1) via (0,0) -> (0,1) -> (2,0) -> (2,1);
%e A353150 (4, 0) via (0,0) -> (0,1) -> (0,2) -> (4,0); and
%e A353150 (0, 3) via (0,0) -> (0,1) -> (0,2) -> (0,3).
%p A353150 b:= proc(n) option remember; `if`(n=0, {[0$2]}, map(l->
%p A353150      [[Bits[Or](l[1], 2^l[2]), 0], l+[0, 1]][], b(n-1)))
%p A353150     end:
%p A353150 a:= n-> nops(b(n)):
%p A353150 seq(a(n), n=0..46);  # _Alois P. Heinz_, Apr 27 2022
%t A353150 b[n_, i_] := b[n, i] = If[n == 0, {{}},
%t A353150      If[i < 1, {}, Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,
%t A353150      Append[#, i]]& /@ b[n-i*j, i-1], {j, 1, n/i}]}]];
%t A353150 A088314[n_] := Length[b[n, n]];
%t A353150 A088314 /@ Range[0, 45] // Accumulate (* _Jean-François Alcover_, May 02 2022, after _Alois P. Heinz_ in A088314 *)
%o A353150 (Python)
%o A353150 from itertools import islice
%o A353150 def agen(): # generator of terms
%o A353150     R1 = {(0, 0)}
%o A353150     while True:
%o A353150         yield len(R1)
%o A353150         R = R1
%o A353150         R1 = set().union(*({(x|(1<<y), 0), (x, y+1)} for x, y in R))
%o A353150 print(list(islice(agen(), 46))) # _Michael S. Branicky_, May 02 2023
%Y A353150 Cf. A003986, A036469, A096914.
%Y A353150 Partial sums of A088314.
%K A353150 nonn
%O A353150 0,2
%A A353150 _Peter Kagey_, Apr 26 2022
%E A353150 a(21)-a(45) from _Alois P. Heinz_, Apr 27 2022