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, 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

Author

Peter Kagey, Apr 26 2022

Keywords

• nonn

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.

Examples

			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).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..100

Crossrefs

Cf. A003986, A036469, A096914.

Partial sums of A088314.

Programs

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 *)

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<Michael S. Branicky, May 02 2023

Formula

a(n) = Sum_{i=0..n} A088314(i). - Alois P. Heinz, May 01 2022

Extensions

a(21)-a(45) from Alois P. Heinz, Apr 27 2022