tag:blogger.com,1999:blog-3722233.post4813311592001744524..comments2022-08-18T12:58:18.038-05:00Comments on Computational Complexity: An open question about a sequence mod M. Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-89621751953457593732022-07-28T04:34:43.056-05:002022-07-28T04:34:43.056-05:00The sequence a(n) that you are considering has an ...The sequence a(n) that you are considering has an ordinary generating function (ogf) f(x) which satisfies the homogeneous linear Mahler equation <br />(1 - x)*f - (1 + x)*f(x^2) = 0<br />if you add the condition a(0) = 1/2. Then the ogf writes down<br />f(x) = 1/2 * 1/(1 - x) * product(1/(1 - x^(2^k)), k = 0..infinity).<br />As a consequence a(n) is (except for the factor 1/2) the summatory function of the sequence b(n) of binary partitions numbers.<br />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'.<br />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. <br />I hope these few keywords help you.<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-83261971431826199692022-07-21T10:45:25.379-05:002022-07-21T10:45:25.379-05:00Oh, I see that I read the problem statement incorr...Oh, 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..Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2656972190240421962022-07-21T10:38:57.514-05:002022-07-21T10:38:57.514-05:00A little more precisely, for m = 2 the even-valued...A 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21449232760144177642022-07-21T01:15:36.559-05:002022-07-21T01:15:36.559-05:00Not the previous poster, but I think "For whi...Not the previous poster, but I think "For which values of M" would have been the easiest way to avoid the ambiguity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60541053719614058442022-07-20T21:23:25.340-05:002022-07-20T21:23:25.340-05:00The problem says `For which M' This means I w...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. <br /><br />Is there a way I could have used a phrase other than `For which M' which would have made what I wanted clear?gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87169139139648067022022-07-20T19:44:43.619-05:002022-07-20T19:44:43.619-05:00Please update any progress. Seems like the questio...Please update any progress. Seems like the question got misunderstood?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-21489671412526481432022-07-20T04:42:32.079-05:002022-07-20T04:42:32.079-05:00m=2 seems trivial... For any a_{k}, it's eithe...m=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.<br />Did I misunderstand the question and the open problem is finding all such m? Or whether it holds for all m?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29527063837711087032022-07-19T20:56:22.039-05:002022-07-19T20:56:22.039-05:00I have emailed you the open problems column so we ...I have emailed you the open problems column so we can see if you proved something that I was unable to. I hope so!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78731399309309192992022-07-19T20:22:25.824-05:002022-07-19T20:22:25.824-05:00To answer the question as stated on twitter, m = 2...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16557968222828981892022-07-19T05:20:27.155-05:002022-07-19T05:20:27.155-05:00Forget the previous comment.
This is a link to t...Forget the previous comment. <br /><br />This is a link to the OEIS entries, at least it is not unknown :-)<br /><br />https://oeis.org/search?q=1%2C2%2C3%2C5%2C7%2C10%2C13%2C18%2C23%2C30%2C37%2C47%2C57&sort=&language=&go=Search<br /><br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76691906521446872282022-07-19T05:12:20.792-05:002022-07-19T05:12:20.792-05:00The sequence should start from a_0 ( otherwise a_{...The sequence should start from a_0 ( otherwise a_{floor(1/2)} is undefined)Anonymousnoreply@blogger.com