A305382 - OEIS

%I #50 Jul 01 2022 22:06:26

%S 9,8,8,8,8,8,9,8,8,11,9,9,12,12,8,14,10,13,9,9,9,15,11,17,9,12,9,13,

%T 10,10,10,12,9,10,9,13,9,11,10,12,16,9,12,13,16,9,9,10,9,10,11,11,9,

%U 16,10,11,9,10,10,10,9,10,13,18,9,11,10,9,11,12,13,15,9,12,9,11,13,15,10,9,11,11,11,10,11,11,13,14,10,10,10,10,9,12,10,15,17,10,13,9

%N a(n) is the number of distinct primes produced by starting with the n-th prime p and repeatedly looking at all the prime factors of 2p+1, and then performing the same process (double, add 1, find all prime factors) with those primes; a(n) = -1 if this produces infinitely many primes.

%C Based on a question posed by _James Propp_. Terms computed by _Michael Kleber_.

%C _W. Edwin Clark_ observes (Jun 16 2018) that, based on analysis of the first 10^5 primes, the procedure always ends with {3, 5, 7, 11, 13, 19, 23, 47}, which is sequence A020575. In particular, it appears that the total number of primes obtained is always finite.

%C First occurrences are in A316226.

%D James Propp, Posting to Math Fun Mailing List, Jun 16 2018

%H Hans Havermann, <a href="/A305382/b305382.txt">Table of n, a(n) for n = 1..10000</a>

%e a(1)=9: Starting with the first prime, 2, we see that:

%e   2 -> 5 -> 11 -> 23 -> 47 -> 95=5*19,

%e   19 -> 39=3*13,

%e   3 -> 7 -> 15=3*5,

%e   13 -> 27=3*3*3,

%e which produces 9 different primes, 2 3 5 7 11 13 19 23 47.

%t propp1[p_] := propp1[p] = #[[1]] & /@ FactorInteger[2*p + 1];

%t propp[p_Integer] := propp[{p}];

%t propp[s_List] := propp[s, Union[s, Union @@ propp1 /@ s]];

%t propp[s_, t_] := If[s == t, s, If[Length[t] > 1000, OVERFLOW[t], propp[t]]];

%t Table[Length[propp[Prime[n]]], {n, 100}] (* _Michael Kleber_, Jun 16 2018 *)

%t g[lst_List] := Union@ Join[lst, First@# & /@ Flatten[FactorInteger[2 lst + 1], 1]]; f[n_] := Length@ NestWhile[g@# &, {Prime@ n}, UnsameQ, All]; Table[ f[n], {n, 100}] (* _Robert G. Wilson v_, Jun 17 2018 *)

%o (Python)

%o from sympy import prime, primefactors

%o def a(n):

%o     pn = prime(n)

%o     reach, expand = {pn}, [pn]

%o     while len(expand) > 0:

%o         p = expand.pop()

%o         for q in primefactors(2*p+1):

%o             if q not in reach:

%o                 expand.append(q)

%o                 reach.add(q)

%o     return len(reach)

%o print([a(n) for n in range(1, 101)]) # _Michael S. Branicky_, Jun 29 2022

%Y Cf. A020575, A306035, A316226.

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Jun 17 2018