## Re: A question

Expand Messages
• ... I agree. ... A is defined recursively so, rather than your depth (which I m not sure I understand) I favour a measure recursion_depth , which would
Message 1 of 12 , Oct 1, 2011
--- In primenumbers@yahoogroups.com, "Mark" <mark.underwood@...> wrote:
>
> --- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@> 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?
> >
>
> I can't think of a reason why any prime would be excluded from being a factor of numbers in the set.

I agree.

> I've only gone 5 'deep', and thus far 19 is the only
> prime < 29 that hasn't shown up yet. 11 and 17 were
> late to the party, but they eventually surfaced at depth 5.

A is defined recursively so, rather than your "depth" (which I'm not sure I understand) I favour a measure "recursion_depth", which would enumerate the elements of A in order of their appearance as follows:-
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.

2621 elements have been inserted into A at this recursion_depth; but 86 others have not been inserted, since they exceed the size limit of 10^64 which I imposed on numbers so that they can be factorised in at most a few seconds.

Mike
• ... 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
Message 2 of 12 , Oct 1, 2011
--- 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
• ... After the work Mark and Mike did, it really seems that any prime number is Euclid-style accessible. Unfortunately, I have no idea how this could be proved.
Message 3 of 12 , Oct 1, 2011
--- In primenumbers@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
> > I can't think of a reason why any prime would be excluded from being a factor of numbers in the set.
>
> I agree.
After the work Mark and Mike did, it really seems that any prime number is Euclid-style accessible. Unfortunately, I have no idea how this could be proved.

> > I've only gone 5 'deep', and thus far 19 is the only
> > prime < 29 that hasn't shown up yet. 11 and 17 were
> > late to the party, but they eventually surfaced at depth 5.
>
> A is defined recursively so, rather than your "depth" (which I'm not sure I understand) I favour a measure "recursion_depth", which would enumerate the elements of A in order of their appearance as follows:-
> 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.
I also would understand the notion of depth in this way. When I wrote "No, I have not gone even to that depth", I actually meant I did not go to a depth at which, for instance, 11 and 17 are already shown to be Euclid-style accessible.

In addition to this notion of accessibility, maybe a stronger one also deserves some attention, namely the one we get when we replace "y is a prime divisor of x+1" with "y is the least prime divisor of x+1" in the definition of the set A.

Dimiter
• ... In this case, of course, the tree degenerates into a list, and so is more straightforward to program; and we have simply card(A)=recursion_depth. Defining
Message 4 of 12 , Oct 1, 2011
--- In primenumbers@yahoogroups.com, "Dimiter Skordev" <skordev@...> wrote:
>
> In addition to this notion of accessibility, maybe a stronger one also deserves some attention, namely the one we get when we replace "y is a prime divisor of x+1" with "y is the least prime divisor of x+1" in the definition of the set A.
>

In this case, of course, the tree degenerates into a list, and so is more straightforward to program; and we have simply
card(A)=recursion_depth.

Defining the function s(m), for integer m, to be its smallest prime factor, your set A is the set {u[n]}, with the (monotonically increasing) sequence u[] being defined by:
u[1] = 1
u[n] = u[n-1] * s(u[n-1]+1), n >= 2

As with the earlier definition, I can see no reason why all primes should not be accessible.

I removed any restriction on size of integer to (attempt to) factorise.

For 14 <= recursion_depth <= 28, the first inaccessible prime is 19.

I have now run into a brick wall:
u[28]=326408399720836161014262419152749\
231088487789442706259494316079679210912\
54869713984092316692981590
and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).

ecm anyone?

Mike
• ... PRP27 = 643679794963466223081509857 PRP28 = 2496022367830647867616317307 PRP44 = 20316223246552213835636779619145529457704309 [Non-text portions of this
Message 5 of 12 , Oct 1, 2011
>
> I have now run into a brick wall:
> u[28]=326408399720836161014262419152749\
> 231088487789442706259494316079679210912\
> 54869713984092316692981590
> and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).
>

PRP27 = 643679794963466223081509857
PRP28 = 2496022367830647867616317307
PRP44 = 20316223246552213835636779619145529457704309

[Non-text portions of this message have been removed]
• ... Thanks, Bernardo. Now do you feel like factorising the 98+27=125-digit integer (u[29]+1) ... Mike
Message 6 of 12 , Oct 1, 2011
--- In primenumbers@yahoogroups.com, Bernardo Boncompagni <RedGolpe@...> wrote:
>
> >
> > I have now run into a brick wall:
> > u[28]=326408399720836161014262419152749\
> > 231088487789442706259494316079679210912\
> > 54869713984092316692981590
> > and pari-Gp is struggling to factorise the 98-digit integer (u[28]+1).
> >
>
> PRP27 = 643679794963466223081509857
> PRP28 = 2496022367830647867616317307
> PRP44 = 20316223246552213835636779619145529457704309
>

Thanks, Bernardo.

Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)
:-)

Mike
• ... Somebody has been here before, carried it up to 256 digits, and saved it all in the factordb http://factorization.ath.cx/index.php?id=1100000000024656542
Message 7 of 12 , Oct 1, 2011
• ... We only need the smallest factor which is trivially found by trial factoring to be 103. The sequence of smallest prime factors is the Euclid-Mullin
Message 8 of 12 , Oct 1, 2011
Mike wrote:
> Now do you feel like factorising the 98+27=125-digit integer (u[29]+1)

We only need the smallest factor which is trivially found by trial
factoring to be 103.
The sequence of smallest prime factors is the Euclid-Mullin sequence.
See for example http://oeis.org/A000945 and
http://en.wikipedia.org/wiki/Euclid%E2%80%93Mullin_sequence

The smallest missing prime in the 47 known terms is 31.

--
Jens Kruse Andersen
• ... It is notable that only one known factorization is incomplete: http://www.rieselprime.de/Others/EuclidMullin.htm and in that case it suffices to show that
Message 9 of 12 , Oct 1, 2011