20170307, 01:42  #1 
Jun 2003
1,583 Posts 
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 p1=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. 
20170307, 03:19  #2 
Jun 2003
3·17·101 Posts 
Or p1 = a*b
Or p1 = 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. 
20170307, 03:40  #3  
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
Quote:
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 20170307 at 03:47 

20170307, 04:35  #4 
Romulan Interpreter
"name field"
Jun 2011
Thailand
97×101 Posts 
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 SophieGermain primes (which is a kinda "tough" conjecture to prove). Last fiddled with by LaurV on 20170307 at 04:44 
20170307, 04:51  #5 
Aug 2006
175B_{16} Posts 
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. 
20170307, 05:02  #7  
Romulan Interpreter
"name field"
Jun 2011
Thailand
97·101 Posts 
Quote:
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 20170307 at 05:14 

20170307, 05:16  #8 
Jun 2003
1,583 Posts 
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 
20170307, 05:23  #9 
Romulan Interpreter
"name field"
Jun 2011
Thailand
10011001000101_{2} Posts 
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 20170307 at 05:24 
20170307, 05:47  #10  
Jun 2003
1,583 Posts 
Quote:
Code:
# of p values * finite set for each p value = Total number of values in set S 

20170307, 05:51  #11  
Aug 2006
3×1,993 Posts 
Quote:
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 

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  20170810 13:47 
Distribution of Mersenne primes before and after couples of primes found  emily  Math  34  20170716 18:44 
Conjecture about Mersenne primes and nonprimes v2  Mickey1  Miscellaneous Math  1  20130530 12:32 
A conjecture about Mersenne primes and nonprimes  Unregistered  Information & Answers  0  20110131 15:41 
possible primes (real primes & poss.prime products)  troels munkner  Miscellaneous Math  4  20060602 08:35 