mersenneforum.org > Math Set of primes
 Register FAQ Search Today's Posts Mark Forums Read

 2017-03-07, 01:42 #1 Citrix     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 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.
2017-03-07, 03:19   #2
axn

Jun 2003

3·17·101 Posts

Quote:
 Originally Posted by Citrix 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.

2017-03-07, 03:40   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by axn 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

 2017-03-07, 04:35 #4 LaurV 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 Sophie-Germain primes (which is a kinda "tough" conjecture to prove). Last fiddled with by LaurV on 2017-03-07 at 04:44
 2017-03-07, 04:51 #5 CRGreathouse     Aug 2006 175B16 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.
 2017-03-07, 04:52 #6 CRGreathouse     Aug 2006 3×1,993 Posts I should also mention that these primes (or rather, the minimal such set) is a subsequence of A079151 in the OEIS.
2017-03-07, 05:02   #7
LaurV
Romulan Interpreter

"name field"
Jun 2011
Thailand

97·101 Posts

Quote:
 Originally Posted by science_man_88 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

 2017-03-07, 05:16 #8 Citrix     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 Since the primes are getting less and less frequent (faster than the set of all primes) ... would this suggest that the set is finite?
 2017-03-07, 05:23 #9 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 100110010001012 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 2017-03-07 at 05:24
2017-03-07, 05:47   #10
Citrix

Jun 2003

1,583 Posts

Quote:
 Originally Posted by LaurV 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.

2017-03-07, 05:51   #11
CRGreathouse

Aug 2006

3×1,993 Posts

Quote:
 Originally Posted by Citrix 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 emily Math 34 2017-07-16 18:44 Mickey1 Miscellaneous Math 1 2013-05-30 12:32 Unregistered Information & Answers 0 2011-01-31 15:41 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