Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re: Challenge: Chasing Knuth's Conjecture

by tall_man (Parson)
on Mar 29, 2005 at 21:33 UTC ( #443270=note: print w/ replies, xml ) Need Help??


in reply to Challenge: Chasing Knuth's Conjecture

On this page there is a reference to Knuth's conjecture but it says he starts with 4:

More recently, we have Knuth's Conjecture:

"Representing Numbers Using Only One 4", Donald Knuth, (Mathematics Magazine, Vol. 37, Nov/Dec 1964, pp.308-310). Knuth shows how (using a computer program he wrote) all integers from 1 through 207 may be represented with only one 4, varying numbers of square roots, varying numbers of factorials, and the floor function.

For example: Knuth shows how to make the number 64 using only one 4:

|_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt |_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt |_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt |_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt |_ sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt sqrt |_ sqrt |_ sqrt |_ sqrt sqrt sqrt sqrt sqrt (4!)! _| ! _| ! _| ! _| ! _| ! _| ! _| ! _|

As to notation in the above example, he means sqrt n! stands for sqrt (n!), not (sqrt n)!

Knuth further points out that |_ sqrt |_ X _| _| = |_ sqrt X _| so that the floor function's brackets are only needed around the entire result and before factorials are taken.

He CONJECTURES that all integers may be represented that way: "It seems plausible that all positive integers possess such a representation, but this fact (if true) seems to be tied up with very deep propertis of the integers."

Your Humble Webmaster believes that Knuth is right, for 9 as well as 4, and will prove that in a forthcoming paper.

Knuth comments: "The referee has suggested a stronger conjecture, that a representation may be found in which all factorial operations precede all square root operations; and, moreover, if the greatest integer function (our floor function) is not used, an arbitrary positive real number can probably be approximated as closely as desired in this manner."


Comment on Re: Challenge: Chasing Knuth's Conjecture
Download Code
Replies are listed 'Best First'.
Re^2: Challenge: Chasing Knuth's Conjecture
by Anonymous Monk on Mar 30, 2005 at 08:56 UTC
    On this page there is a reference to Knuth's conjecture but it says he starts with 4
    But since
    3 == |_sqrt(sqrt(|_sqrt(sqrt(sqrt(sqrt(sqrt(4!!)))))_|!))_|
    
    and
    4 == |_sqrt(sqrt(sqrt(sqrt(sqrt(sqrt((|_sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(((|sqrt(sqrt(3!!))_|)!)!)))))))_|)!))))))_|                        
    
    both "conjectures" are equivalent.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (7)
As of 2015-07-31 00:29 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (274 votes), past polls