[HN Gopher] Does having prime neighbors make you more composite?
___________________________________________________________________
Does having prime neighbors make you more composite?
Author : another
Score : 96 points
Date : 2021-11-05 14:49 UTC (8 hours ago)
(HTM) web link (bit-player.org)
(TXT) w3m dump (bit-player.org)
| AnotherGoodName wrote:
| Oh the site is going slow but it did load.
|
| >Another cross reference took me off to sequence A002822, labeled
| "Numbers m such that 6m-1, 6m+1 are twin primes"
|
| Don't focus on 6m+/-1 alone and you'll get it. Let me explain
|
| All prime numbers above 2 are in the form of 2m + 1. ie. They are
| odd. So we have a formula that rules out half of numbers from
| being possible prime.
|
| Now we can do a similar thing and create a formula to rule out
| factors of 2 and 3. Factors of 2 and 3 repeat every 6 numbers
| (the multiple of 2 and 3). eg. 6m + 0, 6m + 2 or 6m + 4 is
| divisible by 2. 6m + 0 or 6m + 3 is divisible by 3.
|
| So all prime numbers above 3 are in the form of 6m + 1 or 6m + 5.
| We can write the 6m + 5 as 6m - 1 if we want. Only 2 out of 6
| numbers can be prime above 3 and the numbers either side of these
| will have either a factor of 2 or a factor of 6. (Btw never
| simplify the 'only 2 out of 6 numbers can be prime' as there are
| windows (twin primes for example) where there's more than 1 our
| of 3 numbers that are prime. It's only true that there's never
| more than 2 out of 6 sequential numbers prime above 6. If you
| come up with a prime number theory that sets a maximum of the
| frequency of primes you need to consider the window size rather
| than a straight fraction or you'll end up with errors).
|
| Now we can do the same as above for 5. 30 is where factors of 2,3
| and 5 align. All prime numbers above 30 are in the form of 30m +
| 1, 7, 11, 13, 17, 19, 23, 29. The rest are factors or 2,3 or 5.
| Only 8 out of 30 numbers above 5 can possibly be prime. All those
| primes are surrounded by a factor of 6 and 2 (since 6m +1/-1 is a
| subset of this) or in the +1/+29 case surrounded by a factor of 2
| and a factor of 30. For the twin prime case 1/3 of prime numbers
| are next to multiples of 2,3,5 and 2/3 are next to multiples of
| 2,3.
|
| You could do the same with 2x3x5x7 = 210. And again come up with
| a formula for the maximum frequency of primes (48 out of 210
| numbers above 7 can possible by prime) and also a formula for
| where primes can occur. In this case you'd see for the twin prime
| case 1/21 are next to 2x3x5x7, 6/21 next to 2x3x5, 14/21 next to
| 2x3.
|
| And we can keep doing this again and again. Each time we'll see
| the frequency for primes decrease and we'll see a new possibility
| for an even more composite number next to a prime opening up.
|
| Now we can see clearly that primes are always next to at least
| one composite number. As the numbers get larger and larger
| there's there's more possibility for the number next to a prime
| being more composite.
| [deleted]
| [deleted]
| ouid wrote:
| odds are, if you have prime neighbors, you are even.
| edw519 wrote:
| A long time ago, I gave up the pursuit of Elementary Number
| Theory for a career in programming.
|
| Thanks OP for reminding me there's more than one way for a nerd
| to happy dance. Great post!
| sweezyjeezy wrote:
| Here's a relevant stackexchange post
| https://math.stackexchange.com/questions/3490592/what-is-not...
|
| TLDR - given some very reasonable (and wildly unproven)
| heuristics about primes, a large composite number between twin
| prime is expected to have approximately 2.180950 times as many
| divisors as usual.
| rjmunro wrote:
| I think of it like this. If a number n has a factor f, f cannot
| be a factor of n+1 or n-1 (unless f is 1, but we can ignore that
| for primeness). The next numbers to have f as a factor are n+f or
| n-f.
|
| If a number n has loads of factors, all of those factors are
| excluded from n+1 and n-1, so there are not many numbers left to
| be factors of them and they are likely to be twin primes.
| sweezyjeezy wrote:
| This article about the converse though - if you have twin
| primes is the central value more likely to be highly composite?
| Your statement can be true and this second statement not be
| true.
| feoren wrote:
| Assume (1) A -> B, (2) A is sometimes true, and (3) B is
| sometimes false. Then isn't it provably true that P(A | B) >
| P(B)? In other words, if highly composite numbers essentially
| "cause" twin primes, then given a twin prime, they _must_ be
| more likely to contain a highly composite number between
| them.
|
| _Major edit:_
|
| Clearly, P(twin prime | highly composite) > P(twin prime) --
| this is GP's statement. You're (and the article's) question
| is: ok, what about P(highly composite | twin prime)? Well,
| Bayes rule says:
|
| P(highly composite | twin prime) * P(twin prime) = P(twin
| prime | highly composite) * P(highly composite).
|
| We're comparing P(highly composite | twin prime) vs. P(highly
| composite). But we know P(twin prime | highly composite) >
| P(twin prime) based on GP's reasoning. So
|
| P(highly composite | twin prime) * P(twin prime) = P(twin
| prime) * C * P(highly composite)
|
| for some C > 1. Then
|
| P(highly composite | twin prime) = C * P(highly composite)
|
| for some C > 1, and we know
|
| P(highly composite | twin prime) > P(highly composite)
|
| Doesn't this more or less prove the question posed in the
| article?
| sweezyjeezy wrote:
| Yes you're right, my bad - it doesn't answer the question
| in the article though. What's the expected number of
| divisors? That doesn't follow from this kind of analysis,
| because the ones that aren't highly composite could be
| 'very' uncomposite for some reason.
| thaumasiotes wrote:
| > Assume (1) A -> B, (2) A is sometimes true, and (3) B is
| sometimes false. Then isn't it provably true that P(A | B)
| > P(B)?
|
| No, this is not true. Consider a population of 200 people,
| with 20 in group AB, 0 in group A, 80 in group B, and 100
| in group Nil.
|
| We see that A -> B, since group A has 0 members.
|
| We see that A is sometimes true, since group AB has 20
| members.
|
| We see that B is sometimes false, since group Nil has 100
| members.
|
| P(A | B) = 20 / (20 + 80) = 0.2
|
| P(B) = (20 + 80) / (20 + 80 + 0 + 100) = 0.5
| lkrubner wrote:
| "f cannot be a factor of n+1 or n-1"
|
| You are mostly just restating Euclid's proof that there are an
| infinite number of primes.
| thaumasiotes wrote:
| This is an observation on which the proof depends, but, as is
| logically required, it is not the proof.
| phkahler wrote:
| I would like to point out that if we loosen some definitions a
| bit to include negative numbers, we could claim 1 and -1 as some
| form of "primes" and 0 is an integer multiple of an infinite
| number of primes (all of them).
|
| There is something fundamental about zero that I've been trying
| to figure out how to state clearly, but haven't been able to put
| in words just yet. It is closely related to the above.
| Twisol wrote:
| Divisibility can be cast in terms of subsets of the prime
| factor multisets. That is, for every number, we can translate
| it to its multiset of prime factors, e.g. 36 would become
| {2->2, 3->2}; then divisibility becomes the subset relation.
|
| In this world, 1 is the empty set, primes are the singleton
| sets, and composites are anything with at least two elements.
| 0, being divisible by everything, is a superset of everything;
| it probably makes the most sense to treat it as {p->aleph_0}
| for all p, though it's rather undetermined -- you could pick
| another cardinal if you wanted.
|
| The inclusion of negative numbers would basically freely adjoin
| a copy of this lattice with itself. You'd get two "empty-ish"
| things that are divisible by each other, two ranks of
| "singletons" that are divisible across the signs, and so on.
| Modding out by these cycles gets you the original lattice.
| There may be some value to keeping the negative numbers around
| -- certainly in category theory we like to keep equivalences
| explicit rather than modding out by them -- but "morally" you
| don't get any new relations by adding the negative numbers.
| CBLT wrote:
| 1 and -1 are units, which behave differently that primes.
| Gaussian Primes[0] make this more obvious, if you like reading
| math on wikipedia (I don't). In your positive & negative number
| multiplicative space (we get to ignore addition/subtraction
| when considering primality), negatives are just a reflection of
| the positives. Multiplying by -a is exactly the same as
| multiplying by positive a and multiplying by -1, and the -1
| multiplication only reflects onto an otherwise identically-
| shaped number line. You can reflect any number of times, or do
| the identity transformation (multiply by 1) any number of
| times, and it's not changing the absolute value of the number
| you get. The number's magnitude is unchanging here, and the
| number's magnitude is also the only interesting part of the
| number with respect to being prime. So mathematicians just call
| 1 and -1 units, and ignore them for primes.
|
| Many people think of Complex Numbers as vectors, and I think of
| negative numbers as vectors too. They have both magnitude and
| orientation, even if the orientation is only 1-dimensional.
| When you multiply complex numbers, the resulting "vector" has
| magnitude equal to the product of the magnitudes, and angle
| (from the positive x-axis) equal to the sum of the angles. So
| you can actually calculate these products without actually
| multiplying the numbers themselves, but instead only
| considering magnitude and angle (this only really matters with
| complex numbers). But the definition of a vector, that is has
| magnitude and direction, doesn't apply to 0. It doesn't have
| any direction, so it's technically not a vector. Adding angles
| doesn't make sense to something that just doesn't have angles.
| Zero is actually a mess when considering multiplication, and is
| generally excluded from the set of numbers you get to play with
| under multiplication. Another number you don't get to use for
| the same reason is infinity. A professor once told me an
| interesting insight, that zero is messed up in the same way
| that complex infinity is messed up. Neither has orientation,
| both have magnitudes that consume the other number when
| multiplying. And if you think about it, you could
| `s/0/infinity/g` in integer multiplication tables and they'd
| still work exactly the same.
|
| [0]
| https://en.wikipedia.org/wiki/Gaussian_integer#Gaussian_prim...
| roberto wrote:
| This is how I understand it:
|
| For every 3 consecutive numbers, one of them is a multiple of 3.
| If a number has 2 prime neighbors there's 100% chance it's
| divisible by 3. Without prime neighbors, only 33%.
|
| For 3 consecutive numbers there's a 75% chance one of them is a
| multiple of 4. The number with 2 prime neighbors has then a 75%
| chance of being divisible by 4. A number without prime neighbors
| has only 25%.
|
| For 5, it's 60% vs 20%.
|
| So on average we expect the numbers with prime neighbors to be
| more composite.
| curtisf wrote:
| Here's one way to bolster this mathematically just a bit.
|
| If you have a composite number C, you can use C to guarantee
| factors in larger numbers. If k is a factor of C, Cn + k also has
| a factor of k.
|
| So, for a "highly-composite" C, you rule out many prime numbers.
| An easy way to generate these "highly composite" numbers is to
| multiple the first few primes. For example,
|
| C = 2 * 3 = 6.
|
| * 6n + 0 has factors of 2, 3, 6
|
| * 6n + 1 may be prime (e.g. 7)
|
| * 6n + 2 has factors of 2
|
| * 6n + 3 has factors of 3
|
| * 6n + 4 has factors of 2
|
| * 6n + 5 may be prime (e.g., 17)
|
| I'll call the possibly-prime numbers C-primes. So 6n+1 and 6n+5
| are 6-primes. Similarly, we have 6n+0 is a 6-tween, and 6n+2 and
| 6n+4 are 6-nexts (next to exactly one 6-prime), and 6n+3 is a
| 6-non (not adjacent to any 6-primes).
|
| So, the 6-tweens have at least 2 factors, the 6-nons have at
| least 1 factor, and 6-nexts have at least 1 factor.
|
| The number of proper divisors that a number can have is actually
| bounded fairly tightly [1]. For example, number numbers below 24
| have more than 4 divisors; that means the 6-tween behavior
| predicts _three quarters_ of the divisors a number can have until
| 24.
|
| [1]: https://terrytao.wordpress.com/2008/09/23/the-divisor-bound/
|
| You can use a larger C to get information for longer. For
| example, C = 2 * 3 * 5 = 30 gives
|
| * 30n + 0 has divisors 2, 3, 5, 6, 10, 15, 30 -- tween
|
| * 30n + 1 may be prime
|
| * 30n + 2 has divisors 2 -- next
|
| * 30n + 3 has divisors 3
|
| * 30n + 4 has divisors 2
|
| * 30n + 5 has divisors 5
|
| * 30n + 6 has divisors 2, 3, 6 -- next
|
| * 30n + 7 may be prime
|
| * 30n + 8 has divisors 2 -- next
|
| * 30n + 9 has divisors 3
|
| * 30n + 10 has divisors 2, 5, 10 -- next
|
| * 30n + 11 may be prime
|
| * 30n + 12 has divisors 2, 3, 6 -- tween
|
| * 30n + 13 may be prime
|
| * 30n + 14 has divisors 2 -- next
|
| * 30n + 15 has divisors 3, 5, 15
|
| * 30n + 16 has divisors 2 -- next
|
| * 30n + 17 may be prime
|
| * 30n + 18 has divisors 2, 3, 6 -- tween
|
| * 30n + 19 may be prime
|
| * 30n + 20 has divisors 2, 5, 10 -- next
|
| * 30n + 21 has divisors 3
|
| * 30n + 22 has divisors 2 -- next
|
| * 30n + 23 may be prime
|
| * 30n + 24 has divisors 2, 3, 6 -- next
|
| * 30n + 25 has divisors 5
|
| * 30n + 26 has divisors 2
|
| * 30n + 27 has divisors 3
|
| * 30n + 28 has divisors 2 -- next
|
| * 30n + 29 may be prime
|
| So 30-tweens have (7, 3, 3) divisors; 30-nexts have (1, 3, 3, 1,
| 1, 3, 3) divisors; 30-nons have (1, 1, 1, 1, 3, 1, 1, 1, 1)
| divisors.
|
| The first number to have more than 10 divisors is 120 (with 14),
| so this predicts 7 of the possible 13 divisors for numbers 30 to
| 120, all in tween numbers.
|
| This makes the problem somewhat more concrete: why do the numbers
| that have many common factors with C cluster near the numbers
| with no common factors of C? But since we can at least observe it
| for different concrete C, this still does predict something about
| "all" the primes (though the effect of a particular C fades as
| the number of possible divisors eventually increases >> num.
| divisors of C; I posit that you can always generate a larger C to
| extend the pattern, but I don't know number theory to show it)
| vgeek wrote:
| So should having prime neighbors be a factor when looking at
| multiples of properties?
| Jap2-0 wrote:
| Just looking through the comments: a lot of people seem to be
| (knowingly or not) describing the Sieve of Eratosthenes.[0]
|
| [0] https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
| wizzwizz4 wrote:
| They might be describing something equivalent to it. That
| doesn't mean they're describing it. Funny thing about
| mathematics: every single way of describing or talking about
| _any mathematical phenomenon_ is mathematically equivalent, or
| wrong.
| messe wrote:
| Doesn't this just come down to whether you consider there to
| be any philosophical difference between isomorphism and
| equality?
| 6gvONxR4sf7o wrote:
| This is a lovely friday morning diversion. I won't comment on the
| mathematical content, since the article did such an enjoyable
| job, but I do want to call out this slightly tangential quote:
|
| > Could it be that I'm the first person ever to notice the
| curious properties of twin tweens? No. I am past the age of
| entertaining such droll thoughts, even transiently. If I have not
| found any references, it's doubtless because I'm not looking in
| the right places.
|
| Ever since I read Neal Stephenson's Anathem, this idea has stuck
| with me. Especially in regards to questions about who deserves
| the glory for creating/popularizing things first. Vanishingly few
| ideas are new, and that's okay. Journey, not destination, yada
| yada... What a fun write-up.
| ur-whale wrote:
| > If I have not found any references, it's doubtless because
| I'm not looking in the right places.
|
| This is one increasingly frustrating aspect of math and so-
| called hard sciences in general: there is an explosion of
| content since - say - the 18th century that it has become
| increasingly hard to actually find if and where there exists
| published work on a specific topic.
|
| Google is of course a tremendous help, but:
| a) the web has not yet absorbed all scientific literature:
| between walled gardens and stuff that hasn't been scanned yet,
| content is still hard to get to or even index b)
| different scientific fields are often busy re-inventing the
| wheel, assigning their own jargon to the same underlying
| concepts, leading to a rather confusing landscape.
|
| In the "old days", we had librarians, folks who could guide you
| towards that elusive piece of knowledge you desperately needed.
|
| Wishful thinking: I believe a new academic discipline to
| classify, organize and index scientific knowledge (I'm aware of
| existing systems - they are lacking, as exemplified by this
| article), including missionary-style undertaking to try and
| convince different branch of sciences to gently and slowly
| converge towards a uniform language for scientific knowledge.
| howmayiannoyyou wrote:
| Off topic, but: Reading the post title made me wonder: Does
| having neighbors with Amazon Prime Memberships result in getting
| your purchases faster even if you don't have a membership?
| captn3m0 wrote:
| From my limited understanding of Prime India: No.
| kerblang wrote:
| I was actually expecting this was about Amazon collecting data on
| the neighbors of Prime customers by forming some composite view
| of not-Prime vs. Prime traffic. My knee seems to be trained to
| jerk in a persistent direction...
| intrasight wrote:
| I'm in #4. My neighbors are prime across the street (#3 and #5)
| and non-prime on my side (#2 and #6)
| chills wrote:
| 2 is prime
| techbio wrote:
| 2 is the least prime number
| intrasight wrote:
| Yes, of course. So three of four neighbors are prime.
___________________________________________________________________
(page generated 2021-11-05 23:01 UTC)