Gadget wrote:
Here are a couple of (potential) problems that I see with your proof/graph:
1) How do you determine when a number cannot be a multiple of 15 and know when to mark an edge in yellow?
I work backwards. Going from a lower level (n_i) to a higher level (n_(i+1)), where n_(i+1) = 2*n_i (n_(i+1) is even) or n_(i+1) = 2*n_i + 1 (n_(i+1) is odd).
Take the yellow path on the right side. It starts out with 0, so the next higher level can be 0 or 1; since 1 is the only one on the path, it must be next. For 1, the next higher level can be 2 or 3; since 2 is the only one on the path, it must be next. This continues on with 2, 4, 8, 17, and ends with 35, which is not a multiple of 15.
Gadget wrote:
2) As this is a visual representation of the decimal to binary conversion algorithm, path should terminate at a 0 (or 1 if you're saving space); However, as you've stated in your write up, you terminate several of them early.
I did that on the paths that have already encountered 4 1 bits to save on space.
Gadget wrote:
3) Can you prove there are only two outgoing edges for each node in the graph? Although I came to the same result separately using a script, there is no obvious reason to believe this should be the case (eg 10/2 = 5, 12/2 = 6, 14/2 = 7).
Yes.
When a number is divided by two, (a) the ones digit is either less than, or (b) greater than or equal to its ones digit. (b) is the result of n_i * 2 producing a rollover, while (a) results from no rollover of n_i * 2.
Example with 6 as the ones digit. A case of (a) is 26 / 2 = 13; 13 * 2 does not produce a rollover. A case of (b) is 16 / 2 = 8; 8 * 2 produces a rollover.
I realize this isn't the greatest explanation, but hopefully it gives you some insight. Additionally, since we are only concerned with the ones digit, there is a finite number of possibilities (a small one at that), so it can be shown by iterating through all the possibilities that there are only two outgoing edges.
Gadget wrote:
Let's take the tree that you posted (quite nice BTW), remove the redundant nodes, and turn it into a weighted directed graph (note: I removed the edge weights from my graph to reduce the clutter). Reducing to a maximum-flow problem, there cannot be a multiple of 15 with fewer than four 1 bits set unless the minimum flow through the graph from node 5 to node 0 is less than 4. In other words, we can only pass through three odd nodes total. Since 5 and 1 are required nodes, the path from 5 to 0 can only include one additional odd node. The graph on the left includes all of the possible edges; The graph on the right has the 0-5, 1-5, 7-3 and 9-9 nodes removed as paths with these edges will have a flow > 3.
Thanks. I started to do something like this originally, but I stuck with the method above, because it was easier for me to visualize it. I'll look into this a little more (brush up on and get more experience with graph theory).
Gadget wrote:
I think this representation makes it easier to visualize problems with this approach to a proof. Obviously, there are still problems to work out (basically, the same problems). Notice there is a cycle of even nodes adjacent to the 5 and 1 nodes. There is also the 9 node right in the middle of this cycle. This means there are potentially an infinite number of paths with a flow of 2 or 3 (ie 2 bits or 3 bits set). Clearly, you won't be able to enumerate all possible values into a tree (w/o breaking this cycle). Granted, the trip from 5 to 0 doesn't guarantee a value that is a multiple of 15, but I'm not sure how you can determine this in advance. And in both cases, there is nothing providing proof that additional valid edges weren't included in the graph.
If there were a way of encoding the multiple of 3 requirement into the graph, then we could solve using max-flow. As it stands, unless there is some way to break the cycle in the middle, I don't think this method will result in a proof.
You're right, there is a cycle, but it must eventually break. I'll try to figure this hole out. I think the way to do it is to show that any number the cycle would produce, is not a multiple of 15.
The start of this method:
The cycle would go, removing any internal loops (a temporary deviation from the main cycle), 5, 2, 6, 8, 4, 2, 6, 8, 4, ..., 2, 6, 8, 4, 2 or 3, 1, 0 (2 starts the cycle and 2 or 3 ends the cylce, as can be seen from the graph). This produces a number with only two 1 bits. Starting at 1, n_(i+1) = 2 * n_i, until the very end (5), where n_(i+1) = 2 * n_i. In other words, it is 1000...00001. Adding internal loops back in produces a binary form of 1000...1...0001 (any more than one internal loop produces four 1 bits). So the goal then becomes showing that any number of the form 100...001 (2^n + 1) and 100...1...001 (2^n*(2*n_i + 1) + 1) is not a multiple of 15.