mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2017-03-07, 01:42   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

1,583 Posts
Default Set of primes

Consider a set S that consists of the number 1 and certain primes.
A prime p will belong to the set if p-1=a*b*c & a,b,c belong to set S
a,b,c do not have to be distinct from each other i.e. a=b=c is possible.

Would such a set contain an infinite number of primes? Can you provide a proof?
If the set is finite- how many numbers/primes are in the set?

Any help will be appreciated.
Citrix is offline   Reply With Quote
Old 2017-03-07, 03:19   #2
axn
 
axn's Avatar
 
Jun 2003

3·17·101 Posts
Default

Quote:
Originally Posted by Citrix View Post
A prime p will belong to the set if p-1=a*b*c
Or p-1 = a*b
Or p-1 = a
(since 1 is in the set)

Of course, the last of these is useless since that will not generate new primes.

As for the key question, I don't have any ideas. Obviously the set will not contain all the primes.
axn is offline   Reply With Quote
Old 2017-03-07, 03:40   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by axn View Post
Or p-1 = a*b
Or p-1 = a
(since 1 is in the set)

Of course, the last of these is useless since that will not generate new primes.

As for the key question, I don't have any ideas. Obviously the set will not contain all the primes.
a=b=c=1 produces 2 as in the set.
a=b=1 and c=2 produces 3 in the set.
a=b=2 and c=1 produces 5 in the set.
a=2, b=3, c=1 produces 7 in the set.
a=b=2, c=3 produces 13 in the set.
a=2,b=5, c=1 produces 11 in the set.

via the same argument as the infinitude of the primes themselves p=a*b*c+1 either p is prime or is a composite with factors not in the set {a,b,c} ( but not necessarily not in the full set overall). edit: and of course we can show by argument that the p in the set are the union of subsets of primes that are 1 more than a prime or 1 aka {2,3}, primes that are 1 more than a semiprime ( including the ones formed non distinctly aka prime squares), and primes that are one more than a 3 almost prime (triprimes).

Last fiddled with by science_man_88 on 2017-03-07 at 03:47
science_man_88 is offline   Reply With Quote
Old 2017-03-07, 04:35   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

97×101 Posts
Default

So, your set contains 1, 2(=1*1*1+1), 3(=1*1*2+1), 5(=1*2*2+1), 7(=1*2*3+1), 11(=1*2*5+1), 13(=2*2*3+1), 19(=2*3*3+1), 23(=1*2*11+1), 29(=2*2*7+1), 31(=2*3*5+1), 43(=2*3*7+1), etc. It does not contain 17, as 16 is not a product of at most 3 primes, and it does not contain 37, 41, as neither 36 nor 40 is a product of maximum 3 primes.

From here onward, they are getting rarer... One observation is that 2 is always a part of the product, because otherwise you get even numbers, which are not prime. So, you can exclude it from the set, and reformulate the problem:

There is a set S containing {3, 5} and all odd primes of the form 2p+1, 4p+1, 2pq+1, with p, q in set, not necessarily distinct. Is the set S infinite?

From here it may be (?!?) easier to devise a proof. For example, split it in 3, subsets, for 2p, 4p, and 2pq, if any of this is infinite...

Of course, if you prove this, you are a step closer to prove that there are an infinite number of Sophie-Germain primes (which is a kinda "tough" conjecture to prove).

Last fiddled with by LaurV on 2017-03-07 at 04:44
LaurV is offline   Reply With Quote
Old 2017-03-07, 04:51   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

175B16 Posts
Default

I don't see any reason it would be finite, but I can't immediately find a proof that it must be infinite. Am I missing something easy?

There are a lot of these primes in any case -- with the minimal definition, allowing only those primes which must be included, the millionth such prime is 3516312561594070598483.
CRGreathouse is offline   Reply With Quote
Old 2017-03-07, 04:52   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

I should also mention that these primes (or rather, the minimal such set) is a subsequence of A079151 in the OEIS.
CRGreathouse is offline   Reply With Quote
Old 2017-03-07, 05:02   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

97·101 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
via the same argument as the infinitude of the primes themselves p=a*b*c+1 either p is prime or is a composite
Huh? this is blabbering. You can not prove it like that. Who is p? Who is a, b, c?
The "infinitude of primes" goes like that: you assume that the set is finite, then (because the set is finite) you can make a product+1 and this product+1 is NOT in the set, because is BIGGER than everything in the set. Therefore is not prime (all primes are in the set), therefore it factors in some primes. But those primes all divide the product, then it means that all divide the "+1", absurd. So the assumption is false.

Here you can not apply that, any number p in set is a product of either 2a, 4a, or 2ab, with a, b, in set, and added 1. It helps you nothing. You may run into a set where, for all a, b, in it, all numbers of the form 2a+1, 4a+1, 2ab+1, are composite. There are n^2+2n numbers, and as you get higher, their chance to be prime is lower. Then your set is finite and you are stuck.

Last fiddled with by LaurV on 2017-03-07 at 05:14
LaurV is offline   Reply With Quote
Old 2017-03-07, 05:16   #8
Citrix
 
Citrix's Avatar
 
Jun 2003

1,583 Posts
Default

I generated the number of primes that belong to the set under each bit level

Code:
Bit 	# of primes
16	160
17	199
18	243
19	286
20	334
25	864
32	2782
33	3324
40	10013
Since the primes are getting less and less frequent (faster than the set of all primes) ... would this suggest that the set is finite?
Citrix is offline   Reply With Quote
Old 2017-03-07, 05:23   #9
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

100110010001012 Posts
Default

Not necessarily. As CRG suggested, we believe it is infinite. However we do not have some heuristic for it, and a proof is not easy. Your set contains SG/safe primes, but only few of them (for example 83, it is in A079151, because 82=2*41, but it is not in your list, because 41 is neither in any of the lists, and so on with higher primes like 83*2+1, etc). But most of the primes in your set are of the form 2pq+1, with pq in set. Maybe here a proof can be made? (no idea).

Last fiddled with by LaurV on 2017-03-07 at 05:24
LaurV is offline   Reply With Quote
Old 2017-03-07, 05:47   #10
Citrix
 
Citrix's Avatar
 
Jun 2003

1,583 Posts
Default

Quote:
Originally Posted by LaurV View Post
Not necessarily. As CRG suggested, we believe it is infinite. However we do not have some heuristic for it, and a proof is not easy. Your set contains SG/safe primes, but only few of them (for example 83, it is in A079151, because 82=2*41, but it is not in your list, because 41 is neither in any of the lists, and so on with higher primes like 83*2+1, etc). But most of the primes in your set are of the form 2pq+1, with pq in set. Maybe here a proof can be made? (no idea).
If you fix the value of p in 2pq+1, then you get a finite set for every p value.

Code:
# of p values *  finite set for each p value = Total number of values in set S
This would suggest it would be finite.. but I am not sure how to prove it.
Citrix is offline   Reply With Quote
Old 2017-03-07, 05:51   #11
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by Citrix View Post
I generated the number of primes that belong to the set under each bit level

Code:
Bit 	# of primes
16	160
17	199
18	243
19	286
20	334
25	864
32	2782
33	3324
40	10013
Since the primes are getting less and less frequent (faster than the set of all primes) ... would this suggest that the set is finite?
My counts (which are off by one from yours, probably one of us has a fencepost error):
Code:
2 2
3 4
4 6
5 10
6 14
7 18
8 22
9 31
10 42
11 56
12 68
13 84
14 105
15 130
16 159
17 198
18 242
19 285
20 333
21 409
22 504
23 607
24 735
25 863
26 1014
27 1203
28 1430
29 1699
30 2010
31 2366
32 2804
33 3323
34 3898
35 4610
36 5360
37 6246
38 7323
39 8597
40 10012
41 11756
42 13695
43 15984
44 18600
45 21709
46 25231
47 29296
48 33922
49 39459
50 45855
51 53069
52 61560
53 71169
54 82222
55 95004
56 109849
57 126998
58 146625
59 169279
60 195251
61 225061
62 259440
63 299380
64 344979
65 397505
66 458052
67 527392
68 606366
69 697446
70 802544
71 923136
72 1061157
73 1218615
74 1400323
75 1608993
76 1848027
don't seem to be slowing down. I would be at least somewhat surprised to learn that S was finite.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Distribution of Mersenne primes before and after couples of primes found emily Math 34 2017-07-16 18:44
Conjecture about Mersenne primes and non-primes v2 Mickey1 Miscellaneous Math 1 2013-05-30 12:32
A conjecture about Mersenne primes and non-primes Unregistered Information & Answers 0 2011-01-31 15:41
possible primes (real primes & poss.prime products) troels munkner Miscellaneous Math 4 2006-06-02 08:35

All times are UTC. The time now is 13:10.


Tue Oct 26 13:10:50 UTC 2021 up 95 days, 7:39, 0 users, load averages: 1.40, 1.38, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.