Intersections of sets of primes

caters · 2014-03-18 06:41:56

We have this set of primes which is infinite. This has lots of different subsets. Here is the list of subsets:
Real Eisenstein primes: 3x + 2
Pythagorean primes: 4x + 1
Real Gaussian primes: 4x + 3
Landau primes: x^2 + 1
Central polygonal primes: x^2 - x + 1
Centered triangular primes: 1/2(3x^2 + 3x + 2)
Centered square primes: 1/2(4x^2 + 4x + 2)
Centered pentagonal primes: 1/2(5x^2 + 5x + 2)
Centered hexagonal primes: 1/2(6x^2 + 6x + 2)
Centered heptagonal primes: 1/2(7x^2 + 7x + 2)
Centered decagonal primes: 1/2(10x^2 + 10x + 2)
Cuban primes: 3x^2 + 6x + 4
Star Primes: 6x^2 - 6x + 1
Cubic primes: x^3 + 2
Wagstaff primes: 1/3(2^n + 1)
Mersennes: 2^x - 1
thabit primes: 3 * 2^x - 1
Cullen primes: x * 2^x + 1
Woodall primes: x * 2^x - 1
Double Mersennes: 1/2 * 2^2^x - 1
Fermat primes: 2^2^x + 1
Alternating Factorial Primes: if x! has x being odd than every odd number when you take the factorial positive and every even number negative. Opposite for even indexed factorials. For example 3rd alternating factorial = 1! - 2! + 3!
Primorial primes: First n primes multiplied together - 1
Euclid primes: first n primes multiplied together + 1
Factorial primes: x! + 1 or x! - 1
Leyland primes: m^n + n^m where m can be anything not negative but n has to be greater than 1
Pierpont primes: 2^m * 3^n + 1
Proth primes: n * 2^m + 1 where n < 2^m
Quartan primes: m^4 + n^4
Solinas primes: 2^m ± 2^n ± 1 where 0< n< m
Soundararajan primes: 1^1 + 2^2 ... n^n for any n
Three-square primes: l^2 + m^2 + n^2
Two Square Primes: m^2 + n^2
Twin Primes: x, x+2
Cousin primes: x, x+4
Sexy primes: x, x + 6
Prime triplets: x, x+2, x+6 or x, x+4, x+6
Prime Quadruplets: x, x+2, x+6, x+8
Titanic Primes: x > 10^999
Gigantic Primes: x > 10^9999
Megaprimes: x > 10^999999

Now Here is a question. Can you find a number where at least 2 of the sets intersect? I will try to do this myself. Just so you know I am going up to 12 digit primes because that is the largest prime my computer will test without the program taking too long to test it and to be sure I find intersections of the sets.

Another question is if I use the number of intersections between 2 sets of 2 types of primes up to 12 digits and I compare that to the number of intersections in a different pair of sets can I figure out which sets have the most intersections?

I want to know the answer to the first and a hint for the answer of the second one.

I am in 9th grade but know some trig and precalculus.

Last edited by caters (2014-03-18 07:13:23)

bobbym · 2014-03-18 07:59:24

Hi;

You can, if you go to some finite limit. Just a programming problem.

caters · 2014-03-18 08:10:44

yeah I know I can if I go to a finite limit but will a pair of sets that has more intersections up to a finite limit have more intersections than a pair of sets with less intersections up to a finite limit if you go to infinitely many digits? In other words if I do this up to 12 digits will the same thing apply with any number of digits?

bobbym · 2014-03-18 08:31:20

For one thing, you can not measure the size of infinite sets like that. Do you know about Cantor?

caters · 2014-03-18 08:42:23

I know about his fractals. Not much about it though. I know much more about the dragon curve, the Mandelbrot set, and the Koch Snowflake than the Cantor set fractal.

bobbym · 2014-03-18 10:28:25

Hi;

I did not mean a fractal. Cantor was the first guy to show how to compare the size of infinite sets. For instance:

For a finite set from 1 to 2n, the set of natural numbers N, is twice the size of the set of even numbers from 1 to n. But when we compare the two infinite sets they are the same size!

caters · 2014-03-18 11:10:03

How can that be? There are half as many even numbers as positive integers so how can the infinite sets be the same size?

bobbym · 2014-03-18 11:30:41

That is why I asked if you knew about Cantor. There are infinite sets that are bigger than other infinite sets too. We can not really expect to count infinite numbers of thing the same way we count ordinary, everyday objects.

anonimnystefy · 2014-03-18 12:23:16

Hi caters

Think about it - for every integer, there is a corresponding double. This is an intuitive way of thinking about sizes of infinite sets, but this logic is also used to define the formal way of comparing set sizes.

bobbym · 2014-03-18 12:42:31

Also, some ( can this be done ) of those types of primes ( do not know all of them ) can be put into a one to one correspondence with the natural numbers and therefore are the same size.

eigenguy · 2014-03-18 13:03:19

Leaving aside questions of infinite sets, I think the comparison caters is wanting is asymptotic density: For any set A, let A[sub]N[/sub] be the number values in it that are <= N. His question is, I think, how does |A[sub]N[/sub] π B[sub]N[/sub]| / N for some pair of sets A and B compare to the same ratio for other pairs of sets as N increases without bound? (If you haven't seen the notation before, the "absolute value" signs here actually mean cardinality, or set size).

Unfortunately, you can't extrapolate behavior from low numbers to high numbers (and any time you are testing by brute force, you are only looking at low numbers, no matter how high you go). The problem is, in the low numbers, there just isn't enough variation for some things to happen that otherwise would, while the tight quarters also forces other coincidences to occur that would otherwise be quite rare. As the numbers grow, there is more room to move around, as it were, and the behavior starts to change.

I haven't studied prime sets much myself, so I can't comment too deeply on them, but as a different example of what I am talking about: try writing numbers out as a sum of 4 positive squares. It obviously cannot be done for 1, 2, or 3. 4 = 1[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup]. For 5 and 6, it is impossible again, but 7 = 2[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup], and so on.
From the first 30 numbers, you would expect that occasional failures to be expressible as 4 squares would continually crop up. But in fact, there are only 12 of them, with the highest being somewhere in the 30s (I don't remember the exact value and am too lazy to look it up). So if you don't look far enough, you get the wrong about the behavior.

The problem is, you also generally have no idea about how far is far enough. For some problems 40 or 50 are enough to see what's going on. For others, even Ackerman's number may prove far too small. This is the shortcoming of experimental mathematics - it can only tell you about where you've looked. The behavior might change just beyond.

eigenguy · 2014-03-18 13:14:36

Oops - just checked, and its the sum of 5 positive squares that is always possible after a certain point. I think 4 positive squares will always have exceptions (though if 0 is allowed, Lagrange's 4 square theorem says that natural number can be written as sum of 4 squares).

bobbym · 2014-03-18 13:32:07

Hi;

Welcome to the forum. 33 is not representable as the sum of 5 positive squares. That might be the maximum.

eigenguy · 2014-03-18 14:43:18

Probably. If I recall, the proof was to examine numbers up to 169 by brute force. Above 169, you first subtracted 169 from it, apply the Lagrange 4 square theorem to write the result as a sum of 4 squares, some of which could be zero. Then just took noticing that 169 = 13[sup]2[/sup] = 12[sup]2[/sup] + 5[sup]2[/sup] = 12[sup]2[/sup] + 4[sup]2[/sup] + 3[sup]2[/sup] = 10[sup]2[/sup] + 7[sup]2[/sup] + 4[sup]2[/sup] + 2[sup]2[/sup]. So if N is the original number and N - 169 = A[sup]2[/sup] + B[sup]2[/sup] + C[sup]2[/sup] + D[sup]2[/sup], with A >= B >= C >= D, then:

If D > 0, then N = A[sup]2[/sup] + B[sup]2[/sup] + C[sup]2[/sup] + D[sup]2[/sup] + 13[sup]2[/sup].
If D = 0, C > 0, then N = A[sup]2[/sup] + B[sup]2[/sup] + C[sup]2[/sup] + 12[sup]2[/sup] + 5[sup]2[/sup].
If C = 0, B > 0, then N = A[sup]2[/sup] + B[sup]2[/sup] + 12[sup]2[/sup] + 4[sup]2[/sup] + 3[sup]2[/sup].
If B = 0, then N = A[sup]2[/sup] + 10[sup]2[/sup] + 7[sup]2[/sup] + 4[sup]2[/sup] + 2[sup]2[/sup].
(A cannot be 0).

danaj · 2014-03-18 17:24:01

There are plenty of other not-uncommonly-discussed sets as well, e.g. Safe, Sophie Germain, Lucas, Fibonacci, Lucky, Palindromic, Pillai, Good, Cuban (y+1, y+2), Primorial (+1, -1), Euclid, Circular, Panaitopol. (Re digressing about Euclid and Primorial, one wants to distinguish between P#+/-1 and Pn#+/-1 -- that is primes up to P or the Pn-th prime). I'm sure one could come up with another hundred sets. Surveying OEIS would bring up lots of them, for example.

For intersections, I found a useful practical method to be listing the allowable subsets of n mod 210 for each type. Some don't have a pattern, but many do (e.g. cuban1, cuban2, twin, triplet, quadruplet, cousin, sexy, safe, sophie, panaitopol to name some). Not only does this help for single cases, but one can then do the intersection of the two (or 3 or more) types. Sometimes this yields a null set once past tiny numbers (e.g. quadruplet cuban primes, or safe quadruplets other than 5 and 11).

This doesn't really help answer the original questions however. For my reading of the first question, certainly we can find examples where sets intersect, e.g. twin sexy primes, or titanic cousin primes (e.g. 10^1000 + 744843).

I believe the answer to your second question is no in general. In some of the cases, the number of intersections from A to B between two sets will not necessarily follow the same trend as between A to B+delta. In other cases (what I believe most people are discussing) both sets will be infinite, though maybe it would be possible to prove that the number of elements of set P in an interval is always greater than the number of elements of set Q in the same interval, or compare asymptotic densities, or something along those lines (e.g. the density of titanic primes in an interval starting after 10^1000 is going to be at least as dense as any of the restricted sets in the same interval).

caters · 2014-03-19 12:53:36

eigenguy wrote:

Leaving aside questions of infinite sets, I think the comparison caters is wanting is asymptotic density: For any set A, let A[sub]N[/sub] be the number values in it that are <= N. His question is, I think, how does |A[sub]N[/sub] π B[sub]N[/sub]| / N for some pair of sets A and B compare to the same ratio for other pairs of sets as N increases without bound? (If you haven't seen the notation before, the "absolute value" signs here actually mean cardinality, or set size).
Unfortunately, you can't extrapolate behavior from low numbers to high numbers (and any time you are testing by brute force, you are only looking at low numbers, no matter how high you go). The problem is, in the low numbers, there just isn't enough variation for some things to happen that otherwise would, while the tight quarters also forces other coincidences to occur that would otherwise be quite rare. As the numbers grow, there is more room to move around, as it were, and the behavior starts to change.
I haven't studied prime sets much myself, so I can't comment too deeply on them, but as a different example of what I am talking about: try writing numbers out as a sum of 4 positive squares. It obviously cannot be done for 1, 2, or 3. 4 = 1[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup]. For 5 and 6, it is impossible again, but 7 = 2[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup] + 1[sup]2[/sup], and so on.
From the first 30 numbers, you would expect that occasional failures to be expressible as 4 squares would continually crop up. But in fact, there are only 12 of them, with the highest being somewhere in the 30s (I don't remember the exact value and am too lazy to look it up). So if you don't look far enough, you get the wrong about the behavior.
The problem is, you also generally have no idea about how far is far enough. For some problems 40 or 50 are enough to see what's going on. For others, even Ackerman's number may prove far too small. This is the shortcoming of experimental mathematics - it can only tell you about where you've looked. The behavior might change just beyond.

well I decided the largest 12 digit prime my computer will test is a good number because then I am sure to find intersections between sets.

Density is real easy, take the number of primes of a certain type up to some finite limit and divide that by the number of numbers in that finite limit. density of twin primes in the set of primes for example. Just take the actual number of twin primes up to a limit and divide that by the number of primes in that limit. Same for others like the density of the 2 types of prime triplets etc.

The n/log(n) for primes is lim x(where x is = n/log(n)) as x -> ∞ = # of primes/# number of positive integers. It is not an exact bound but rather a limit which means it is approximate and it gets closer and closer but in this case it never reaches it.

Last edited by caters (2014-03-19 12:55:23)

bobbym · 2014-03-19 13:20:28

well I decided the largest 12 digit prime my computer will test is a good number because then I am sure to find intersections between sets.

What intersections did you get?

caters · 2014-03-19 14:25:27

Here are the first 3 sets I have found intersections with:

Real Eisenstein with Pythagorean:
5
Real Eisenstein with Gaussian:
11
Real Eisenstein with Landau:
2, 5, 17, 101, 197, 257, 401, 677, 1601, 3137, 5477, 8837, 12101, 13457, 15377, 16901, 17957, 21317, 25601, 28901, 30977, 42437, 50177, 52901, 55697, 62501, 65537, 67601, 78401, 80657, 98597, 106277, 115601, 122501, 148997, 160001, 164837, 184901, 190097, and it continues on and on and on. There are infinite intersections betwen real eisenstein primes and landau primes. This makes sense because:
There are infinite primes
There are infinite primes that satisfy 3x+2
There are infinite primes that satisfy x^2 + 1
any line will intersect a parabola infinitely many times even though it gets further and further apart.

bobbym · 2014-03-19 14:27:26

There are infinite primes that satisfy x^2 + 1
any line will intersect a parabola infinitely many times even though it gets further and further apart.

You must mean something else. A line can only intersect a parabola at two points.

caters · 2014-03-19 14:30:57

but when I program this:
x = 1
square x and add 1

and I do that for any x and I solve for x when I get a prime number that follows x^2 + 1 and have 3x+2 on the other side I get infinitely many numbers that satisfy both.

If I get infinitely many primes that satisfy both 3x+2 which is a line and x^2 + 1 which is a parabola shifted up by 1 doesn't that mean that a line can intersect a parabola infinitely many times?

Last edited by caters (2014-03-19 14:33:09)

bobbym · 2014-03-19 14:33:23

Is that a proved statement, that there are an infinite number of intersections?

caters · 2014-03-19 14:38:33

well I have found lots of x's that give me prime numbers that satisfy both x^2+1 and 3x+2 so my theorem is that there are infinite intersections between x^2 + 1 and 3x+2 and thus a line and a parabola can have infinite intersection points.

bobbym · 2014-03-19 14:41:16

Hi;

You only have to plot it to see that a line can only intersect a parabola at 2 points.

What you are doing is generating primes using a line and a second order equation. It does not imply multiple intersections.

caters · 2014-03-19 14:58:59

I know it does not imply more than 2 intersections. I also know that lines can intersect other lines only once unless the 2 equations are the same exact line. I graphed 3x+2 and x^2 + 1 and I got 1/2 * (3 + positive square root of 13) and 1/2 * (3 + negative square root of 13).

I also solved for x when x^2 + 1 was prime and on the right side I had 3x+2 and sometimes got a fraction and multiple times got an integer.

the graphing of the 2 says "0 primes intersect in this set. It is an empty set the intersection is." however the solving for x when x^2 + 1 is prime says "There are multiple intersections in these sets and I suspect that there are infinitely many."

bobbym · 2014-03-19 15:23:04

It looks like Charles has pretty much answered your question over at the SE. How come you have not looked at it?

Math Is Fun Forum

#1 2014-03-18 06:41:56

Intersections of sets of primes

#2 2014-03-18 07:59:24

Re: Intersections of sets of primes

#3 2014-03-18 08:10:44

Re: Intersections of sets of primes

#4 2014-03-18 08:31:20

Re: Intersections of sets of primes

#5 2014-03-18 08:42:23

Re: Intersections of sets of primes

#6 2014-03-18 10:28:25

Re: Intersections of sets of primes

#7 2014-03-18 11:10:03

Re: Intersections of sets of primes

#8 2014-03-18 11:30:41

Re: Intersections of sets of primes

#9 2014-03-18 12:23:16

Re: Intersections of sets of primes

#10 2014-03-18 12:42:31

Re: Intersections of sets of primes

#11 2014-03-18 13:03:19

Re: Intersections of sets of primes

#12 2014-03-18 13:14:36

Re: Intersections of sets of primes

#13 2014-03-18 13:32:07

Re: Intersections of sets of primes

#14 2014-03-18 14:43:18

Re: Intersections of sets of primes

#15 2014-03-18 17:24:01

Re: Intersections of sets of primes

#16 2014-03-19 12:53:36

Re: Intersections of sets of primes

#17 2014-03-19 13:20:28

Re: Intersections of sets of primes

#18 2014-03-19 14:25:27

Re: Intersections of sets of primes

#19 2014-03-19 14:27:26

Re: Intersections of sets of primes

#20 2014-03-19 14:30:57

Re: Intersections of sets of primes

#21 2014-03-19 14:33:23

Re: Intersections of sets of primes

#22 2014-03-19 14:38:33

Re: Intersections of sets of primes

#23 2014-03-19 14:41:16

Re: Intersections of sets of primes

#24 2014-03-19 14:58:59

Re: Intersections of sets of primes

#25 2014-03-19 15:23:04

Re: Intersections of sets of primes

Board footer