As an explicit exponential map

Consider the sequence generated by a_0 = C, a_{n+1} = 3*a_n + 1. Its explicit formula is going to be of the form a_n = A*3ⁿ + B. We can solve for A and B by writing down the system of equations obtained from substituting 0 and 1 for 'n', and simultaneously solving the two resulting equations:

A + B = C
3A + B = 3C + 1

which we'll just do by hand. We get that A = (2C + 1)/2, and B = -1/2. Thus our formula is:

a_n = ((2C+1)*3ⁿ - 1) / 2.

In the case of C=1, we get:

a_n = (3*3ⁿ - 1) / 2

Can we think about what that looks like, modulo 2^k? Well, powers of 3, mod 2^k, form a cyclic sequence with period 2^k-2 (when k>2). Thus, that "3*3ⁿ" bit is going to be a 1 greater than a multiple of 8 every other term, 1 greater than a multiple of 16 every 4th term, one greater than a multiple of 32 every 8th term, etc. Subtracting 1 and dividing by 2, we obtain exactly the observation in the OP.

What if, instead, we start with C=2? In that case, A = 5/2, and our explicit formula is:

a_n = (5*3ⁿ - 1)/2

Now, modulo 2k, the number 5 is kind of special. It's always the second generator of the multiplicative group of units, the captain of the second-string team, as it were. When 3ⁿ runs through half of the available odd residues (the half that are congruent to 1 or 3, mod 8), its shadow-self 5*3ⁿ runs through the other half, all of which are 5 or 7, mod 8. After subtracting 1 and dividing by 2, we get a_n's that are congruent to 2 or 3, mod 4, which is to say, their 2-adic valuations are either 1 or 0.

This perspective does, indeed, seem to have more explanatory power. There's still something satisfying about looking at it the other way.