DouglasReay/PrimeDigitFactorTree

I've been up all evening ignoring work I ought to be doing, exploring a sequence:

    4, 6, 8, 9, 24, 32, 42, 48, 64, 84, 243, 324, 432, 672, 896, 42336, ...

I'm not sure if it terminates or not. Here is how it is generated:

1. The first four terms are the numbers 4, 6, 8, 9
2. To be added to the sequence, a positive integer must meet the following criteria:
2.a) It does not contain the digits "0" or "1"
2.b) When its digits are multiplied together, they give a number already in the sequence
2.c) Its prime factors are all single digits (ie 2,3,5,7)

The sequence can be portrayed as a tree structure, where "dead" means there are no
numbers that will have that number as a parent:

4

: dead

: dead

672

: factors = [2, 2, 2, 2, 2, 3, 7]

: dead

243

: dead

324

: dead

432

896

: factors = [2, 2, 2, 2, 2, 2, 2, 7]

42336

: factors = [2, 2, 2, 2, 2, 3, 3, 3, 7, 7]

: dead

: dead

The three I've listed the factors for are ones for which I have not elliminated the possibility that some number exists that can be added to the sequence with that as its parent. (Such a number would, of course, consist of digits that can be constructed from the factor list.)

example: 42336 has the factors [2, 2, 2, 2, 2, 3, 3, 3, 7, 7] so the following are all possibilities that would need to be investigated:

: 2222233377
: 2327232723
: 826977

I notice that a 5 is never going to come up as a factor or a digit, since the resultant parent would have in it either a 0 (forbidden) or a 5 (continuing the chain, which, since there are no valid 2 digit numbers that have 5 as a parent, can't happen). Therefore every number in the series can be identified as the powers of 2, 3 and 7 required to generate it. Eg: "5.3.2" means 2^5 x 3^3 x 7^2

Displaying the tree in this notation gives:
2.0.0

: dead

1.1.0

5.0.0

4.1.0

: dead

2.1.1

5.1.1

: unknown

3.0.0

3.1.0

6.0.0

: dead

0.5.0

: dead

2.4.0

: dead

4.3.0

7.0.1

: unknown

5.3.2

: unknown

1.1.1

: dead

0.2.0

: dead

It would be interesting to plot these nodes as points on a 3D graph (eg showing dead nodes as red, base nodes as green, and intermediate live nodes (ones with at least one child) in yellow, connecting the child-parent links in black. If the trees starting a the 4 unit start points all turn out to be finite, there is still the possibility that there are high numbers which, if used as base nodes, would create additional trees.

: Sunday 24th Feb. I have now had time to look for alternative trees higher up the forest, and found some. I'm pretty convinced that the original tree is indeed finite. The question now becomes, does there exist a base node for such a tree that is not finite? Here are the ones I have found so far:

[1, 1, 0]

[5, 0, 0]

[4, 1, 0]

[2, 1, 1]

: [5, 1, 1]

[3, 0, 0]

[3, 1, 0]

[6, 0, 0]

[0, 5, 0]

[2, 4, 0]

[4, 3, 0]

: [7, 0, 1]
: [5, 3, 2]

[1, 1, 1]

[5, 1, 0]

[7, 1, 0]

: [2, 8, 0]
: [3, 4, 3]

[3, 1, 3]

[4, 1, 1]

[8, 1, 0]

[7, 1, 1]

[10, 3, 0]

[8, 3, 2]

[11, 7, 0]

: [12, 7, 2]

[1, 10, 1]

[10, 7, 0]

[2, 5, 2]

[0, 3, 4]

[6, 3, 2]

[1, 7, 0]

: [2, 5, 3]

[4, 7, 1]

[12, 5, 1]

[13, 8, 2]

: [9, 13, 3]

[4, 14, 3]

[2, 2, 0]

: [0, 0, 2]
: [0, 0, 3]

[3, 2, 0]

: [1, 0, 2]
: [1, 1, 2]

[5, 0, 1]

: [4, 0, 2]
: [3, 0, 3]

[5, 2, 0]

[1, 0, 3]

[1, 3, 2]

[5, 6, 0]

: [6, 8, 1]

[5, 3, 0]

: [5, 1, 3]

[4, 5, 0]

: [5, 4, 4]

[3, 2, 3]

: [2, 4, 4]

[6, 4, 1]

[11, 5, 0]

[10, 6, 0]

: [26, 0, 2]

[0, 9, 2]

[15, 5, 0]

[8, 3, 1]

: [8, 2, 5]

[13, 2, 0]

: [13, 4, 1]

[15, 0, 1]

: [16, 0, 3]

[14, 3, 0]

: [10, 3, 4]
: [2, 3, 7]

[5, 7, 1]

: [14, 0, 4]

[15, 3, 0]

: [4, 10, 4]
: [17, 2, 4]

[14, 4, 1]

: [3, 9, 5]
: [4, 13, 3]

[9, 5, 3]

: [0, 17, 2]

[23, 3, 3]

: [4, 26, 1]

I have proven to my own satisfaction that there are no loops (ie that any number in the sequence will terminate at one of the 4 single digit members in a finite number of steps), and that this holds for whatever base you set the problem up in. (This is because the parent of a 2 or more digit number will always be smaller than the number, because the most significant digit is being multiplied by something that is less than its place value. Eg in the decimal PQQ, each P is worth 100. In the parent, PxQxQ?, each P is worth QxQ? which is, at most, 81.)

Given that the number of possible permutations will go up on the order of a factorial of how many factors a number has, I'd expect at some point the tree to start branching out rapidly. Can anyone draw more of it and prove or disprove this conjecture or shed light on the mathematics behind it?

Looking at the density of numbers formable by multiplying powers of 2,3 and 7 in the ranges 1000-10000, 10000-100000, 100000-1000000, etc I'm guessing that since log(2) : log(3) : log(7) is roughly the ratio 3:5:8 so 2^40 (1x10^12) =~ 3^25 (0.8x10^12) =~ 7^15 (4.7x10^12), the density curve is roughly analogous to how the number of ways you can construct a bridge of length of 120, 240 or 360 meters increases as the bridge increases in length, if you have to construct it from a combination of sections that are either 3m, 5m or 8m in length (Fibbonacci like, isn't that?)

On the other hand, the more digits you have in a number, the more likely it is that one of them will be a 0, 1 or 5 (if those are distributed more or less evenly). In which case, the question becomes, for any particular finite size (eg 25), will at least one tree of that size exist? Are there an infinite number of trees of size 3 or more? Does the answer change if we look at height of tree (the length of the longest chain of parent-child links), rather than size (the number of nodes with the base node in their ancestry, including the base node itself)?

The highest number I have found is 733283388672788498743296 (which is 2^45 x 3^11 x 7^6), having searched the space up to (2^80 x 3^50 x 7^30). I'm therefore tempted to predict that the largest tree existing is: