Set of primes

[LaurV]

Originally Posted by CRGreathouse

My counts (which are off by one from yours, probably one of us has a fencepost error):

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

[axn]

Originally Posted by LaurV

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

1 is a 2 bit number?!

EDIT:- Nevermind. This is cumulative total.

[CRGreathouse]

Originally Posted by LaurV

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

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

Next few counts:

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

[LaurV]

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.

[science_man_88]

Originally Posted by LaurV

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.

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.

[science_man_88]

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

{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
}

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

[Citrix]

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.

[CRGreathouse]

Originally Posted by Citrix

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.

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

[science_man_88]

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:

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

[science_man_88]

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.

[CRGreathouse]

Those attachments look right to me, sm88.