Perl: the Markov chain saw 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."

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.

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: (14)
As of 2019-10-15 09:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (37 votes). Check out past polls.

Notices?