2009-02-13

Numbers that Grow on Trees

Bengt has come up with a whole new kind of number system, which he has decided to call "Dendriux". Each number is expressed as a full binary tree - that is, a tree diagram where each node has either two child nodes or none. It's also binary in a different sense; each node contains either a 1 or a 0.
The numerical value is calculated as follows:
- A node with a 1 has a value which is 1 less than it otherwise would be.
- A (0) node with no children has the value 2.
- A (0) node with children of value n and m has the value of the sum of the nth and the mth prime number (counting 2 as prime number number one).
  1. Some numbers can be written more than one way. Find, for example, all ways of writing 10, 11 and 12.
  2. Suppose that f(x) is the number of ways in which the number x can be written. Find the asymptotic upper bound (the "ordo") for f(x).
  3. (hard) Is it really possible to write all positive integers this way? Prove it.