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 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:

.........|-3=17.x4......

.........|......|......|-3=281.

.........|......|+3=71.x4

..|-3=.5.x4

..|......|.....................|-3=1409.x4

..|......|.....................|........|+3=5639.

..|......|.............|-3=353.x4..

..|......|......|-3=89.x4

..|......|......|......|.......|-3=1433.

..|......|......|......|+3=359.x4

..|......|......|..............|+3=1439.

..|......|+3=23.x4

2.x4

..|......|-3=41.x4

..|......|......|+3=167.

..|+3=11.x4

.........|+3=47.x4

................|........................|-3=12161.x4

................|........................|.........|+3=48647.x4

................|........................|...................|..........|-3=778361.x4

................|........................|...................|..........|..........|+3=3113447.

................|........................|...................|+3=194591.x4

................|...............|-3=3041.x4

................|.......|-3=761.x4

................|+3=191.x4

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

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.

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.

These results can be viewed at the link provided.

C. Seggelin, Deepest Prime Trees.

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

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]

Sequence in context: A019381 A113426 A078894 this_sequence A053033 A115057 A038390

Adjacent sequences: A086316 A086317 A086318 this_sequence A086320 A086321 A086322

fini,nonn

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

Edited by Robert G. Wilson v (rgwv(AT)rgwv.com), Jul 19 2003