Beefy Boxes and Bandwidth Generously Provided by pair Networks
P is for Practical
 
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
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 surveying the Monastery: (6)
As of 2014-09-21 09:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    How do you remember the number of days in each month?











    Results (168 votes), past polls