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

2, 17, 23, 167, 173, 227, 233, 1667, 1733, 2267, 2273, 2333, 16673, 17327, 17333, 22727, 23327, 23333, 173267, 173273, 227267, 233267, 233327, 1732727, 2272667, 2332667, 22726667, 23326673

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 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 *10

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

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

..|-3=17 *10

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

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

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

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

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

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

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

2 *10

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

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

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

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

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

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

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

..|+3=23 *10

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

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

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

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

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

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

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

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

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.

Links

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

C. Seggelin, Deepest Prime Trees

Formula

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

Mathematica

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]

Crossrefs

Cf. A086319, A086321.

Sequence in context: A343241 A049562 A107137 * A340048 A164275 A284646

Adjacent sequences: A086319 A086320 A086321 * A086323 A086324 A086325

Keyword

fini,full,nonn

Author

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

Status

approved