--- In

primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:

>

> > > Let A be the least set of natural numbers with the following two properties:

> > > (i) the number 1 belongs to A;

> > > (ii) whenever x belongs to A, and y is a prime divisor of x+1, the product x*y also belongs to A.

> > > Let us call a prime number Euclid-style accessible if it is a divisor of some number belonging to A. Are there prime numbers that are not Euclid-style accessible, and if there are such ones, which is the least among them?

>

> x*y recursion_depth

> 1 1

> 1*2 2

> 2*3 3

> 6*7 4

> 42*43 5

> 1806*13 6

> 1806*139 6

> etc.

>

> Going to recursion_depth=13, pari_GP take a couple of minutes

> to find that all primes < 271 are Euclid-style accessible.

>

Here are the results of running pari-GP on a single Intel core @ 1.8 GHz:-

depth first_inaccessible card(A) time

1 2 1 0 secs

2 3 2 0 secs

3 5 3 0 secs

4 5 4 0 secs

5 5 5 0 secs

6 5 7 0 secs

7 11 11 0 secs

8 11 20 0 secs

9 19 44 0 secs

10 19 96 0.05 secs

11 47 261 0.28 secs

12 103 808 15.71 secs

13 271 2621 161.9 secs

14 827 8151 788.2 secs

15 1913 23884 3779.3 secs

At depth 12, 13, 14, 15, the number of elements of A > 10^64 (and so left unfactorised) were 4, 86, 780, 3894, respectively.

Mike