Set of primes

[Citrix]

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.

[axn]

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.

[science_man_88]

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

[LaurV]

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

[CRGreathouse]

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]

I should also mention that these primes (or rather, the minimal such set) is a subsequence of A079151 in the OEIS.

[LaurV]

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.

[Citrix]

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

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?

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

[Citrix]

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.

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

[CRGreathouse]

Originally Posted by Citrix

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

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):

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.