

A360799


Numbers m with m mod 3 = q, q != 2, such that the number of ones in its base2 representation is even if q=0 and odd if q=1.


1



0, 1, 3, 4, 6, 7, 9, 12, 13, 15, 16, 18, 19, 22, 24, 25, 27, 28, 30, 31, 33, 36, 37, 39, 45, 48, 49, 51, 52, 54, 55, 57, 60, 61, 63, 64, 66, 67, 70, 72, 73, 75, 76, 78, 79, 82, 88, 90, 91, 94, 96, 97, 99, 100, 102, 103, 105, 108, 109, 111, 112, 114, 115, 118, 120, 121
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

For q=0, the terms in A180963 are excluded.
The terms of the sequence occur, with some exceptions, while tiling a wall (odd width w) with 1 X 2 dominos. The current tiling status can be described by a number x with 0 <= x < 2^w. In the base2 representation, 1 stands for an overstanding unit square, see example.
Statement:
The tiling always starts with q=1 and an odd number of ones (type 1) and is followed by a term with q=0 and an even number of ones (type 2) and so on, alternately.
Proof:
Start, provisionally, with w upright dominos. The corresponding term is x = (11..1) = 2^w1 with x mod 3 = 1 (type 1). Another first profile can be generated by replacing a pair of adjacent upright dominos with one flat domino. In the base2 representation, this is the subtraction (11..11..1)  (00..11..0) = (11..00..1). The subtrahend is 3*2^j with 0 <= j < w. Therefore, the modified term also is type 1. This way, any first profile can be found and it is type 1.
In the next provisional step, an upright domino is placed on each not overstanding unit square. If p1 is the first profile, then the second is p2 = 2^w  1  p1 with p2 mod 3 = 0. Moreover, the transition from p1 to p2 exchanges the ones and zeros such that p2 is type 2. Again, replacing adjacent upright dominos by one flat domino does not change the type of the profile. The next profile is type 1 and so on. QED. Condition to be satisfied by a tiling profile: The continued removal of 00 and 11 (reduction) leads to (0) or (1). Example: a(10)=18=(10010) > (110) > (0). The first exceptions are a(314) = 682 = (01010101010), a(611) = 1365 = (10101010101) and a(988) = 2218 = (0100010101010). Note that the reduction of 2218 is 682.


LINKS



EXAMPLE

5 X 4 wall is tiled bottomup with 1 X 2 dominos:
_ ___ ___ _
_ _ _ _ ___  _ ____ 
_   _ ___   _ __   _ __
___ ___ __ ___ __ ___ __ ___
_______ _______ _______ _______
0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0
4 = a(3) 24 = a(14) 1 = a(1) 0 = a(0)


PROG

(Maxima)
block(kmax: 100, a:[],
even_ones(x):= block(su:0,
while x>0 do(p: mod(x, 2), x:(xp)/2, su:su+p),
return(mod(su, 2))),
for k from 0 thru kmax do(r:mod(k, 3),
if r<2 and r=even_ones(k) then a:append(a, [k])), a);
(PARI) isok(m) = my(k=m%3); if (hammingweight(m) % 2, k==1, k==0); \\ Michel Marcus, Feb 27 2023


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



