A086322 - OEIS

%I #13 Jul 03 2018 02:39:53

%S 2,17,23,167,173,227,233,1667,1733,2267,2273,2333,16673,17327,17333,

%T 22727,23327,23333,173267,173273,227267,233267,233327,1732727,2272667,

%U 2332667,22726667,23326673

%N Primes produced by repeated application of the formula p -> (10p +- 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 10*2-3 = 17 and 10*2+3 = 23. When p=167 there is but one child 10*167-3=1667 because 10*167+3=1673 which is (7 * 239) and therefore not a prime. Essentially a tree of primes is being built which is at best binary:

%C .................|-3=1667 *10

%C .................|........|+3=16673

%C .........|-3=167 *10

%C ..|-3=17 *10

%C ..|......|+3=173 *10

%C ..|..............|..................|-3=173267

%C ..|..............|........|-3=17327 *10

%C ..|..............|........|.........|..........|-3=1732727

%C ..|..............|........|.........|+3=173273 *10

%C ..|..............|+3=1733 *10

%C ..|.......................|+3=17333

%C 2 *10

%C ..|..............|-3=2267

%C ..|......|-3=227 *10

%C ..|......|.......|.........................................|-3=22726667

%C ..|......|.......|.............................|-3=2272667 *10

%C ..|......|.......|..................|-3=227267 *10

%C ..|......|.......|........|-3=22727 *10

%C ..|......|.......|+3=2273 *10

%C ..|+3=23 *10

%C .........|+3=233 *10

%C .................|.............................|-3=2332667 *10

%C .................|.............................|...........|+3=23326673

%C .................|..................|-3=233267 *10

%C .................|........|-3=23327 *10

%C .................|+3=2333 *10

%C ..........................|.........|-3=233327

%C ..........................|+3=23333 *10

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

%C The choice of 2 as the root of this tree, 10 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 only 6p+-5 (see A086321) and 10p+-3 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.

%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) = (10 * a(n-m)) - 3 or (10 * a(n-m)) + 3.

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

%Y Cf. A086319, A086321.

%K fini,full,nonn

%O 1,1

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