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.
ADDED LATER: I have now posted the sequel which includes a pointer to the open problems column. To save you time, I post it here as well.
The sequence should start from a_0 ( otherwise a_{floor(1/2)} is undefined)
ReplyDeleteForget the previous comment.
DeleteThis is a link to the OEIS entries, at least it is not unknown :-)
https://oeis.org/search?q=1%2C2%2C3%2C5%2C7%2C10%2C13%2C18%2C23%2C30%2C37%2C47%2C57&sort=&language=&go=Search
To answer the question as stated on twitter, m = 2. Starting with n=2, the next even value is at a_(n+4), and it continues like that indefinitely jumping by 4 each time. (I would tell you I am @orcmid and sign in as orcmid@gmail.com but there is something not working on the blog (or my browser) about that.
ReplyDeleteI have emailed you the open problems column so we can see if you proved something that I was unable to. I hope so!
DeleteA little more precisely, for m = 2 the even-valued a_n are exactly those for n = 2 x (2k+1), k = 0, 1, ... .I didn't receive the open problem column, but might not have recognized the email address it was from. I see from your later post that you want to know about all such m and whether it is bounded or maybe works for all prime m or something. I will look further. The m=2 case works easily because of the fact that two odds add to an even and there are 3 odd + even = odd cases in each cycle before the next even a_n. I will look at the SIGACT column.
DeleteOh, I see that I read the problem statement incorrectly. I was using floor(n/2), not a_(floor(n/2)). No wonder I got the m=2 case so easily. My Emily Litella moment..
Deletem=2 seems trivial... For any a_{k}, it's either odd, in which case one of a_{2k}, a_{2k+1} is even, or it's even. This should be sufficient to prove there's infinitely many even entries.
ReplyDeleteDid I misunderstand the question and the open problem is finding all such m? Or whether it holds for all m?
The problem says `For which M' This means I want to know the set A such that for all M in A BLAH holds, but it also means you need to (a) proof that for all M in A BLAH holds, and (b) proof that for all M in N-A BLAH does not hold.
DeleteIs there a way I could have used a phrase other than `For which M' which would have made what I wanted clear?
Not the previous poster, but I think "For which values of M" would have been the easiest way to avoid the ambiguity.
DeletePlease update any progress. Seems like the question got misunderstood?
ReplyDeleteThe sequence a(n) that you are considering has an ordinary generating function (ogf) f(x) which satisfies the homogeneous linear Mahler equation
ReplyDelete(1 - x)*f - (1 + x)*f(x^2) = 0
if you add the condition a(0) = 1/2. Then the ogf writes down
f(x) = 1/2 * 1/(1 - x) * product(1/(1 - x^(2^k)), k = 0..infinity).
As a consequence a(n) is (except for the factor 1/2) the summatory function of the sequence b(n) of binary partitions numbers.
You can find articles on the web about the congruence properties of the sequence b(n), which could inspire you. Search for `Congruence Properties of Binary Partition Functions'.
Note that if you reduce the sequence b(n) modulo M with M a power of 2, then you get a 2-automatic sequence. It follows that a(n) is also 2-automatic.
I hope these few keywords help you.