in reply to Challenge: Chasing Knuth's Conjecture

Your challenge was to write an elegant, fast, or golfish program. As I look at the problem, I can see an elegant solution, but unfortunately all the implementations I have tried so far are slow in comparison.

You can treat the problem as a tree where each node has two children - the sqrt and the factorial. The stack starts out with the root node (3). After each node has its two children, it is removed from the stack and placed in the tree. A branch is terminated if the child node represents its parent (sqrt(1) = 1, fact(2) = 2), the node is already present in the tree, or the number is beyond a user imposed limit.

Finding the path to a particular node is done in reverse (since the tree is represented by a hash). You select the node and traverse backwards to the root. If you would like to see my implementation, let me know and I will post what I came up with tomorrow when I get to work.

Cheers - L~R

Replies are listed 'Best First'. | |
---|---|

Re^2: Challenge: Chasing Knuth's Conjecture
by Roy Johnson (Monsignor) on Mar 30, 2005 at 03:34 UTC |

Comment onRe: Challenge: Chasing Knuth's ConjectureDownloadCode