A353150 - OEIS

%I #41 May 02 2023 07:14:42

%S 1,2,4,7,12,18,28,40,58,80,110,147,198,259,338,434,558,706,892,1114,

%T 1389,1715,2115,2588,3163,3836,4647,5593,6725,8042,9600,11413,13551,

%U 16014,18907,22230,26112,30573,35750,41667,48514,56332,65326,75577,87343,100677

%N 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 In the definition, OR refers to the bitwise OR operator.

%C When the bitwise OR operator is replaced with the bitwise XOR operator, this appears to be A096914.

%C 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 The number of configurations of the lights themselves (ignoring the position of the lamplighter) appears to be given by A036469.

%H Alois P. Heinz, <a href="/A353150/b353150.txt">Table of n, a(n) for n = 0..100</a>

%F a(n) = Sum_{i=0..n} A088314(i). - _Alois P. Heinz_, May 01 2022

%e For n = 3, the a(3) = 7 pairs are:

%e (1, 0) via (0,0) -> (1,0) -> (1,0) -> (1,0);

%e (1, 1) via (0,0) -> (1,0) -> (1,0) -> (1,1);

%e (3, 0) via (0,0) -> (1,0) -> (1,1) -> (3,0) or

%e        via (0,0) -> (0,1) -> (2,0) -> (3,0);

%e (1, 2) via (0,0) -> (1,0) -> (1,1) -> (1,2);

%e (2, 1) via (0,0) -> (0,1) -> (2,0) -> (2,1);

%e (4, 0) via (0,0) -> (0,1) -> (0,2) -> (4,0); and

%e (0, 3) via (0,0) -> (0,1) -> (0,2) -> (0,3).

%p b:= proc(n) option remember; `if`(n=0, {[0$2]}, map(l->

%p      [[Bits[Or](l[1], 2^l[2]), 0], l+[0, 1]][], b(n-1)))

%p     end:

%p a:= n-> nops(b(n)):

%p seq(a(n), n=0..46);  # _Alois P. Heinz_, Apr 27 2022

%t b[n_, i_] := b[n, i] = If[n == 0, {{}},

%t      If[i < 1, {}, Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,

%t      Append[#, i]]& /@ b[n-i*j, i-1], {j, 1, n/i}]}]];

%t A088314[n_] := Length[b[n, n]];

%t A088314 /@ Range[0, 45] // Accumulate (* _Jean-François Alcover_, May 02 2022, after _Alois P. Heinz_ in A088314 *)

%o (Python)

%o from itertools import islice

%o def agen(): # generator of terms

%o     R1 = {(0, 0)}

%o     while True:

%o         yield len(R1)

%o         R = R1

%o         R1 = set().union(*({(x|(1<<y), 0), (x, y+1)} for x, y in R))

%o print(list(islice(agen(), 46))) # _Michael S. Branicky_, May 02 2023

%Y Cf. A003986, A036469, A096914.

%Y Partial sums of A088314.

%K nonn

%O 0,2

%A _Peter Kagey_, Apr 26 2022

%E a(21)-a(45) from _Alois P. Heinz_, Apr 27 2022