cp's OEIS Frontend

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

%I A360799 #16 Mar 31 2023 14:58:11
%S A360799 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,
%T A360799 48,49,51,52,54,55,57,60,61,63,64,66,67,70,72,73,75,76,78,79,82,88,90,
%U A360799 91,94,96,97,99,100,102,103,105,108,109,111,112,114,115,118,120,121
%N A360799 Numbers m with m mod 3 = q, q != 2, such that the number of ones in its base-2 representation is even if q=0 and odd if q=1.
%C A360799 For q=0, the terms in A180963 are excluded.
%C A360799 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 base-2 representation, 1 stands for an overstanding unit square, see example.
%C A360799 Statement:
%C A360799 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.
%C A360799 Proof:
%C A360799 Start, provisionally, with w upright dominos. The corresponding term is x = (11..1) = 2^w-1 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 base-2 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.
%C A360799 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.
%e A360799  5 X 4 wall is tiled bottom-up with 1 X 2 dominos:
%e A360799                                       _    ___ ___ _
%e A360799                  _ _          _ _ ___| |  |_ _|___| |
%e A360799         _       | | |_ ___   | | |_ _|_|  | | |_ _|_|
%e A360799     ___| |___   |_|_| |___|  |_|_| |___|  |_|_| |___|
%e A360799    |___|_|___|  |___|_|___|  |___|_|___|  |___|_|___|
%e A360799     0 0 1 0 0    1 1 0 0 0    0 0 0 0 1    0 0 0 0 0
%e A360799      4 = a(3)   24 = a(14)     1 = a(1)     0 = a(0)
%o A360799 (Maxima)
%o A360799 block(kmax: 100, a:[],
%o A360799  even_ones(x):= block(su:0,
%o A360799   while x>0 do(p: mod(x,2), x:(x-p)/2, su:su+p),
%o A360799    return(mod(su,2))),
%o A360799 for k from 0 thru kmax do(r:mod(k,3),
%o A360799  if r<2 and r=even_ones(k) then a:append(a,[k])),a);
%o A360799 (PARI) isok(m) = my(k=m%3); if (hammingweight(m) % 2, k==1, k==0); \\ _Michel Marcus_, Feb 27 2023
%Y A360799 Cf. A001835, A003775, A028469, A028471, A180963, A187616, A360800.
%K A360799 nonn
%O A360799 0,3
%A A360799 _Gerhard Kirchner_, Feb 24 2023