User dakota - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T09:09:49Z http://mathoverflow.net/feeds/user/5597 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/22629/are-there-primes-of-every-hamming-weight Are There Primes of Every Hamming Weight? dakota 2010-04-26T18:29:45Z 2010-04-27T20:12:28Z <p>That is, for every integer $n \in \mathbb{Z}_{>0}$ does there exist a prime which is the sum of $n$ distinct powers of $2$?</p> <p>In this case, the <a href="http://en.wikipedia.org/wiki/Hamming_weight" rel="nofollow">Hamming weight</a> of a number is the number of $1$s in its binary expansion.</p> <p>Many problems of this sort have been considered, but perhaps not in such language. For instance, the question "Are there infinitely many <a href="http://en.wikipedia.org/wiki/Fermat_number" rel="nofollow">Fermat primes</a>?" corresponds to asking, "Are there infinitely many distinct primes with Hamming weight exactly $2$?" Also related is the question of whether there are infinitely many <a href="http://en.wikipedia.org/wiki/Mersenne_prime" rel="nofollow">Mersenne primes</a>.</p> <p>These examples suggest a class of such problems, "Do there exist infinitely many primes which are the sum of exactly $n$ distinct powers of two?"</p> <p>Since this question is open even for the $n=2$ case, I pose a much weaker question here.</p> <p>What is known is that for every $n \leq 1024$ there is such a prime.</p> <p>The smallest such prime is listed in the Online Encyclopedia of Integer Sequences <a href="http://www.research.att.com/~njas/sequences/A061712" rel="nofollow">A061712</a>.</p> <p>The number of zeros in the smallest such primes are listed in <a href="http://www.research.att.com/~njas/sequences/A110700" rel="nofollow">A110700</a>. The number of zeros in a number with a given Hamming weight is a reasonable measure of how large that number is. The conjecture at OEIS is quite a bit stronger than the question I pose.</p> <p>Is there a theorem ensuring such primes for every $n \in \mathbb{Z}_{>0}$?</p> http://mathoverflow.net/questions/11503/does-war-have-infinite-expected-length/31185#31185 Comment by dakota dakota 2010-09-05T06:33:02Z 2010-09-05T06:33:02Z On the other hand the randomness assumption is a statistical one, therefore the proof may be informative in cases of, sufficiently defined, pseudorandomness. http://mathoverflow.net/questions/24818/beginning-a-sentence-with-a-mathematical-symbol Comment by dakota dakota 2010-05-15T22:43:11Z 2010-05-15T22:43:11Z Harry, the lecture you mention seems interesting. Do you have a link or reference where one could find the video or a transcript? http://mathoverflow.net/questions/22927/why-worry-about-the-axiom-of-choice/22931#22931 Comment by dakota dakota 2010-04-29T04:42:57Z 2010-04-29T04:42:57Z The effective/nonconstructive trade-off is also of use when going the other direction. That is, many messy epsilon management tasks in analysis can be avoided by moving the discussion to structures involving nonprincipal ultrafilters. Or so says Tao in his exceptional blog post on the subject: <a href="http://terrytao.wordpress.com/2007/06/25/ultrafilters-nonstandard-analysis-and-epsilon-management/" rel="nofollow">terrytao.wordpress.com/2007/06/25/&hellip;</a> http://mathoverflow.net/questions/22629/are-there-primes-of-every-hamming-weight/22738#22738 Comment by dakota dakota 2010-04-27T18:04:03Z 2010-04-27T18:04:03Z This is an excellent summary of the solution of this problem. I accept this answer. http://mathoverflow.net/questions/22629/are-there-primes-of-every-hamming-weight Comment by dakota dakota 2010-04-27T15:18:51Z 2010-04-27T15:18:51Z fedja, let me see if I understand this correctly. The paper (<a href="http://www.dmg.tuwien.ac.at/drmota/DMRcomp2.pdf" rel="nofollow">dmg.tuwien.ac.at/drmota/DMRcomp2.pdf</a>) gives (5) for the number of primes, p, less than a given x whose Hamming weight is near half the length of p. The expression is (something positive)*(something unbounded)*(something greater than 1) and is therefore &amp;geq;1 for large x. I haven't looked at it long enough, but I don't immediately see why it is the case that we can specify a length here and find a prime of that length. It looks like you can do this in (4), but how do you show for any k we have an x so (4) is &amp;geq;1? http://mathoverflow.net/questions/22629/are-there-primes-of-every-hamming-weight Comment by dakota dakota 2010-04-26T19:28:56Z 2010-04-26T19:28:56Z @Joel Quite so. Edited to reflect this.