What is known about that sequence

 In my last post I wrote:

---------------------------

Consider the recurrence

a_1=1

for all n\ge 2, a_n = a_{n-1} + a_{n/2}.

For which M does this recurrence have infinitely many n such that a_n \equiv  0 mod M?

I have written an open problems column on this for SIGACT News which also says

what is known (or at least what I know is known).  It will appear in the next issue.

I will post that open problems column here on my next post.

Until then  I would like you to work on it, untainted by what I know. 

----------------------------------------

I will now say what is known and point to the open problems column, co-authored with Emily Kaplitz and Erik Metz. 

If  M=2 or M=3 or M=5 or M=7 then there are infinitely many n such that a_n \equiv 0 mod M

If M\equiv 0 mod 4 then there are no n such that a_n \equiv 0 mod M

Empirical evidence suggests that

If M \not\equiv 0 mod 4 then there are infinitely many n such that a_n\equiv 0 mod M

That is our conjecture. Any progress would be good- for example proving it for M=9. M=11 might be easier since 11 is prime. 

The article that I submitted is HERE