A307096 Positive integers m such that for any positive integer k the last k bits of the binary expansion of m is not a multiple of 3.

1, 5, 13, 17, 29, 37, 49, 61, 65, 77, 101, 113, 125, 133, 145, 157, 193, 205, 229, 241, 253, 257, 269, 293, 305, 317, 389, 401, 413, 449, 461, 485, 497, 509, 517, 529, 541, 577, 589, 613, 625, 637, 769, 781, 805, 817, 829, 901, 913, 925, 961, 973, 997, 1009

Offset: 1

Author

John Rickert, Mar 24 2019

Keywords

• easy
• base
• nonn

Comments

The number of terms less than 2^n is the n-th Fibonacci number F(n), A000045.

The number of terms between 2^(n-1) and 2^n in the sequence is the Fibonacci number F(n-2), A000045.

If 2^(n-1) <= x < 2^n, then x is in the sequence if and only if x is not divisible by 3 and x - 2^(n-1) is in the sequence. - Robert Israel, Apr 25 2019

Examples

			29 is 11101_2 and none of 11101_2, 1101_2, 101_2, 1_2 are divisible by 3.
		

Crossrefs

Cf. A060142, A219608, A000045.

Programs

Maple

f := n-> if(n != 0, add(2^(k-1)*`if`((n mod 2^k) mod 3 = 0, 1, 0), k = 1 .. ceil(log(n)/log(2))), 0);
ker := []; for n from 1 to 1024 do if f(n) = 0 then ker := [op(ker), n] end if end do; ker;
# Alternative:
A1:= {1}: A2:= {}:
for d from 1 to 12 do
  if d::odd then A1:= A1 union map(`+`,A2,2^d)
  else A2:= A2 union map(`+`,A1,2^d)
  fi
od:
sort(convert(A1 union A2,list)); # Robert Israel, Apr 25 2019

Mathematica

Select[Range[10^3], Function[s, NoneTrue[Array[FromDigits[Take[s, -#], 2] &, Length@ s], Mod[#, 3] == 0 &]]@ IntegerDigits[#, 2] &] (* Michael De Vlieger, Mar 24 2019 *)

PARI

isok(n) = {if (n % 3, my(b=binary(n)); for (k=1, #b-1, b[k] = 0; if ((fromdigits(b, 2) % 3) == 0, return (0));); return (1);); return (0);} \\ Michel Marcus, Apr 24 2019

Formula

(a(n)+1)/2 = A219608(n), the n-th odd term in A060142.