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

2, 5, 11, 17, 23, 41, 47, 71, 89, 167, 191, 281, 353, 359, 761, 1409, 1433, 1439, 3041, 5639, 12161, 48647, 194591, 778361, 3113447

Offset

1,1

Comments

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.*4......

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

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

..|-3=.5.*4

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

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

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

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

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

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

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

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

2.*4

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

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

..|+3=11.*4

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

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

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

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

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

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

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

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

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

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.

Links

Table of n, a(n) for n=1..25.

C. Seggelin, Deepest Prime Trees.

Formula

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

Mathematica

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]

Crossrefs

Sequence in context: A019381 A113426 A078894 * A220813 A217303 A053033

Adjacent sequences: A086316 A086317 A086318 * A086320 A086321 A086322

Keyword

fini,nonn

Author

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

Extensions

Edited by Robert G. Wilson v, Jul 19 2003

Status

approved