A086319 - OEIS

%I #10 Jul 03 2018 02:39:31

%S 2,5,11,17,23,41,47,71,89,167,191,281,353,359,761,1409,1433,1439,3041,

%T 5639,12161,48647,194591,778361,3113447

%N Primes produced by repeated application of the formula p -> (4p +- 3) starting at the prime 2.

%C Since the formula is being applied twice (once with -3 and once with +3) to each prime generated, each prime may have at most two "children". So if p=2, then its children are 4*2-3 = 5 and 4*2+3 = 11. When p=23 there is but one child 4*23-3=89 because 4*23+3=95 and 95 clearly is not a prime. Essentially a tree of primes is being built which is at best binary:

%C .........|-3=17.*4......

%C .........|......|......|-3=281.

%C .........|......|+3=71.*4

%C ..|-3=.5.*4

%C ..|......|.....................|-3=1409.*4

%C ..|......|.....................|........|+3=5639.

%C ..|......|.............|-3=353.*4..

%C ..|......|......|-3=89.*4

%C ..|......|......|......|.......|-3=1433.

%C ..|......|......|......|+3=359.*4

%C ..|......|......|..............|+3=1439.

%C ..|......|+3=23.*4

%C 2.*4

%C ..|......|-3=41.*4

%C ..|......|......|+3=167.

%C ..|+3=11.*4

%C .........|+3=47.*4

%C ................|........................|-3=12161.*4

%C ................|........................|.........|+3=48647.*4

%C ................|........................|...................|..........|-3=778361.*4

%C ................|........................|...................|..........|..........|+3=3113447.

%C ................|........................|...................|+3=194591.*4

%C ................|...............|-3=3041.*4

%C ................|.......|-3=761.*4

%C ................|+3=191.*4

%C The 4p+-3 tree for the root prime 2 is 11 generations deep and has a population of 25 nodes (including 2 itself).

%C The choice of 2 as the root of this tree, 4 as the coefficient and 3 as the +-offset are not arbitrary. Performing this analysis for the first 1,000 primes for all combinations of coefficient (2 to 32) and offset (1 to 31) demonstrates that the deepest tree formed is the one shown here, at 11 generations. 25p+-6 produces a 10-generation tree when p=809, 3p+-2 yields a 9-generation tree when p=5, 6p+-5 also is 9 generations when p=269 and so forth.

%C Note that the most populous tree formed need not be the deepest, since a single generation can produce 1 or 2 children for each parent. The most populous tree is a tie between 6p+-5 and 10p+-3 which both produce trees with a population of 28 nodes when p=2.

%C These results can be viewed at the link provided.

%H C. Seggelin, <a href="https://web.archive.org/web/20040621084312/http://www.plastereddragon.com:80/maths/DeepestPrimeTree_1000.txt">Deepest Prime Trees</a>.

%F a(n) = (4 * a(n-m)) - 3 or (4 * a(n-m)) + 3.

%t a[1] = {2}; a[n_] := Union[ Join[ a[n - 1], Select[ Flatten[{4*a[n - 1] - 3, 4*a[n - 1] + 3}], PrimeQ[ # ] &]]]; a[11]

%K fini,nonn

%O 1,1

%A Chuck Seggelin (barkeep(AT)plastereddragon.com), Jul 16 2003

%E Edited by _Robert G. Wilson v_, Jul 19 2003