[numerology] yet more primes

[Chuck Seggelin]

> > %N A006254 2n-1 is prime.
> > %N A024912 10n+1 is prime.
> > %N A033868 7n-11 is a prime.
> > %N A067076 2n+3 is a prime.
> > %N A081759 5n+6 is a prime.
> > %N A086303 n+15 is prime.
> > %N A086304 n+6 is prime.
> > %N A086801 n+3 is a prime.
> > %N A088879 3n+5 is a prime.
> > %N A088958 n such that 60*n+1 is prime.
> > %N A089038 2n+5 is prime.
> > %N A089559 2n+15 is prime.
>
>     Those seem to be the rage, nowadays. Let me join the fun:
>
> %I A123456
> %S A123456 2,3,5,7,11,13,17,19,23,29,31
> %N A123456 840n+175177943 is a prime.
> %K A123456 nonn,dumb,joke,less
> %A A123456 A. Nonymous (i.wish(AT)nowhere.org)
>
>     (Those who extend the sequence will be unsurprisingly disappointed.)
> --
> Don Reble       djr at nk.ca

Dear seqfans,

Let me preface this by warning the reader that I am a complete amateur, so
although it is interesting to me, this message may seem pretty boneheaded to
you pros.  I apologize in advance, but consider this fair warning! :)

Awhile back I did some analysis based on simple expressions like the ones
listed above to generate primes.  I wanted to find out if certain simple
coefficient*prime +/- offset formulas would more reliably generate primes
than others (beyond the obvious differences between those that generate even
numbers and those that generate odd numbers).  My reasons for looking at
this is I thought it would be useful for generating large primes.  If, for
example 6p+/-5 is a reliable source of primes, then maybe 6*(large prime)+5
or 6*(large prime)-5 might produce an even larger prime.

I performed this analysis for all coefficients from 2 to 32, all offsets
from 1 to 31, and using the first 1000 primes as starting points.  I never
let the offset be greater than the coefficient because that seemed like
repeating work (6n-7 = 6(n-1)+5).  My results indicated that though there
were coefficient and offset pairings that produced larger numbers of primes
than any other, the differences appeared to be not very significant.  For
example the #1 generator of primes in my test was 21p+/-20, which generated
800 primes.  The #32 generator of primes was 30p+/-1 coming in at 642
primes.  Some difference, but each generator was only a few primes ahead of
the previous one and a few primes behind the next.  There were no large
jumps.

Then I started to wonder if particular pairings of coefficients and offsets
were more likely to produce chains of primes (i.e. 6n+5 = prime i, 6i+5 =
prime j, 6j+5 = prime k, etc.)

When doing this analysis I imagined a data structure which I called a prime
tree.  The root node of the tree held the starting prime, and each node of
the tree had 0, 1, or 2 children.  If N is the value of a node, C the value
of the coefficient, and F the value of the offset, then the potential
children of N are C*N-F and C*N+F.  Candidates are tested for primality and
added to the tree only if they are prime.  The process continues for each
child until no new nodes are added to the tree.  For example, here is the
prime tree generated by 3p+/-2 starting at 5:

+-------------------------------------------
|  [5]
|    - = [13]
|    .   - = [37]
|    .   .   - = [109]
|    .   .   + = [113]
|    .   .       - = [337]
|    .   .           - = [1009]
|    .   .           + = [1013]
|    .   .               - = [3037]
|    .   .               .   - = [9109]
|    .   .               .       + = [27329]
|    .   .               + = [3041]
|    .   + = [41]
|    + = [17]
|        + = [53]
|            - = [157]
+-------------------------------------------

The minuses indicate children created by subtracting the offset, and the
pluses indicate children created by adding the offset.  This particular tree
is 9 generations deep and has a population of 16 nodes.

I then repeated the analysis for C=2..32, F=1..31, and N=first 1000 primes.
This time there were clear winners and losers.  15p produced an average of
1444 primes in prime trees across offsets 1 to 31.  6p's average was 1440.
The third place was held by 21p at 1293.  Individually, the most generative
pairing was 6p+/-5 at 1761 primes produced.  One of the least generative was
31p+/-8 which produced only 273 primes.

Along the way I started to take an interest in the prime trees themselves.
Which one was the deepest?  Which one was the most populous?  At the
conclusion of this analysis the deepest tree found was 4p+/-3 starting at 2,
with a depth of 11 generations and a population of 25 nodes.  The most
populous tree was a tie between 6p+/-5 and 10p+/-3 both starting at 2 and
having 28 nodes, the former in 7 generations and the latter in 8.

Since then, as computer time becomes available, I have been slowly expanding
this analysis to find bigger trees.  At the present time I have tested all
coefficients up to 898 for all primes from 2 to 10009 (the first 1231
primes).  I have found several trees deeper than 4p+/-3 at 2, but none
anywhere near as populous as 6p+/-5 at 2 and 10p+/-3 at 2.  The deepest tree
found so far was 50p+/-27 at 1879:

+--------------------------------------------------------------------------
|[1879]
|- = [93923]
|    + = [4696177]
|        - = [234808823]
|            - = [11740441123]
|                + = [587022056177]
|                    - = [29351102808823]
|                        + = [1467555140441177]
|                            - = [73377757022058823]
|                                + = [3668887851102941177]
|                                    - = [183444392555147058823]
|                                    .   - = [9172219627757352941123]
|                                    .       + = [458610981387867647056177]
|                                    + = [183444392555147058877]
+--------------------------------------------------------------------------

This tree is 13 generations deep and has a population of 14 nodes.

My understanding is that primes tend to become less densely packed as
numbers grow larger, so I suspect that I may never find a more populous tree
than the current record holders, but I wonder about deeper trees.  Might
there be a tree out there with a depth of 20 generations?  I'm pushing my
analysis out to coefficients up to 1000, and then I may try pushing the
starting primes further out beyond 10009 but the process is very slow.  I
run it in the evenings using Maple on a machine at work, set up to e-mail me
when prime trees with more than 24 nodes or 9 generations are found.  Since
the computations are recursive, Maple's sub-par memory management tends to
slow the operations down very quickly.

I'd be curious in knowing what serious mathematicians think the likelihood
is that there might be a prime tree more populous than 28 nodes.

Anyway, I suppose all this isn't very interesting, but perhaps you can take
some solace in that it doesn't appear to resolve into any sort of
prime-silliness sequence to include in the OEIS.  Well almost.  The record
holder prime trees for C=2..32 were added to the OEIS as finite sequences
(A086319, A086321, A086322) and one additional sequence was added for a(n) =
prime tree depth of the n'th prime as the root of a 4p+/-3 tree (A086320).

   -- Chuck

PS: Here's 6p+/-5 at 2:

+------------------------------------
|  [2]
|    - = [7]
|    .   - = [37]
|    .   .   + = [227]
|    .   .       + = [1367]
|    .   + = [47]
|    .       - = [277]
|    .           - = [1657]
|    .           + = [1667]
|    .               + = [10007]
|    .                   - = [60037]
|    + = [17]
|        - = [97]
|        .   - = [577]
|        .   .   - = [3457]
|        .   .   .   + = [20747]
|        .   .   .       - = [124477]
|        .   .   + = [3467]
|        .   .       + = [20807]
|        .   .           + = [124847]
|        .   + = [587]
|        .       - = [3517]
|        .       .   + = [21107]
|        .       + = [3527]
|        .           - = [21157]
|        + = [107]
|            + = [647]
|                - = [3877]
+------------------------------------