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.

[QUOTE=Citrix;454406]A prime p will belong to the set if p-1=a*b*c[/QUOTE]
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.

[QUOTE=axn;454415]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.[/QUOTE]

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

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 [URL="https://en.wikipedia.org/wiki/Sophie_Germain_prime#Infinitude_and_density"]an infinite number of Sophie-Germain primes[/URL] (which is a kinda "tough" conjecture to prove).

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.

I should also mention that these primes (or rather, the minimal such set) is a subsequence of [url=https://oeis.org/A079151]A079151[/url] in the OEIS.

[QUOTE=science_man_88;454416]via the same argument as the infinitude of the primes themselves p=a*b*c+1 either p is prime or is a composite[/QUOTE]
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 [U]assume[/U] 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.

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
[/code]

Since the primes are getting less and less frequent (faster than the set of all primes) ... would this suggest that the set is finite?

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

[QUOTE=LaurV;454433]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).[/QUOTE]

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
[/code]

This would suggest it would be finite.. but I am not sure how to prove it.

[QUOTE=Citrix;454432]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
[/code]

Since the primes are getting less and less frequent (faster than the set of all primes) ... would this suggest that the set is finite?[/QUOTE]

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[/code]
don't seem to be slowing down. I would be at least somewhat surprised to learn that S was finite.

[QUOTE=CRGreathouse;454437]My counts (which are off by one from yours, probably one of us has a fencepost error):
[/QUOTE]
You :razz:
His original set (which includes 1 and 2) has 3 terms of 2 bits (1, 2, 3), 5 terms of 3 bits (5, 7), etc.

[QUOTE=LaurV;454440]You :razz:
His original set (which includes 1 and 2) has 3 terms of 2 bits (1, 2, 3), 5 terms of 3 bits (5, 7), etc.[/QUOTE]

1 is a 2 bit number?!

EDIT:- Nevermind. This is cumulative total.

[QUOTE=LaurV;454440]You :razz:
His original set (which includes 1 and 2) has 3 terms of 2 bits (1, 2, 3), 5 terms of 3 bits (5, 7), etc.[/QUOTE]

Ah yes, I was including only the primes in my set. :smile:

Next few counts:

76 1848027
77 2121688
78 2436010
79 2796830
80 3211028
81 3685127
82 4227347
83 4849991

Yes, it seems that the "supply" is not shrinking too fast. I would put my money on infinite.

As supposed initially, the "2pq+1" part is the driving here, because without it, the set dies very fast, practically {3, 5, 7, 11, 13, 23, 29, 47, 53, 59, 107} seems to be a closed set (i.e. finite). All these, either doubled and added 1, or quadrupled and added 1, are composite. But combinations of two of them, multiply with 2 and add 1, still give enough primes.... Each combination pq can give between 0 and 3 primes (i.e. 2pq+1, 2(2pq+1)+1, and 4(2pq+1)+1 can be all prime, or none prime, then the cycle repeats, a new step). So in average, the list should grow with about log(n^2) at every "pq-parse", where n is the number of the elements in the list, considering the logarithmic density of the primes. But unless proved, this is just some more gibberish.

Example: consider the given set as the initial set, which is closed to 2p+1 and 4p+1 extensions. We have to check for all 11*11 combinations, if z=2pq+1 is prime, and if so, then check if 2z+1 is prime, and/or 4z+1 is prime. Then repeat. This way we add 2p+1 and 4p+1 too, and there is no other step necessary. First parse, there are 11*11=121 combinations, therefore 363 candidates. From these, 25 are prime. Then the list has 36 terms, and there are 3*36*25 candidates at the next step (the old members will not result in new primes, only combinations of all numbers with a new member can result in a new prime, the others are already in the list), i.e. 2700 candidates. From all these, 86 are prime, bringing the set at 122 members. And so on. The list grows 442, 2203, 17122 members. There is always a log factor. If I plot this numbers in excel and use a logarithmic scale of the axis, it looks like a perfect parabola.

Edit: the next value is 246599 members.

[QUOTE=LaurV;454431]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 [U]assume[/U] 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.[/QUOTE]

I didn't say it proved the infinitude of this set but it is true of the subset {a,b,c} you are either producing another member or you are not. edit:you have {2,p,q}
if one of these is 3 then you are in a subset of 6*l+1 where l is a prime ( or 1).
primes other than 3 are 1 or 2 mod 3 p and q can't be both 2 mod 3 or both 1 mod 3 they have to be a mixture and the resulting value will then be 2 mod 3. so only if your primes that are 1 mod 3 keep producing primes with the 2 mod 3 values already in the set can it keep going forever along these lines.

here's a really ugly code for it (seems to jump for 15 ms to about 26 s with an increase of 10 fold in the #d can surpass):

[CODE]{my(d=[1,2,3],e=1);z
until(e==0 || #d>1000,
f=select(q->setminus([q],d)==[q] && isprime(q),apply(r->6*r+1,d));
g=fold((x,y)->vecsort(concat(x,y),,8),select(v->setminus([v],d)==[v] && setminus([v],f)==[v] && isprime(v),apply(t->apply(u->u+1,t),apply(s->2*s,apply(r->r*select(q->q%3!=r%3,d),d)))));
d=vecsort(concat(d,concat(g,f)),,8);
e=#f+#g);
d
}[/CODE]

there's likely already a faster way known that I don't know ( only thing that comes to mind is the 6 ways of arranging {a,b,c} is probably slowing it down without a condition to prevent that). edit:the vecsort in the fold slowed it down a lot for one now about 4 seconds for #d>100000

Let f(x) be the number of prime candidates belonging to the set between 2^x and 2^(x+1).
Then f(x+1)/f(x) → 1.14 (an irrational number, from the data posted above)
If this keeps on holding true then there would be infinite candidates.

[QUOTE=Citrix;454473]Let f(x) be the number of prime candidates belonging to the set between 2^x and 2^(x+1).
Then f(x+1)/f(x) → 1.14 (an irrational number, from the data posted above)
If this keeps on holding true then there would be infinite candidates.[/QUOTE]

Even f(x+1) - f(x) > 0 would suffice. :smile:

here's the data I get based on my code ( the number in each bit level, some bit levels may not be filled completely and started at x=45 and went down but there were 6 greater than 2^45:
[CODE]24
157
362
984
1528
2699
3413
5157
5947
7592
8113
9342
8955
9604
8921
8718
7576
7070
5829
5312
4240
3573
2770
2281
1707
1385
990
734
522
384
278
186
124
83
58
34
21
11
9
4
4
2
2
2
1[/CODE]

sorry second post for those interested here are the actual numbers themselves in 2 files so I don't break the forum size limit on the file.

Those attachments look right to me, sm88.

[QUOTE=CRGreathouse;454492]Those attachments look right to me, sm88.[/QUOTE]

yeah I just figured I'd give the information I could get quickly but you basically already have it and then some.