1,1

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:

.................|-3=1667 x10

.................|........|+3=16673

.........|-3=167 x10

..|-3=17 x10

..|......|+3=173 x10

..|..............|..................|-3=173267

..|..............|........|-3=17327 x10

..|..............|........|.........|..........|-3=1732727

..|..............|........|.........|+3=173273 x10

..|..............|+3=1733 x10

..|.......................|+3=17333

2 x10

..|..............|-3=2267

..|......|-3=227 x10

..|......|.......|.........................................|-3=22726667

..|......|.......|.............................|-3=2272667 x10

..|......|.......|..................|-3=227267 x10

..|......|.......|........|-3=22727 x10

..|......|.......|+3=2273 x10

..|+3=23 x10

.........|+3=233 x10

.................|.............................|-3=2332667 x10

.................|.............................|...........|+3=23326673

.................|..................|-3=233267 x10

.................|........|-3=23327 x10

.................|+3=2333 x10

..........................|.........|-3=233327

..........................|+3=23333 x10

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

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.

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.

C. Seggelin, Deepest Prime Trees

a(n) = (10 * a(n-m))-3 or (10 * a(n-m))+3

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]

Cf. A086319, A086321.

Sequence in context: A105901 A049562 A107137 this_sequence A018759 A132146 A139827

Adjacent sequences: A086319 A086320 A086321 this_sequence A086323 A086324 A086325

fini,nonn

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