More on Leroy Quets prime trees.

This is more a topic for rec.puzzles than sci.math, but there is a touch of genuine math in it, near the end, so I post here as well.

Leroy asks about 'prime trees', that is, full binary trees labelled from 1 to (2^n - 1), such that every branch sums to a prime number.

Obviously there is only one 2 4 1 with n = 2, and there are / / / six with n = 3, unless I made 1 3 2 6 4 7 a mistake in my manual searches. 1 5 3 7 2 6 3 5

In fact, for these small numbers it is not hard to find examples, though counting the actual number of distinct ones seems to be merely a boring search.

So we might consider placing further restrictions on the trees. It is not hard to see that there is always a good chance of finding a tree with the 'standard pattern' in parity, which I will call 'homogeneous'. That is, every level has uniform parity, which in turn means that all the internal nodes are even, and the leaves odd. The lone 3-tree is of this type, as is the first of the 7-trees shown above. In fact four of the six 7-trees are homogeneous, and only two heterogeneous, including the second one shown. My bet is that there are always a lot fewer heterogeneous ones, and these could make for an interesting search. There is only one feasible heterogeneous parity pattern for 7-trees, so both examples are of this type. (The other is obtained by exchanging 1 & 7.)

Another intriguing restriction is to require that the trees be 'univalent', that is, have a different prime total down every branch. The middle tree above is of this type, with totals of 7, 11, 13, 17. It is the only univalent 7-tree, (modulo my mistakes). So there are NO univalent heterogeneous 7-trees!

For 15-trees, there are apparently six feasible parity-patterns, and, of course, a great many example trees. I haven't checked that there is at least one for each of the six patterns, (exercise for the reader), but I guess there is, as it is fairly easy to construct examples. Of more interest is whether there is any UNIVALENT HETEROGENEOUS 15-tree. After a lengthy manual search I finally found one, but I won't spoil your fun by printing it here. Indeed, I would encourage others to look for them and post them here, and we may find more than one. As a teaser, I mention that my example has thirteen as the root; so if you find some other root you will know it is new to the world!

Finally, Leroy wonders whether there may be prime trees of all heights.

Though for small heights they seem easy to construct, suggesting that there may be increasingly many of each height, I strongly suspect that this may be yet another example of the law of small numbers. Indeed, there is another puzzle of this type that I plan to print sometime, (also followupping someone else's post, of several months ago), wherein there are increasingly many examples of a prime-based thingy, until at suitably high levels they start to dry up rapidly and suddenly run out! I suspect it may be so here, as well.

In that other case the heuristics were fairly easy to establish, and the examples followed these 'predictions' (hello Mike!) closely. In this tree problem, though, the heuristics are fairly hideous and necessarily grossly crude, and I have also run out of steam for the moment; so I will leave it to the prime number experts to consider the matter and see if they agree with my suspicion.

A fun problem, Leroy. Thanks for listening, all!

|> course, a great many example trees. I haven't checked that there is at |> least one for each of the six patterns, (exercise for the reader), but |> I guess there is, as it is fairly easy to construct examples.

Yes there is at least one of each type, I just checked. It's not hard.

There is another special type that might be fun to search for, and will be rather easier to program a machine search for, thus maybe giving us some clue on the matter of whether there are infinitely many overall, or just (as I suspect) finitely many.

We can also look for 'sequential prime trees'. These are as before, but with the further property that all the levels above the bottom have the integers in sequential order from 1 onwards. It's easy to check there are none with 2 or 3 levels; and the 4-levellers only *just* miss out too. The nearest miss is: 1 / 2 3 / / 4 5 6 7 / / / / 10 12 11 15 9 13 8 14

totals: 17 19 19 23 19 23 19 25 <

Very interesting. My intuition is that sequential prime trees should exist for almost every number of levels. A sequential prime tree of k levels is equivalent to a matching in a particular bipartite graph on 2 x 2^(k-1) vertices (the labels from 2^(k-1) to 2^k - 1 on one side, and their valid positions on the tree on the other side). The average degree of this bipartite graph is ~ 2^k/k.

Now, I believe the threshold for perfect matching in a *random* bipartite on n vertices is p >> log n/n, for a degree of only log n = k. Our graph exceeds this threshold by quite a significant margin! So my expectation is that prime trees get easier and easier to find as the number of levels increases, but to prove this seems to require number-theoretic bounds on primes in certain dense subset sums.

For instance, it would imply that for any m, 2^k - 1 <= m < 3*2^(k-1), there exists a (possibly empty) subset of {1, 3, 7, ..., 2^(k-2)-1} that sums to p-m for some prime p. I don't see a good way to approach this problem.