login
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).
1
1, 2, 4, 7, 12, 18, 28, 40, 58, 80, 110, 147, 198, 259, 338, 434, 558, 706, 892, 1114, 1389, 1715, 2115, 2588, 3163, 3836, 4647, 5593, 6725, 8042, 9600, 11413, 13551, 16014, 18907, 22230, 26112, 30573, 35750, 41667, 48514, 56332, 65326, 75577, 87343, 100677
OFFSET
0,2
COMMENTS
In the definition, OR refers to the bitwise OR operator.
When the bitwise OR operator is replaced with the bitwise XOR operator, this appears to be A096914.
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.)
The number of configurations of the lights themselves (ignoring the position of the lamplighter) appears to be given by A036469.
LINKS
FORMULA
a(n) = Sum_{i=0..n} A088314(i). - Alois P. Heinz, May 01 2022
EXAMPLE
For n = 3, the a(3) = 7 pairs are:
(1, 0) via (0,0) -> (1,0) -> (1,0) -> (1,0);
(1, 1) via (0,0) -> (1,0) -> (1,0) -> (1,1);
(3, 0) via (0,0) -> (1,0) -> (1,1) -> (3,0) or
via (0,0) -> (0,1) -> (2,0) -> (3,0);
(1, 2) via (0,0) -> (1,0) -> (1,1) -> (1,2);
(2, 1) via (0,0) -> (0,1) -> (2,0) -> (2,1);
(4, 0) via (0,0) -> (0,1) -> (0,2) -> (4,0); and
(0, 3) via (0,0) -> (0,1) -> (0,2) -> (0,3).
MAPLE
b:= proc(n) option remember; `if`(n=0, {[0$2]}, map(l->
[[Bits[Or](l[1], 2^l[2]), 0], l+[0, 1]][], b(n-1)))
end:
a:= n-> nops(b(n)):
seq(a(n), n=0..46); # Alois P. Heinz, Apr 27 2022
MATHEMATICA
b[n_, i_] := b[n, i] = If[n == 0, {{}},
If[i < 1, {}, Union@Flatten@{b[n, i - 1], Table[If[Head[#] == List,
Append[#, i]]& /@ b[n-i*j, i-1], {j, 1, n/i}]}]];
A088314[n_] := Length[b[n, n]];
A088314 /@ Range[0, 45] // Accumulate (* Jean-François Alcover, May 02 2022, after Alois P. Heinz in A088314 *)
PROG
(Python)
from itertools import islice
def agen(): # generator of terms
R1 = {(0, 0)}
while True:
yield len(R1)
R = R1
R1 = set().union(*({(x|(1<<y), 0), (x, y+1)} for x, y in R))
print(list(islice(agen(), 46))) # Michael S. Branicky, May 02 2023
CROSSREFS
Partial sums of A088314.
Sequence in context: A033500 A003318 A329398 * A035300 A035296 A230118
KEYWORD
nonn
AUTHOR
Peter Kagey, Apr 26 2022
EXTENSIONS
a(21)-a(45) from Alois P. Heinz, Apr 27 2022
STATUS
approved