It's been a long time since I was able to report the discovery of a D22 prime tree. I only know of 2 others. The first was found on 2/24/2004 and the second on 4/21/2004. So as you can see it's been nearly 7 months. The other interesting thing is that ShareCal didn't find this tree--I found it on my own. ShareCal is currently checking root primes in the vicinity of 2.9 million. When ShareCal reaches the root prime of this tree (vicinity of 3.3 million) it will find it. However it was ShareCal's output data which gave me the leads that led to this tree...

Brief Recap: What's a Prime Tree?

Skip this section if you already know what a prime tree is. A prime tree is a family of primes produced by repeated applications of the same formula starting from a given root prime. For example, if the formula were 5p +/- 4 starting at root prime 3, the resulting tree would look like this: 

5p+/-4 at 3 (D3, P4):

  [3]
   - = [11]
   .   + = [59]
   + = [19]

Here's how it got built:

  1. Let p = the root prime. (3)
  2. Let A = 5p - 4. (5x3 - 4 = 11).
  3. Let B = 5p + 4. (5x3 + 4 = 19).
  4. Is A (11) prime? YES. Add it to the tree.
  5. Is B (19) prime? YES. Add it to the tree.
    We've added two primes to the tree (11 and 19), so we need to check them both.
  6. Let p = A. (11)
  7. Let C = 5p - 4. (5x11 - 4 = 51).
  8. Let D = 5p + 4. (5x11 + 4 = 59).
  9. Is C (51) prime? NO. (51 = 3 x 17). Skip it.
  10. Is D (59) prime? YES. Add it to the tree.
  11. Let p = B. (19)
  12. Let E = 5p - 4. (5x19 - 4 = 91).
  13. Let F = 5p + 4. (5x19 + 4 = 99).
  14. Is E (91) prime? NO. (91 = 7 x 13). Skip it.
  15. Is F (99) prime? NO. (99 = 9 x 11). Skip it.
  16. The only prime in the tree we haven't checked yet is D (59), so Let p = D.
  17. Let G = 5p - 4. (5x59 - 4 = 291).
  18. Let H = 5p + 4. (5x59 + 4 = 299).
  19. Is G (291) prime? NO. (291 = 3 x 97). Skip it.
  20. Is H (299) prime? NO. (299 = 13 x 23). Skip it.
    We've detemined that no further primes are generated by this tree. It has a depth of 3 generations, and a population of 4 primes.

The characteristics of this tree are as follows:

  • The coefficient (c) is 5 -- the thing we multiplied by.
  • The offset (b) is 4 -- the thing we added and subtracted after multiplying.
  • The root (r) is 3 -- the first prime in the tree. (Sometimes called the starting prime.)
  • The depth (D) is 3 -- the maximum number of generations in the tree. (In this case 3 begat 11 begat 59, that's three generations.)
  • The population (P) is 4 -- the total number of primes appearing in the tree. (In this case 3, 11, 59, and 19, that's four primes.)

Of these the latter two are determined by the first three. If a tree has a depth of 10 or more, and/or a population of 18 or more, I call it "big". If it has a depth of 16 or more, and/or a population of 30 or more, I call it a "monster". The deepest tree I've found to date is 22 generations deep. The most populous (widest) tree I've found to date had a population of 71 primes. I am trying to break the record for depth. In other words I am seeking a tree with a depth of 23 or more. I've been at it for over a year now.

It is possible to make the offset so large, that the first prime computed is smaller than the root. (For example 2p+/-15 at 13. 2x13=26 - 15 = 11. 11 < 13.) Because the primes in such trees tend to grow smaller for awhile before they grow bigger, I call such trees "inverted". Inverted trees tend to grow the biggest, and so this is the type of prime tree I am exploring right now.

You can find a more detailed explanation of prime trees here.

The New D22 Tree

The new D22 tree is a real whopper. The other two D22 trees (2p +/- 560,415 at 384,187 and 2p +/- 2,258,025 at 1,867,823) both had populations of 29 primes. The new tree weighs in at 41 primes! Here's what the new monster tree looks like:

2p +/- 4,849,845 at 3,337,421 (D22, P41):

 [3337421]
   - = [1824997]
       + = [8499839]
           - = [12149833]
           .   - = [19449821]
           .   + = [29149511]
           .       + = [63148867]
           + = [21849523]
               - = [38849201]
               .   - = [72848557]
               .   + = [82548247]
               .       + = [169946339]
               .           - = [335042833]
               .           .   - = [665235821]
               .           .   .   - = [1325621797]
               .           .   .   .   + = [2656093439]
               .           .   .   .       + = [5317036723]
               .           .   .   .           + = [10638923291]
               .           .   .   .               - = [21272996737]
               .           .   .   .               + = [21282696427]
               .           .   .   .                   - = [42560543009]
               .           .   .   .                   .   - = [85116236173]
               .           .   .   .                   .       - = [170227622501]
               .           .   .   .                   .           - = [340450395157]
               .           .   .   .                   .           .   + = [680905640159]
               .           .   .   .                   .           .       - = [1361806430473]
               .           .   .   .                   .           .           + = [2723617710791]
               .           .   .   .                   .           .               + = [5447240271427]
               .           .   .   .                   .           + = [340460094847]
               .           .   .   .                   + = [42570242699]
               .           .   .   .                       - = [85135635553]
               .           .   .   .                           - = [170266421261]
               .           .   .   .                               + = [340537692367]
               .           .   .   + = [1335321487]
               .           .   + = [674935511]
               .           + = [344742523]
               + = [48548891]
                   - = [92247937]
                   + = [101947627]
                       + = [208745099]
                           - = [412640353]

Productive Offsets

As I said, it was ShareCal's output data that gave me the idea that led to this tree. I was studying the characteristics of the first 4,800 monster trees and looking for patterns.

There didn't appear to be any interesting pattern of the root primes. They either work or they don't and I've found none that produce more than 2 monsters for coefficients of 2, 3, or 4.

The coefficients were slightly more interesting. Smaller coefficients tend to be more productive. I learned this early on, and that is why ShareCal currently only tests coefficients 2, 3, and 4. (Out of 4,862 monsters 2,459 have c=2, 1,980 have c=3, and only 423 have c=4.) It may be that primality has something to do with it too (both 2 and 3 are prime, but 4 is not) but I haven't done enough experimentation with

That leaves the offsets, and it turns out there is an interesting pattern to them... some offsets show up more than others. For example the offset 1,726,725 shows up more than any other offset in the list of monster trees, appearing 13 times. So I asked myself, what is so special about this offset? It turns out that the prime factorization of the offset is interesting, and also appears to be directly related to the coefficient used in the prime tree formula. In fact the same offset has never reappeared twice with a different coefficient in the monster tree list. Here's a table of the top 10 offsets which should make clear what I noticed:

Offset Occurances Coefficient Factorized
1726725 13 2 3 x 5^2 x 7 x 11 x 13 x 23
255255 12 2 3 x 5 x 7 x 11 x 13 x 17
285285 10 2 3 x 5 x 7 x 11 x 13 x 19
3465 9 2 3^2 x 5 x 7 x 11
373065 9 2 3 x 5 x 7 x 11 x 17 x 19
2297295 9 2 3^3 x 5 x 7 x 11 x 13 x 17
451605 7 2 3 x 5 x 7 x 11 x 17 x 23
465465 7 2 3 x 5 x 7 x 11 x 13 x 31
1740970 7 3 2 x 5 x 7^2 x 11 x 17 x 19
3318315 7 2 3 x 5 x 7 x 11 x 13^2 x 17


Notice anything interesting about the factorizations? I sure did. They all seem to include a nearly contiguous series of the first few primes. 255,255 for example is 3 x 5 x 7 x 11 x 13 x 17, that's the first six primes after 2. Notice how they all exclude 2 except for one? One of them includes 2 but excludes 3... and that also happens to be the one which occurs when the coefficient is 3. :-) The excluded early prime appears to be the coefficient. They all seem to include 5 x 7 x 11 and then after that a prime may be skipped here and there. The other interesting thing is that all of them except for one appear to have six prime factors. Curious, no?

 But it is also exciting, because it means if I generate offsets that follow this general pattern, I may be able to find what I am looking for that much more quickly. Instead of checking hundreds of thousands of offsets for a given root, maybe I only need to check 30 or so?

Just as an experiment, I decided to multiply the first 7 prime factors after 2 together (3 x 5 x 7 x 11 x 13 x 17 x 19 = 4,849,845) and try that with a coefficient of 2. I tested all root primes between 2 and 3,360,000 and was delighted to discover (in addition to the new D22 tree, that this offset generated 22 different monsters:

  1. 2p +/- 4849845 at 239333 (D16, P19)
  2. 2p +/- 4849845 at 323579 (D17, P27)
  3. 2p +/- 4849845 at 624097 (D16, P27)
  4. 2p +/- 4849845 at 681047 (D17, P26)
  5. 2p +/- 4849845 at 924731 (D16, P24)
  6. 2p +/- 4849845 at 1128697 (D16, P27)
  7. 2p +/- 4849845 at 1458907 (D13, P32)
  8. 2p +/- 4849845 at 1712861 (D16, P23)
  9. 2p +/- 4849845 at 1819343 (D17, P26)
  10. 2p +/- 4849845 at 1824997 (D21, P40)
  11. 2p +/- 4849845 at 1916909 (D12, P30)
  12. 2p +/- 4849845 at 2022487 (D19, P28)
  13. 2p +/- 4849845 at 2197873 (D17, P21)
  14. 2p +/- 4849845 at 2313197 (D19, P22)
  15. 2p +/- 4849845 at 2451277 (D11, P31)
  16. 2p +/- 4849845 at 2609657 (D16, P21)
  17. 2p +/- 4849845 at 2664241 (D12, P35)
  18. 2p +/- 4849845 at 2989271 (D17, P28)
  19. 2p +/- 4849845 at 3139447 (D11, P30)
  20. 2p +/- 4849845 at 3164827 (D16, P28)
  21. 2p +/- 4849845 at 3295559 (D11, P32)
  22. 2p +/- 4849845 at 3337421 (D22, P41)

Of course I'd be concerned that there would be an offset that kicks out a D23 tree that doesn't share the characteristics that these others do. For example, the offset 9,165,525 appears in the monster tree 4p +/- 9,165,525 at 2,710,373 (D16, P20), but the factorization of 9,165,525 is 3 x 5^2 x 122,207. So for now I'm going to leave ShareCal as it is, but clearly there is a pattern to the most productive offsets, so I have put together some Maple 6 worksheets to experiment with likely offsets. Further exploration in this area may yield the D23 tree I have sought for so long.

Wish me luck!