A086321 - OEIS

%I #11 Jul 03 2018 02:39:40

%S 2,7,17,37,47,97,107,227,277,577,587,647,1367,1657,1667,3457,3467,

%T 3517,3527,3877,10007,20747,20807,21107,21157,60037,124477,124847

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

%C Since the formula is being applied twice (once with -5 and once with +5) to each prime generated, each prime may have at most two "children". So if p=2, then its children are 6*2-5 = 7 and 6*2+5 = 17. When p=37 there is but one child 6*37+5=227 because 6*37-5=217 which is (7 * 31) and therefore not a prime. Essentially a tree of primes is being built which is at best binary:

%C ..........|-5=37 *6

%C ..........|......|+5=227 *6

%C ..........|..............|+5=1367

%C ...|-5= 7 *6

%C ...|......|..............|-5=1657

%C ...|......|......|-5=277 *6

%C ...|......|......|.......|+5=1667 *6

%C ...|......|......|................|.........|-5=60037

%C ...|......|......|................|+5=10007 *6

%C ...|......|+5=47 *6

%C 2 *6

%C ...|.....................|-5=3457 *6

%C ...|.....................|........|.........|-5=124477

%C ...|.....................|........|+5=20747 *6

%C ...|.............|-5=577 *6

%C ...|.............|.......|+5=3467 *6

%C ...|.............|................|+5=20807 *6

%C ...|.............|..........................|+5=124847

%C ...|......|-5=97 *6

%C ...|......|......|.......|-5=3517 *6

%C ...|......|......|.......|........|+5=21107

%C ...|......|......|+5=587 *6

%C ...|......|..............|........|-5=21157

%C ...|......|..............|-5=3527 *6

%C ...|+5=17 *6

%C ..........|+5=107 *6

%C ..................|.......|-5=3877

%C ..................|+5=647 *6

%C The 6p+-5 tree for the root prime 2 is 7 generations deep and has a population of 28 nodes (including 2 itself).

%C The choice of 2 as the root of this tree, 6 as the coefficient and 5 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 only 6p+-5 and 10p+-3 (see A086322) ever produce a tree with this many nodes on it. All other prime trees are smaller. 4p+-3 produces a 25-node tree when p=2, 12p+-5 produces a 22-node tree when p=2, and 28p+-15 and 30p+-7 produce 21-node trees when p=953 and 13, respectively.

%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 deepest tree is 4p+-3 which is 11 generations deep when p=2. 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) = (6 * a(n-m)) - 5 or (6 * a(n-m)) + 5.

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

%Y Cf. A086319, A086322.

%K fini,full,nonn

%O 1,1

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