[math-fun] How often does every bit matter?
Each of the following is a prime number P, such that if any single bit of P's binary representation is changed, then you no longer have a prime. (And this is the full list of such P<10000.) 127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443, 491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193, 1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777, 1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999, 3083, 3181, 3209, 3313, 3511, 3593, 3643, 3767, 3779, 3851, 3877, 3889, 3967, 4013, 4177, 4283, 4441, 4451, 4561, 4597, 4603, 4679, 4813, 4889, 4951, 5051, 5099, 5209, 5323, 5557, 5801, 5867, 6007, 6073, 6151, 6203, 6211, 6287, 6323, 6379, 6481, 6521, 6971, 6977, 6997, 7027, 7039, 7043, 7103, 7109, 7151, 7207, 7297, 7307, 7331, 7369, 7507, 7573, 7583, 7841, 7883, 8017, 8087, 8111, 8171, 8231, 8243, 8311, 8363, 8627, 8747, 8831, 8849, 8867, 8923, 9137, 9151, 9161, 9319, 9323, 9697, 9767 The Mersenne primes P=2^p-1 also have this "every bit matters" property when p = 7, 31, 127, 607, 1279, 4423 for the p<5000. I would presume that asymptotically, a constant fraction C of all primes are "every bit matters" primes. What is that constant? I would guess that C = exp( (-1/ln2) * (1-1/2)/(1-1/3) * (1-1/4)/(1-1/5) * (1-1/6)/(1-1/7) * ... ) = exp( (-1/ln2) * (1*3)/2^2 * (3*5)/4^2 * ... * (p-2)*p/(p-1)^2 * ... ) = exp( (-1/ln2) * 0.660162) = 0.38581 the product being over all odd primes p. However, my guess seems to be wrong in view of the actual counts 89486 / 664579 = 0.13465 from the primes below 10^7 794760 / 5761455 = 0.13794 from the primes below 10^8 I think I see my error now... getting this right should be tricky. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
Tao http://arxiv.org/abs/0802.3361 gets >> 1/log x of numbers up to x with that property. I don't know if this is sharp. See also Cohen & Selfridge http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0376583-0/S0025... Charles Greathouse Analyst/Programmer Case Western Reserve University On Fri, Mar 29, 2013 at 12:53 PM, Warren D Smith <warren.wds@gmail.com>wrote:
Each of the following is a prime number P, such that if any single bit of P's binary representation is changed, then you no longer have a prime. (And this is the full list of such P<10000.)
127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443, 491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193, 1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777, 1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999, 3083, 3181, 3209, 3313, 3511, 3593, 3643, 3767, 3779, 3851, 3877, 3889, 3967, 4013, 4177, 4283, 4441, 4451, 4561, 4597, 4603, 4679, 4813, 4889, 4951, 5051, 5099, 5209, 5323, 5557, 5801, 5867, 6007, 6073, 6151, 6203, 6211, 6287, 6323, 6379, 6481, 6521, 6971, 6977, 6997, 7027, 7039, 7043, 7103, 7109, 7151, 7207, 7297, 7307, 7331, 7369, 7507, 7573, 7583, 7841, 7883, 8017, 8087, 8111, 8171, 8231, 8243, 8311, 8363, 8627, 8747, 8831, 8849, 8867, 8923, 9137, 9151, 9161, 9319, 9323, 9697, 9767
The Mersenne primes P=2^p-1 also have this "every bit matters" property when p = 7, 31, 127, 607, 1279, 4423 for the p<5000.
I would presume that asymptotically, a constant fraction C of all primes are "every bit matters" primes. What is that constant? I would guess that C = exp( (-1/ln2) * (1-1/2)/(1-1/3) * (1-1/4)/(1-1/5) * (1-1/6)/(1-1/7) * ... ) = exp( (-1/ln2) * (1*3)/2^2 * (3*5)/4^2 * ... * (p-2)*p/(p-1)^2 * ... ) = exp( (-1/ln2) * 0.660162) = 0.38581 the product being over all odd primes p.
However, my guess seems to be wrong in view of the actual counts 89486 / 664579 = 0.13465 from the primes below 10^7 794760 / 5761455 = 0.13794 from the primes below 10^8
I think I see my error now... getting this right should be tricky.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Charles Greathouse points out paper by T.Tao...
--oh, great, scooped by Terry Tao. Terence Tao: A remark on primality testing and decimal expansions, J.Australian Math'l. Soc. 91,3 (2011) 405-413. http://arxiv.org/abs/0802.3361 However, upon reading this paper, I observe that Tao does not have even any guess about what the constant C is. Tao proves that the proportion of n-bit primes (n sufficiently large) in which "every bit matters" is bounded between two constants in (0,1). He also proves analogous statement in every fixed radix other than 2. Tao also remarks that it should be possible to show not only that every bit-altered version is composite, but actually is fairly highly composite, i.e. having at least (loglogN)^0.33 prime factors. He also thinks it should be possible to consider "edits" of the number where you erase or insert one digit, and all edited versions must be composite. (He does not actually solve these problems, he just claims using similar techniques one presumably could solve them.) Tao's result with radix 2 is actually a trivial consequence of the fact, pointed out by Zhi-Wei Sun: Proc. Amer. Math. Soc. 128 (2000) 997-1002 http://www.ams.org/journals/proc/2000-128-04/S0002-9939-99-05502-1/ that every integer in the arithmetic progression with initial term 47867742232066880047611079 and increment 46397560804008899814641902590 = 2*3*5*7*11*13*17*19*31*37*41*61*73*97*109*151*241*257*231 has the property that all 1-bit alterations of it, are composite. Now use Dirichlet's theorem for primes in arithmetic progressions, end of proof. This shows the lower bound C >= 1/46397560804008899814641902590 > 2.155*10^(-29) on the proportion of "every bit matters" primes. However, Tao does not know, nor even guess, what these constants are, and he does not prove that a limit exists, i.e. he does not show that the constants in his upper and lower bounds ultimately become the same. I believe that (a) limit does exist, and (b) we should be able to write down an expression for the limit constant, somewhat like my wrong-guess expression, but trickier. There will be no known way to prove this expression is correct, but it will be correct anyhow. Also, I see little or no hope to prove the limit exists (but it should).
Tao proves that the proportion of n-bit primes (n sufficiently large) in which "every bit matters" is bounded between two constants in (0,1).
--sorry, I should have said (0,1] not (0,1). The conjecture that the proportion of "every bit matters" primes is strictly below 100%, apparently is still open (albeit undoubtably true).
As I commented in A153352, Sun's result gives a (weak) lower bound on the density (for a slightly stronger version of the problem). Charles Greathouse Analyst/Programmer Case Western Reserve University On Fri, Mar 29, 2013 at 3:05 PM, Warren D Smith <warren.wds@gmail.com>wrote:
Tao proves that the proportion of n-bit primes (n sufficiently large) in which "every bit matters" is bounded between two constants in (0,1).
--sorry, I should have said (0,1] not (0,1).
The conjecture that the proportion of "every bit matters" primes is strictly below 100%, apparently is still open (albeit undoubtably true).
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Let N be a positive integer. As long as N > 1, we can always find the largest integer of the form K * p^r with p prime, r >= 1, 1 <= K <= p-1 that is <= N. Letting K*p^r be that largest such integer, now find the corresponding number for N - K*p^r, iteratively, until what is left is 0 or 1. If it's 0, we're done, and if it's 1, just add 1 at the end. In this way we can represent all positive integers as sums of such K*p^r with possibly a 1 tacked on at the end: N = K_1*p_1^r_1 + . . . + K_d*p_d^r_d (+ 1). For instance 46 = 4*11 + 2, 126 = 5^3 + 1, 144 = 11*13 + 1. There seem to be interesting statistics lurking here, such as how often the representation ends with a 1 at the end, or how many terms are required. Having checked up to only 150 (by hand), things I don't know yet include * What is the 2nd case ending with + 2 (other than 2 itself) ? (46 is the first.) * What is the first case ending with + 3 (other than 3) ? * What is the first case having a term K*2^r with r >= 1 (other than powers of 2 themselves) ? (This is not counting terms of the form K*p^r where p > 2 and K is a power of 2, such as 108 = 4*3^3.) * What is the first case with more than two terms altogether? --Dan
Oops, that's wrong. Using this representation, 108 = 107 + 1. An actual example of the type of cases not counted in the query below would be 28 = 4*7. --Dan -------------------------------------- On 2013-03-29, at 7:04 PM, Dan Asimov wrote:
* What is the first case having a term K*2^r with r >= 1 (other than powers of 2 themselves) ? (This is not counting terms of the form K*p^r where p > 2 and K is a power of 2, such as 108 = 4*3^3.)
(All numbers here are from code that's been tested only in the trivial sense that I've run it and not noticed that the answers are obviously wrong. Don't trust them.) On 30/03/2013 02:04, Dan Asimov wrote:
For instance 46 = 4*11 + 2, 126 = 5^3 + 1, 144 = 11*13 + 1.
46 = 2*23, surely.
Having checked up to only 150 (by hand), things I don't know yet include
* What is the 2nd case ending with + 2 (other than 2 itself) ? (46 is the first.)
No (see above), 176 appears to be the first, followed by 225, then 325, 351, 385, 400, 441, 456, 476, 495, 540, 561, 576, 595, 715, 736, 760, 833, 875, 897, 936. (That's it up to 1000.)
* What is the first case ending with + 3 (other than 3) ?
352, 442, 1276, 1520, 1666, 1702, 1887. (That's it up to 2000.)
* What is the first case having a term K*2^r with r >= 1 (other than powers of 2 themselves) ? (This is not counting terms of the form K*p^r where p > 2 and K is a power of 2, such as 108 = 4*3^3.)
Powers of 2 (of course); 513 = 512 + 1; many many that end with "+ 2"; and (up to 10000) the following ending with other powers of 2: 4961, 5831, 6786, 7140, 7505. Unless I've misunderstood your definitions, in this case you always have K=1 because 1 <= K < p.
* What is the first case with more than two terms altogether?
None below 11000000. First appearances of every "tail", as far as my little program has got: 1 : 1 [empty tail] 12 : 1.11^1 + 1 176 : 6.29^1 + 1.2^1 352 : 1.349^1 + 1.3^1 2109 : 5.421^1 + 1.2^2 5832 : 1.5827^1 + 1.5^1 28037 : 1.28031^1 + 2.3^1 290789 : 2.145391^1 + 1.7^1 290790 : 2.145391^1 + 1.2^3 1255508 : 7.179357^1 + 1.3^2 4325179 : 3.1441723^1 + 2.5^1 11135847 : 4.2783959^1 + 1.11^1 ... from which, super-crudely, it looks like we might expect to see "+12" somewhere around 40 million, at which point we'd get three terms. My code is shockingly inefficient and hasn't got nearly that far yet. The right way to implement this is probably to generate all the k.p^r values in order and look at the gaps between them. I've taken the more naive approach of just computing the "variable prime-power base" representation separately for each n. So, anyway, it looks a little as if the "remainder" after pulling out the first term from n grows rather slowly; maybe something like log(n). I bet that whatever the fact is is hard to prove, but is some good bound implied by any standard theorem or conjecture about the distribution of primes? -- g
Thanks, Gareth!
For instance 46 = 4*11 + 2, 126 = 5^3 + 1, 144 = 11*13 + 1.
46 = 2*23, surely.
Sigh (my 6th grade teacher promised to teach me algebra if I got 3 consecutive 100's on the weekly arithmetic tests. I never managed to do this all year long, and apparently in over 50 years I haven't changed). Nice to see those statistics. It's curious that there are no 3-term representations, at least up to Gareth's 11 million. Is there some simple reason for this? --Dan P.S. The definition here seemed natural at the time, but maybe it's too arbitrary to be of general interest. On 2013-03-29, at 8:49 PM, Gareth McCaughan wrote:
(All numbers here are from code that's been tested only in the trivial sense that I've run it and not noticed that the answers are obviously wrong. Don't trust them.)
On 30/03/2013 02:04, Dan Asimov wrote:
For instance 46 = 4*11 + 2, 126 = 5^3 + 1, 144 = 11*13 + 1.
46 = 2*23, surely.
Having checked up to only 150 (by hand), things I don't know yet include
* What is the 2nd case ending with + 2 (other than 2 itself) ? (46 is the first.)
No (see above), 176 appears to be the first, followed by 225, then 325, 351, 385, 400, 441, 456, 476, 495, 540, 561, 576, 595, 715, 736, 760, 833, 875, 897, 936. (That's it up to 1000.)
* What is the first case ending with + 3 (other than 3) ?
352, 442, 1276, 1520, 1666, 1702, 1887. (That's it up to 2000.)
* What is the first case having a term K*2^r with r >= 1 (other than powers of 2 themselves) ? (This is not counting terms of the form K*p^r where p > 2 and K is a power of 2, such as 108 = 4*3^3.)
Powers of 2 (of course); 513 = 512 + 1; many many that end with "+ 2"; and (up to 10000) the following ending with other powers of 2: 4961, 5831, 6786, 7140, 7505.
Unless I've misunderstood your definitions, in this case you always have K=1 because 1 <= K < p.
* What is the first case with more than two terms altogether?
None below 11000000.
First appearances of every "tail", as far as my little program has got:
1 : 1 [empty tail] 12 : 1.11^1 + 1 176 : 6.29^1 + 1.2^1 352 : 1.349^1 + 1.3^1 2109 : 5.421^1 + 1.2^2 5832 : 1.5827^1 + 1.5^1 28037 : 1.28031^1 + 2.3^1 290789 : 2.145391^1 + 1.7^1 290790 : 2.145391^1 + 1.2^3 1255508 : 7.179357^1 + 1.3^2 4325179 : 3.1441723^1 + 2.5^1 11135847 : 4.2783959^1 + 1.11^1
... from which, super-crudely, it looks like we might expect to see "+12" somewhere around 40 million, at which point we'd get three terms. My code is shockingly inefficient and hasn't got nearly that far yet.
The right way to implement this is probably to generate all the k.p^r values in order and look at the gaps between them. I've taken the more naive approach of just computing the "variable prime-power base" representation separately for each n.
So, anyway, it looks a little as if the "remainder" after pulling out the first term from n grows rather slowly; maybe something like log(n). I bet that whatever the fact is is hard to prove, but is some good bound implied by any standard theorem or conjecture about the distribution of primes?
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On 30/03/2013 04:54, Dan Asimov wrote:
It's curious that there are no 3-term representations, at least up to Gareth's 11 million. Is there some simple reason for this?
(The first 3-termer actually comes at 18567920; my program found it while I was asleep, and Charles Greathouse's email reports the same number without explicitly saying it's where you first need three terms.) I think it depends on what you mean by a simple reason. Numbers of the form k.p^r with 1 <= k < p are quite common, so the gaps between them are quite short, so for smallish N two terms generally suffice. You need three terms once the gap reaches a length that takes two terms, which is to say 12. How common *are* numbers of the form k.p^r with 1 <= k < p? Asymptotically, presumably only r=1 matters. For fixed k, the count is then pi(n/k) - pi(k). So: sum {k<sqrt(n)} pi(n/k) - pi(k) which, simple-mindedly, is approximately sum {k<sqrt(n)} (n/k)/log(n/k) - k/log(k) = {splitting out the two terms} sum {k<sqrt(n)} (n/k)/log(n/k) - sum {k<sqrt(n)} k/log(k) ~= {asymptotics for second term} (sum {k<sqrt(n)} (n/k)/log(n/k)) - n / log n = {rearrange first term a little} ((n / log n) sum {k<sqrt(n)} (1/k)/(1 - log(k)/log(n))) - n / log n ~= {that denominator is always between 1/2 and 1} (A (n / log n) sum {k<sqrt(n)} (1/k)) - n / log n ~= {asymptotics} ((n / log n) A/2 log n) - n / log n ~= {triv} A/2 n where I've probably done all sorts of illegitimate things, but the point is that it seems like at least a constant proportion of numbers have that form, which suggests that large gaps should be rare. Exactly how rare is probably a hard problem. -- g
Reminds me of the Pillai sequence http://oeis.org/A066352 which is the special case K = r = 1. The first cases I get for +_ are 1 1 2 176 3 352 4 2109 5 5832 6 28037 7 290789 8 290790 9 1255508 10 4325179 11 11135847 12 18567920 13 28794696 14 28794696 15 28794696
What is the first case with more than two terms altogether?
Pretty big, I'd wager. Charles Greathouse Analyst/Programmer Case Western Reserve University On Fri, Mar 29, 2013 at 10:04 PM, Dan Asimov <dasimov@earthlink.net> wrote:
Let N be a positive integer.
As long as N > 1, we can always find the largest integer of the form
K * p^r
with p prime, r >= 1, 1 <= K <= p-1
that is <= N.
Letting K*p^r be that largest such integer, now find the corresponding number for N - K*p^r, iteratively, until what is left is 0 or 1.
If it's 0, we're done, and if it's 1, just add 1 at the end.
In this way we can represent all positive integers as sums of such K*p^r with possibly a 1 tacked on at the end:
N = K_1*p_1^r_1 + . . . + K_d*p_d^r_d (+ 1).
For instance 46 = 4*11 + 2, 126 = 5^3 + 1, 144 = 11*13 + 1.
There seem to be interesting statistics lurking here, such as how often the representation ends with a 1 at the end, or how many terms are required.
Having checked up to only 150 (by hand), things I don't know yet include
* What is the 2nd case ending with + 2 (other than 2 itself) ? (46 is the first.)
* What is the first case ending with + 3 (other than 3) ?
* What is the first case having a term K*2^r with r >= 1 (other than powers of 2 themselves) ? (This is not counting terms of the form K*p^r where p > 2 and K is a power of 2, such as 108 = 4*3^3.)
* What is the first case with more than two terms altogether?
--Dan
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
This is A137985 in the OEIS, where you could have found the Tao reference Feel free to your comments there Neil On Fri, Mar 29, 2013 at 12:53 PM, Warren D Smith <warren.wds@gmail.com>wrote:
Each of the following is a prime number P, such that if any single bit of P's binary representation is changed, then you no longer have a prime. (And this is the full list of such P<10000.)
127, 173, 191, 223, 233, 239, 251, 257, 277, 337, 349, 373, 431, 443, 491, 509, 557, 653, 683, 701, 733, 761, 787, 853, 877, 1019, 1193, 1201, 1259, 1381, 1451, 1453, 1553, 1597, 1709, 1753, 1759, 1777, 1973, 2027, 2063, 2333, 2371, 2447, 2633, 2879, 2917, 2999, 3083, 3181, 3209, 3313, 3511, 3593, 3643, 3767, 3779, 3851, 3877, 3889, 3967, 4013, 4177, 4283, 4441, 4451, 4561, 4597, 4603, 4679, 4813, 4889, 4951, 5051, 5099, 5209, 5323, 5557, 5801, 5867, 6007, 6073, 6151, 6203, 6211, 6287, 6323, 6379, 6481, 6521, 6971, 6977, 6997, 7027, 7039, 7043, 7103, 7109, 7151, 7207, 7297, 7307, 7331, 7369, 7507, 7573, 7583, 7841, 7883, 8017, 8087, 8111, 8171, 8231, 8243, 8311, 8363, 8627, 8747, 8831, 8849, 8867, 8923, 9137, 9151, 9161, 9319, 9323, 9697, 9767
The Mersenne primes P=2^p-1 also have this "every bit matters" property when p = 7, 31, 127, 607, 1279, 4423 for the p<5000.
I would presume that asymptotically, a constant fraction C of all primes are "every bit matters" primes. What is that constant? I would guess that C = exp( (-1/ln2) * (1-1/2)/(1-1/3) * (1-1/4)/(1-1/5) * (1-1/6)/(1-1/7) * ... ) = exp( (-1/ln2) * (1*3)/2^2 * (3*5)/4^2 * ... * (p-2)*p/(p-1)^2 * ... ) = exp( (-1/ln2) * 0.660162) = 0.38581 the product being over all odd primes p.
However, my guess seems to be wrong in view of the actual counts 89486 / 664579 = 0.13465 from the primes below 10^7 794760 / 5761455 = 0.13794 from the primes below 10^8
I think I see my error now... getting this right should be tricky.
-- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Dear Friends, I have now retired from AT&T. New coordinates: Neil J. A. Sloane, President, OEIS Foundation 11 South Adelaide Avenue, Highland Park, NJ 08904, USA Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com
Keith F. Lynch kfl at KeithLynch.net "Fred W. Helenius" <fredh at ix.netcom.com> wrote: 271129 is such a number; it is prime and 271129 + 2^k is always divisible by (at least) one of 3, 5, 7, 13, 17 and 241.
Tao in his paper page 1 (he says this result is due to Sun, but it actually is not immediate from what Sun says, you must have to do some extra work) claims that every N with N = 47867742232066880047611079 mod (2*3*5*7*11*13*17*19*31*37*41*61*73*97*109*151*241*257*231) has the property that N+2^k and |N-2^k| are always composite for every k>=0, in other words for the prime such N, "every bit matters" including(!) leading 0s, so REALLY every bit matters (I originally had in mind not counting leading 0s but Tao permits us)... and something stronger also is true since you can change 1s to 0s and 0s to 1s, but also 1s to 2s and 0s to (-1)s, eh? Evidently this was inspired by Sierpinski, as Helenius points out... but Tao never mentions Sierpinski in his paper so it is a good thing Helenius told us this. (Tao actually proves his analogous results using radices>2 without using just covering congruences, he also uses sieving arguments.)
participants (5)
-
Charles Greathouse -
Dan Asimov -
Gareth McCaughan -
Neil Sloane -
Warren D Smith