The Euclid-Mullin graph

[sean]

The Euclid-Mullin sequence EM2 is formed by choosing the smallest prime at each step -- if you need the basic detail look at Wikipedia. One generalization is to start with a different prime, EMp. Here I want to talk about a different extension.

Conjecture (Mullin): EM2 contains every prime.

Instead of the smallest, you could choose the largest. This is A000946 in the OEIS. It does not contain every prime.

Consider the directed graph arising from choosing each possible prime at each possible level. The root node, level 0, is 2. Thereafter, each node corresponds to the product, P, of primes occurring on the edges on the path to the root. The edges leaving a node are the prime factors of the 1+P. I have completely computed this graph to level 11, nearly all of level 12 and partially beyond.

The attached pictures is what the first six levels looks like.

Conjecture: The graph is not a tree.

So far the graph appears to be a tree. This surprises me as I expected that some nodes (especially as the level increases) would have multiple paths to the root. Clearly, all the paths to the root from a given node must be the same length since they differ only in the permutation of primes on the edges.

Conjecture: The graph contains every prime.

If the Mullin conjecture is true, then this conjecture is trivially true. The smallest prime not yet known to occur in the graph is 625543 (cf. 41 for EM2).

The following table is the count of nodes I have at each level. The deepest levels correspond to the factorizations of the usual Euclid-Mullin sequence. Each composite factored will contribute to counts at later levels.

Level   Nodes   Remaining Composites
0       1       0
1       1       0
2       1       0
3       1       0
4       2       0
5       4       0
6       9       0
7       24      0
8       52      0
9       165     0
10      555     0
11      2020    0
12      7946    4
13      32540   141
14      126704  11204
15      449852  49949
16      1219127 301325
17      2756616 710256
18      6034310 1628441
19      4908251 4157630
20      1300793 456952
21      1519479 590663
22      1574118 677178
23      1428618 678039
24      1115872 586929
25      735330  423907
26      405275  254321
27      182684  125015
28      65271   47554
29      18404   14549
30      3689    3110
31      476     432
32      29      21
33      7       4
34      9       2
35      13      6
36      8       6
37      5       1
38      6       3
39      6       2
40      6       3
41      7       2
42      9       4
43      6       4
44      6       1
45      8       5
46      4       2
47      3       1
48      7       2
49      7       4
50      6       2
51      4       4

For those wanting specific numbers to work on, here are the four remaining composites for level 12. They have already been attacked with ECM to the t45 level.

C158 16725286149205799289310225874008636198274795885843971180510821119380611596869679883277768104411059480976832887227092979153756838492627432424241769161906502079
C160 5750341423321392771619665185830820535063917818822438491665001912956307626646884370944616171915151704682007771717048171815538594136569945729293007030136808777327
C190 9851500905967364596308855916938505530179142133407601511344781780757909504954256486134282392664209490003020778251154092274838105492468526237369332200103335236155071892234176717228026625633727
C253 3074163804126375730960046000006410703299860491052515399352204389494565424622768931080605652579832748915879865519993669161314951649593763245464995966627308199534468607184384744257573685683221611440202806222725727083224756010635164700144499225512799343807

[arbooker]

Originally Posted by sean

Conjecture: The graph is not a tree.

Great question! I think it wouldn't be too surprising if it did turn out to be a tree. I'll guess that the average number of digits of the nodes of level n is superpolynomial in n, while the log of the number of nodes is roughly linear in n. So there's a lot of space to put not so many numbers, making future coincidences unlikely if they're not present near the beginning.

I also wonder if there are combinatorial obstructions to loops in the graph. Suppose that there are two paths between nodes n and m with edge primes p_1,...,p_k and q_1,...,q_k. Then from how the primes are chosen we know that if p_i=q_j then the partial products p_1...p_{i-1} and q_1...q_{j-1} are congruent mod p_i and q_j. We can also assume that these products are never equal (otherwise there would be another common node strictly between n and m). Is it even possible for two permutations of a sequence of primes to satisfy all of these congruences? (Playing around with small examples, it's easy to see that k must be at least 4.) Have you tried computing the graph with other small starting values (besides 2)? If there is a small example with a loop, that would at least clear up the combinatorial question.

[arbooker]

Originally Posted by arbooker

Is it even possible for two permutations of a sequence of primes to satisfy all of these congruences?

With some more work, I've found that this is possible for k=4. I expect that there are infinitely many quadruples of edge primes that work, and I found 23 examples up to permutation. From those I derived 44 different arithmetic progressions of node values that are the root of a loop of height 4. The most interesting ones are those where none of the edge primes divide 2*3*7*43, so there is a chance that such a node occurs in the graph rooted at 2. I found six such progressions (the edges are the prime divisors of the modulus):

418499259 or 1226476565 (mod 23*367*401*421)
839663413093108 or 1059078026220785 (mod 11*34739*53353*62011)
181420147843819 or 5261107238001999 (mod 5*30977*31153*1096621)

It seems very likely that the graph will eventually meet one of these arithmetic progressions. In fact, it's reasonable to expect that the nodes corresponding to A000946 will hit each progression with the obvious frequency. So I believe your conjecture now. Unfortunately, these numbers are all rather large (much larger than the number of nodes you have computed), which might explain why you haven't seen any loops so far.

[Dubslow]

Do you have the full graph data somewhere?

One candidate format is an ordered CSV style (each level is a line, and the nodes on each line are ordered the same as they are in your graph, such that EM2 is the left most vertical list of numbers, and A000946 is the right most vertical list). One drawback of this plain text format is that determining a node's parent isn't easy, since the edges themselves aren't stored and you don't know how many children each node has a priori.

What format do you already have it in?

[lorgix]

Originally Posted by sean

C158 16725286149205799289310225874008636198274795885843971180510821119380611596869679883277768104411059480976832887227092979153756838492627432424241769161906502079
C160 5750341423321392771619665185830820535063917818822438491665001912956307626646884370944616171915151704682007771717048171815538594136569945729293007030136808777327
C190 9851500905967364596308855916938505530179142133407601511344781780757909504954256486134282392664209490003020778251154092274838105492468526237369332200103335236155071892234176717228026625633727
C253 3074163804126375730960046000006410703299860491052515399352204389494565424622768931080605652579832748915879865519993669161314951649593763245464995966627308199534468607184384744257573685683221611440202806222725727083224756010635164700144499225512799343807

Anybody wanting to work on c190 should go directly to 26e7 (t60). I've done a t50, working on t55. I'll get back with exact curve counts.

[arbooker]

Originally Posted by arbooker

418499259 or 1226476565 (mod 23*367*401*421)
839663413093108 or 1059078026220785 (mod 11*34739*53353*62011)
181420147843819 or 5261107238001999 (mod 5*30977*31153*1096621)

I overlooked another two pairs of progressions:
1125513 or 1861426 (mod 5*13*73*593)
50128563253 or 539370320206 (mod 41*61*2551*127601)

The first two of these have much smaller modulus, but we have to avoid multiples of 5 and 13. I'm curious how many of your leaf nodes are co-prime to 5*13*73*593. Maybe it would be feasible to push further on only those branches?

[arbooker]

Originally Posted by arbooker

1125513 or 1861426 (mod 5*13*73*593)

I did a further direct search for n-tuples (not just quadruples) of edge primes permitting a loop where the product is small, so as to give relatively dense arithmetic progressions. That search confirmed that 5*13*73*593 is indeed the smallest modulus. The next smallest in terms of expected density is 5*13*17*53*563 (the modulus is over 10 times larger, but it has four progressions instead of two, so it's about 5.5 times less dense). The smallest without a factor of 13 is 5*11*23*31*1307 (17 times less dense), and the smallest without a factor of 5 is 11*19*29*71*1871 (322 times less dense).

So probably the best bet for finding a loop is to hit one of the progressions mod 5*13*73*593, though the answer might be different if the available data is heavily skewed toward multiples of 13. (It would be helpful to know what fraction of leaf nodes are divisible by 13, and how many are co-prime to 5*13*73*593.) Any given co-prime node has about 1 in a million chance of success with that modulus, so it's just a matter of computing enough nodes.

[arbooker]

Originally Posted by sean

Conjecture: The graph is not a tree.

I have proven this conjecture by finding three loops starting at level 27. All of them have height 4, so there are (at least) three nodes at level 31 with multiple paths to the root. (As an aside, I think it would make sense to prepend 1 to the graph and call that level 0; then the level of a node is just its number of prime factors.) There are sure to be examples of lower level, and we should be able to find some with more work.

The smallest example that I found follows these edges:
2, 3, 7, 43, 139, 50207, 1607, 157, 3179891833123363, 134947, 59, 90481, 1753, 365003, 739283, 67, 31, 1627, 1307, 199, 193, 1110839, 5711, 1289, 3121, 137, 49031, 5839.
From there you can follow either 73, 5, 13, 593 or 593, 5, 13, 73 to arrive at the same node.

My general strategy was as outlined in previous posts. Starting from 2*3*7*43*139*50207, I followed paths in the subgraph of nodes relatively prime to 5*13*73*593, looking for the residue classes 1125513 or 1861426. I computed everything up to level 10, and then continued along all the easily accessible branches, using all possible edge primes up to 10^7. The idea is to get lots of nodes quickly rather than being comprehensive.

There are two obvious improvements: 1) Using more complete data from lower levels will boost the number of nodes at all higher levels, so we should fall into the lucky residue classes sooner. 2) The 10^7 can be improved by using ECM to look for factors up to 15 digits, say. That should improve the expansion factor from one level to the next, so again we'll get lucky sooner.

[sean]

Wow, amazing what happens when I don't look for a few days! Congratulations on proving the conjecture. I can see now that it makes sense exploring particular paths, but without your insight about the residues I would never have figured that out.

When I get a chance, I'll certainly add your technique to my code for deciding where to try and expand. I can probably get some counts of nodes wrt to various residues as well.

[arbooker]

Originally Posted by sean

Wow, amazing what happens when I don't look for a few days! Congratulations on proving the conjecture.

Thanks. It must have made for entertaining reading. I started out doubting the conjecture, so I certainly didn't expect to prove it!

Originally Posted by sean

When I get a chance, I'll certainly add your technique to my code for deciding where to try and expand. I can probably get some counts of nodes wrt to various residues as well.

Looking at your node counts, I'm wondering if there isn't already a lucky residue by level 18. Even if not, by systematically applying a low level of ECM to everything, one is sure to turn up within a few more steps.

Here is the output from my search for dense progressions. Each line is of the form q a, indicating that any node congruent to a (mod q) is the start of a loop with edges formed from the prime factors of q. This is the complete list of possible q < 2^32.

2813785 1125513
2813785 1861426
29541655 2913109
29541655 19876614
32972095 45473
32972095 14501753
32972095 15173846
32972095 15665474
51254005 29374824
51254005 37354844
115908845 30432518
115908845 43262953
115908845 74975328
115908845 87805763
155186405 92870549
179491195 106001778
179491195 120823468
179491195 140339224
179491195 145796156
183631045 16718992
183631045 26947777
183631045 40801752
183631045 51030537
241819435 31106978
241819435 108457851
274715155 161397329
274715155 273388114
405125435 26064013
405125435 332551556
451629145 16717776
451629145 363759119
471892265 331562178
471892265 399028904
714350695 171690041
714350695 516232304
782534665 504298018
782534665 599617009
805149301 159790883
805149301 664072158
863399185 132876677
863399185 201396989
1013575615 442565334
1013575615 1006013283
1098605365 687205733
1098605365 858084699
1224215135 629631672
1224215135 710567134
1270054955 167197107
1270054955 611290783
1425018061 418499259
1425018061 1226476565
1573162855 760033971
1573162855 957335761
1770390115 300112643
1770390115 738780074
1770390115 896537609
1770390115 1649815998
1962339665 448494513
1962339665 1892298814
2306397115 576302818
2306397115 1425277064
2306397115 2102564379
2306397115 2205412618
2330561365 593010591
2330561365 737493212
2330561365 1026804278
2330561365 1702036344
2354908595 428971191
2354908595 901967799
2354908595 1624034476
2354908595 2075900299
2616130255 718242222
2616130255 732312684
2616130255 1953487229
2616130255 2582483153
2683051085 181879307
2683051085 861347709
2705569295 719195916
2705569295 1717299964
3548079095 1301483919
3548079095 2589164021
3691452505 1080835434
3691452505 1754193704
3744790465 1129582989
3744790465 3460770598
3768778345 2264199644
3768778345 3034364281
4231397755 59611576
4231397755 338011764
4231397755 851556379
4231397755 1174497596
4231397755 1262219359
4231397755 2098705191
4231397755 3366801736
4231397755 4158746539

[sean]

Originally Posted by Dubslow

Do you have the full graph data somewhere?

One candidate format is an ordered CSV style (each level is a line, and the nodes on each line are ordered the same as they are in your graph, such that EM2 is the left most vertical list of numbers, and A000946 is the right most vertical list). One drawback of this plain text format is that determining a node's parent isn't easy, since the edges themselves aren't stored and you don't know how many children each node has a priori.

What format do you already have it in?

I'm working on getting it uploaded somewhere. Current size is about 700M compressed.
I've just got an in-order traversal text file that only explicitly lists values for the edges.
Thus the first lines do correspond with EM2 and the last line with a given numbers of "."s
corresponds to A000946.

It starts like this (after Andrew's suggestion of starting from 1):

1
.2
..3
...7
....43
.....13

where each "." indicates going down a level. Composites are in parentheses.