20150224, 20:51  #1 
Aug 2004
New Zealand
222_{10} Posts 
The EuclidMullin graph
The EuclidMullin 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 EuclidMullin sequence. Each composite factored will contribute to counts at later levels. Code:
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 Code:
C158 16725286149205799289310225874008636198274795885843971180510821119380611596869679883277768104411059480976832887227092979153756838492627432424241769161906502079 C160 5750341423321392771619665185830820535063917818822438491665001912956307626646884370944616171915151704682007771717048171815538594136569945729293007030136808777327 C190 9851500905967364596308855916938505530179142133407601511344781780757909504954256486134282392664209490003020778251154092274838105492468526237369332200103335236155071892234176717228026625633727 C253 3074163804126375730960046000006410703299860491052515399352204389494565424622768931080605652579832748915879865519993669161314951649593763245464995966627308199534468607184384744257573685683221611440202806222725727083224756010635164700144499225512799343807 
20150225, 14:01  #2 
"Andrew Booker"
Mar 2013
5·17 Posts 
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_{i1} and q_1...q_{j1} 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. 
20150226, 16:52  #3  
"Andrew Booker"
Mar 2013
5·17 Posts 
Quote:
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. Last fiddled with by arbooker on 20150226 at 17:06 

20150226, 18:02  #4 
Basketry That Evening!
"Bunslow the Bold"
Jun 2011
40<A<43 89<O<88
3·29·83 Posts 
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? Last fiddled with by Dubslow on 20150226 at 18:06 
20150226, 20:04  #5  
Sep 2010
Scandinavia
615_{10} Posts 
Quote:


20150226, 21:51  #6  
"Andrew Booker"
Mar 2013
5·17 Posts 
Quote:
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 coprime to 5*13*73*593. Maybe it would be feasible to push further on only those branches? Last fiddled with by arbooker on 20150226 at 22:10 Reason: fixed yet another mistake 

20150227, 13:20  #7 
"Andrew Booker"
Mar 2013
1010101_{2} Posts 
I did a further direct search for ntuples (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 coprime to 5*13*73*593.) Any given coprime node has about 1 in a million chance of success with that modulus, so it's just a matter of computing enough nodes. Last fiddled with by arbooker on 20150227 at 13:32 Reason: corrected densities 
20150227, 22:14  #8 
"Andrew Booker"
Mar 2013
1010101_{2} Posts 
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. 
20150228, 20:11  #9 
Aug 2004
New Zealand
2×3×37 Posts 
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. 
20150301, 00:12  #10  
"Andrew Booker"
Mar 2013
5·17 Posts 
Quote:
Quote:
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. Code:
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 

20150302, 03:34  #11  
Aug 2004
New Zealand
336_{8} Posts 
Quote:
I've just got an inorder 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): Code:
1 .2 ..3 ...7 ....43 .....13 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring 43rd Term of EuclidMullin sequence  grandpascorpion  Factoring  108  20150430 17:51 
Euclid Mullin  henryzz  Factoring  1  20131227 01:37 
second EuclidMullin sequence  arbooker  Factoring  52  20131203 23:00 
Progress Report  Graph?  vaughan  No Prime Left Behind  9  20090717 07:32 
Graph of server assignments  tha  PrimeNet  1  20061214 00:24 