Differences between revisions 8 and 9
 ⇤ ← Revision 8 as of 2007-12-24 21:35:28 → Size: 2937 Editor: DanBron Comment: #.66#1 ← Revision 9 as of 2008-12-08 10:45:52 → ⇥ Size: 2924 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 2: Line 2: ''Compress the decimal representation of a natural number to an expression in J with less characters than the number of digits.''[[BR]] ''Compress the decimal representation of a natural number to an expression in J with less characters than the number of digits.''<
> Line 10: Line 10: This puzzle was inspired by a solution given by ["Raul Miller"] in [http://www.jsoftware.com/pipermail/programming/2007-December/009046.html Jforum] where he gave an excellent example of compression. See [:Puzzles/Compress#example:example]. This puzzle was inspired by a solution given by [[Raul Miller]] in [[http://www.jsoftware.com/pipermail/programming/2007-December/009046.html|Jforum]] where he gave an excellent example of compression. See [[Puzzles/Compress#example|example]]. Line 18: Line 18: * ` %~&(#@":)". ` can be used to determine the compression (rate) of an expression.[[BR]]{{{ (%~&(#@":)".)'!5' * ` %~&(#@":)". ` can be used to determine the compression (rate) of an expression.<
>{{{ (%~&(#@":)".)'!5' Line 21: Line 21: * Numbers which are not compressable are "Kolmogorov random", see [http://en.wikipedia.org/wiki/Kolmogorov_complexity#Kolmogorov_randomness Kolmogorov] * Proliferation of modern programming languages:[[BR]] "APL: You shoot yourself in the foot, then spend all day figuring out how to do it in fewer characters." * Numbers which are not compressable are "Kolmogorov random", see [[WikiPedia:Kolmogorov_complexity#Kolmogorov_randomness|Kolmogorov]] * Proliferation of modern programming languages:<
> "APL: You shoot yourself in the foot, then spend all day figuring out how to do it in fewer characters." Line 28: Line 28: ||<)>120||<:>`!5`||<:>1.5||<(>Trivial, since ` !y ` needs less characters for all ` y>4 `.[[BR]]Smallest number (I know of) which can be compressed||[:RE Boss]||||<)>1024||<:>`4^5`||<:>1.33||Trivial, since most of ` x^y ` are compressed.[[BR]]`x = 2 3 4 5 6 7 8 9 10`[[BR]]`y>: 14 7 5 5 4 4 4 4 4` ||[:RE Boss]||||<)>[[Anchor(example)]]9534410355667921512188400||<:>`*./33+i.29x`||<:>2.27||Smallest number which is divisible by all numbers 1,...,61,[[BR]] except two successive ones. See[http://www.jsoftware.com/pipermail/programming/2007-December/009046.html Jforum]||["Raul Miller"]||||<)>73786976294838206000||<:>`#.66#1`||<:>3.333|| Neat that it's a ratio of exactly 10r3 || -- DanBron [[DateTime(2007-12-24T21:35:28Z)]] || ||<)>120||<:>`!5`||<:>1.5||<(>Trivial, since ` !y ` needs less characters for all ` y>4 `.<
>Smallest number (I know of) which can be compressed||[[RE Boss]]||||<)>1024||<:>`4^5`||<:>1.33||Trivial, since most of ` x^y ` are compressed.<
>`x = 2 3 4 5 6 7 8 9 10`<
>`y>: 14 7 5 5 4 4 4 4 4` ||[[RE Boss]]||||<)><>9534410355667921512188400||<:>`*./33+i.29x`||<:>2.27||Smallest number which is divisible by all numbers 1,...,61,<
> except two successive ones. See[[http://www.jsoftware.com/pipermail/programming/2007-December/009046.html|Jforum]]||[[Raul Miller]]||||<)>73786976294838206000||<:>`#.66#1`||<:>3.333|| Neat that it's a ratio of exactly 10r3 || -- DanBron <> || Line 34: Line 34: [[BR]][[BR]][[BR]] <
><
><
> Line 38: Line 38: * The [wiki:JForum:general/2005-March/020985 angels dancing] Forum thread from 2005. It has many good examples of short J expressions which produce astronomically large numbers (some actually can't be executed, but it is easily seen that if they could, the result would be unimaginable). [[BR]][[BR]] Note that the link provided only points to the head of the thread; most the examples are contained in later messages (just follow the "next in thread" links). * The [[JForum:general/2005-March/020985|angels dancing]] Forum thread from 2005. It has many good examples of short J expressions which produce astronomically large numbers (some actually can't be executed, but it is easily seen that if they could, the result would be unimaginable). <
><

## Problem

Compress the decimal representation of a natural number to an expression in J with less characters than the number of digits.
E.g. 120 can be compressed to  !5 .

### Constraints

• The expression(s) in J should produce the number for anyone in a new session in a freshly installed J-version with the maximal printing precision:  (9!:11) 20 .

• The total number of characters needed (in a new session in a freshly installed J-version) should be less than the number of digits in the decimal representation of the number.

### Credits

This puzzle was inspired by a solution given by Raul Miller in Jforum where he gave an excellent example of compression. See example.

### Rules

1. The rate of compression is the ratio between the number of (decimal) digits and the number of characters in the expression.
2. Since the compression ratio is unbounded, the smaller the number the better.
3. Higher (rate of) compression per number is better.

### Remarks

•  %~&(#@":)".  can be used to determine the compression (rate) of an expression.
{{{ (%~&(#@":)".)'!5'

1.5 }}}

• Numbers which are not compressable are "Kolmogorov random", see Kolmogorov

• Proliferation of modern programming languages:
"APL: You shoot yourself in the foot, then spend all day figuring out how to do it in fewer characters."

## Solutions

 Number Sentence Compression Notes Author 120 !5 1.5 Trivial, since  !y  needs less characters for all  y>4 . Smallest number (I know of) which can be compressed RE Boss 1024 4^5 1.33 Trivial, since most of  x^y  are compressed. x =  2 3 4 5 6 7 8 9 10 y>: 14 7 5 5 4 4 4 4  4 RE Boss 9534410355667921512188400 *./33+i.29x 2.27 Smallest number which is divisible by all numbers 1,...,61, except two successive ones. SeeJforum Raul Miller 73786976294838206000 #.66#1 3.333 Neat that it's a ratio of exactly 10r3 -- DanBron 2007-12-24 21:35:28