Find the number of sequences related to XOR

Question

Given a positive integer $n$, I want to find the number of sequences starting with $1$ and ending with $n$, such that every two adjacent elements $i,j$ satisfy $j\oplus i<j$ and $j>i$ ($\oplus$ is bitwise XOR).

I tried to solve this problem through brute force and got some results with the following code:

ans = [0] * 33
ans[1] = 1
def f(n):
    for i in range(1, n + 1):
        for j in range(1, i):
            if ans[j] and i ^ j < i:
                ans[i] += ans[j]
f(32)
for i, j in enumerate(ans):
    print(i, j)

The results from 0 to 32 are like this, and it seems to have some kind of regularity, but I can't explain it.

[0, 1, 0, 1, 0, 1, 2, 5, 0, 1, 2, 5, 16, 33, 66, 133, 0, 1, 2, 5, 16, 33, 66, 133, 512, 1025, 2050, 4101, 8208, 16417, 32834, 65669, 0]

Could you please tell if there is any way to solve it. Thanks!

Answer 1

In binary

     n            ans[n]
------   ---------------
     0                 0
     1                 1
    10                 0
    11                 1
   100                 0
   101                 1
   110                10
   111               101
  1000                 0
  1001                 1
  1010                10
  1011               101
  1100             10000
  1101            100001
  1110           1000010
  1111          10000101
 10000                 0
 10001                 1
 10010                10
 10011               101
 10100             10000
 10101            100001
 10110           1000010
 10111          10000101
 11000        1000000000
 11001       10000000001
 11010      100000000010
 11011     1000000000101
 11100    10000000010000
 11101   100000000100001
 11110  1000000001000010
 11111 10000000010000101   
100000                 0

Can you spot a pattern?