Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Re: Challenge: Chasing Knuth's Conjecture

by Limbic~Region (Chancellor)
on Mar 30, 2005 at 01:01 UTC ( #443316=note: print w/replies, xml ) Need Help??


in reply to Challenge: Chasing Knuth's Conjecture

Mark,
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

Note: It is assumed that each operation will result in an implicit floor()

Replies are listed 'Best First'.
Re^2: Challenge: Chasing Knuth's Conjecture
by Roy Johnson (Monsignor) on Mar 30, 2005 at 03:34 UTC
    Limbic,
    I've also got what I think is a perly-golfish approach. It's at least somewhat novel, even if implementation turns out to be impractical. I haven't implemented it at all, but I'll describe it here in the hope that it's interesting.

    Every number is either a factorial or the integer sqrt of some other number (well, actually, every number is the latter, but some are also the former). So when you look at a number, you check to see if it's a factorial. If so, you replace it with NF, where N is what you apply the factorial function to to get your number (that is, the inverse-factorial of your number). Otherwise, you replace it with X..YS, where X and Y are the minimum and maximum values that you can plug into int(sqrt()) to get your number. S and F are literal characters to indicate the operation in your solution string.

    If you have already computed the solution for N, or for any number between X and Y, you can substitute that solution string for the number/range in your solution string and continue solving. Otherwise, you have to solve for it. If a factorial falls in your range, you replace your range with the factorial indicator as before. Otherwise, you expand your range using the inverse int(sqrt()) function.

    You proceed until the number (or range) at the beginning of your solution string includes your desired base case.


    Caution: Contents may have been coded under pressure.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://443316]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (8)
As of 2019-11-13 18:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Strict and warnings: which comes first?



    Results (74 votes). Check out past polls.

    Notices?