Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

comment on

( [id://3333] : superdoc . print w/replies, xml ) Need Help??

On a related note; a real challenge is also to just compute one of the entries in the table. Especially for higher values.

If we number the table as follows:

F 1 2 3 4 5 6 7 8 9 10 11 --> m 1 1 2 1 1 3 1 2 1 4 1 3 3 1 5 1 4 6 4 1 6 1 5 10 10 5 1 7 1 6 15 20 15 6 1 8 1 7 21 35 35 21 7 1 9 1 8 28 56 70 56 28 8 1 10 1 9 36 84 126 126 84 36 9 1 11 1 10 45 120 210 252 210 120 45 10 1 | n

it can be said to define a function F(n,m). For instance:

F(1,1) = 1 F(11,2) = 10 F(9,5) = 70

However for higher values of n this function returns very large numbers around the point F(n,n/2). This are the numbers in the center of the table. For instance try computing F(400,200) or F(400,199).

These numbers are so large they do not fit into a floatingpoint number. It's of course possible to use the BigInt package, but that slows down computation, and uses quite some memory. Hence just printing the table for large values of n becomes impossible.

However the numbers around F(n,n), and F(n,1) stay pretty small for large n and could be computed. These are the numbers at the edge of the table. For instance F(400,1) = F(400,400) = 1, and even F(400,5) is computable.

Finding F(n,m) is useful for several statistical and counting problems. However writing a program that efficiently computes F(n,m) for any n,m, is quite a challenge! (At least I found it quite a challenge when I tried to write one.) One approach is to 'walk' the edge of the table towards the entry that needs to be computed. Thereby avoiding the center of the table with all the giant numbers. But there must be a more effecient way to compute F .... any suggestions?

Have Fun


In reply to Re: Binomial Golf by gumpu
in thread Binomial Golf by tachyon

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.