## 23297Re: A question

Expand Messages
• Oct 1 8:05 AM
• 0 Attachment
--- 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
• Show all 12 messages in this topic