Does having prime neighbors make you more composite? | Hacker News Reader

Does having prime neighbors make you more composite?

bit-player.org

147 pointsanother43 comments

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.

> 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.

We still have librarians and they can still guide you towards nirvana. As my librarian friend puts it, she got a master's degree in googling better than everyone else.

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.

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.

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?

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.

> 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

Thank you, you're absolutely right: I meant to say P(A | B) > P(A). By excluding !B, you're necessarily excluding only the Nil group. I think I got it right in my edit, but thank you for correcting my thinking here.

"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.

This is an observation on which the proof depends, but, as is logically required, it is not the proof.

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.

> Now we can see clearly that primes are always next to at least one composite number.

That only is true for odd primes, and then, doesn’t require that long an argument. If p is an odd prime, p+1 is divisible by 2 and not equal to 2, so it is composite :-)

Back to the article: I think that using the number of divisors as a measure for compositeness isn’t the best choice. I would use the number of prime factors. That gives 5×5×5×5×5 the same ‘score’ as 2×3×5×7×11, and not a much smaller one.

I also suspect that a large part of the difference between these tween numbers and the other numbers actually shows that, within numbers that are about equal, multiples of 6 are more composite than other numbers. Phrased that way, that isn’t that surprising.

To show that, I would only plot multiples of six in these plots.

Everything you and the post you're replying to raise is discussed in the article. It even does the analysis focused on multiples of six.

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?

From my limited understanding of Prime India: No.

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.

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.

Was going to ask whether this proportion of the number of divisors of these prime tweens, to the number of other divisors of other composites, might yield a known constant, or even converge on 2.718.. or a related function of it asymtotically as the n increased.

odds are, if you have prime neighbors, you are even.

Odds have nothing to do with it, it's guaranteed.

Odds are, if you have two prime neighbours, you're a multiple of three.

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.

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...

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.

I only brought negative "primes" in for this particular article because then 1 and -1 are like twin primes. I usually don't think about negatives in these contexts. Just thought that was interesting.

>Babylonian accountants and land surveyors did their arithmetic in base 60, presumably because sexagesimal numbers help with wrangling fractions.

I thought the agreed theory is its due to Babylonians counting the sections of each finger? The thumb is the pointer and it's used to touch each of the 12 sections five times over one loop per finger (thumb sections are not included). It's also why clocks and time are base 12.

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

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.

Doesn't this just come down to whether you consider there to be any philosophical difference between isomorphism and equality?

There's a difference? Heathen!

I consider isomorphism to be isomorphic to equality. Interpret that as you wish.

Huh, that's an interesting thing to think about, and considering that I probably would've worded my comment differently. Thanks.

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!

I wonder if reversing the statement is useful? Are the neighbors of a highly composite number more likely to be prime?

So should having prime neighbors be a factor when looking at multiples of properties?

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)

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...

Prime neighbours? 3,5,7?

I'm in #4. My neighbors are prime across the street (#3 and #5) and non-prime on my side (#2 and #6)

2 is prime

2 is the least prime number

Yes, of course. So three of four neighbors are prime.

Reply on news.ycombinator.com