login
Number of distinct values in the prime tree starting with n.
2

%I #18 Jul 30 2020 07:17:46

%S 35,35,34,22,12,11,5,7,10,5,10,10,6,6,7,7,4,3,5,13,14,6,1,5,5,3,4,3,2,

%T 2,4,3,2,2,3,3,1,4,6,3,3,3,1,3,7,6,2,2,2,6,6,1,6,9,5,5,5,2,4,5,2,2,2,

%U 7,8,7,6,2,3,4,5,3,1,1,4,5,4,4

%N Number of distinct values in the prime tree starting with n.

%C Starting from n construct a tree that includes nodes for each prime in n^2 + n + 1, n^2 + n - 1, n^2 - n + 1, n^2 - n - 1, and recurse on each node until no further primes can be included.

%H Robert Israel, <a href="/A291654/b291654.txt">Table of n, a(n) for n = 1..10000</a>

%H Ralf Steiner, <a href="https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;d5ff2a3a.1708">Prime-trees</a>, NMBRTHRY posting, 13 Aug 2017.

%e a(5) = 12 since the tree for 5 looks like this where, for example, the symbol -[+-]-> stands for p^2+p-1 and the symbol -| stands for a leaf:

%e 5-[--]->19-[+-]->379-[--]->143261-|

%e -[-+]->143263-[-+]->20524143907-|

%e -[+-]->29-[--]->811-|

%e -[++]->31-[--]->929-|

%e -[+-]->991-[-+]->981091-|

%p f:= proc(n) local R, agenda;

%p agenda:= {n}; R:= {n};

%p while nops(agenda) > 0 do

%p agenda:= select(isprime, map(t -> (t^2+t+1,t^2+t-1,t^2-t+1,t^2-t-1), agenda) minus R) ;

%p R:= R union agenda;

%p od;

%p nops(R);

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Aug 29 2017

%t f[n_] := Module[{R = {n}, agenda = {n}}, While[Length[agenda] > 0, agenda = Select[Flatten[Map[Function[t, {t^2 + t + 1, t^2 + t - 1, t^2 - t + 1, t^2 - t - 1}], agenda]] ~Complement~ R, PrimeQ]; R = Union[R, agenda]]; Length[R]];

%t Array[f, 100] (* _Jean-François Alcover_, Jul 30 2020, after _Robert Israel_ *)

%K nonn

%O 1,1

%A _Ralf Steiner_ and _Sean A. Irvine_, Aug 28 2017