From: Scott Hemphill on 1 Dec 2009 12:28 earthnut(a)web.de (Bastian Erdnuess) writes: > Scott Hemphill wrote: > >> earthnut(a)web.de (Bastian Erdnuess) writes: >> >> > Thus, the chances are about 56/103/19 ~ 2.71% that Ms. 32 can make her >> > choice. >> >> You have arrived at answer that is approximately correct. It's easy >> to show that this can't be the exact answer, however. To get the >> exact answer (I think!) I enumerated all the ways the choices could be >> made. I did this with a C program on my PC, but I believe that it >> could be done on in RPL on an HP48 series calculator. > > I didn't took my time to read your code, yet, but I almost cannot > beleave that you really enumerated all possibilities. The men are no > problem, they can choose their numbers in (25 over 13) ~ 5 million > different ways. But the first 18 women can choose their numbers already > in (74 over 18) ~ 73 * 10^15 different ways and it would take months to > enumerate them all, even on a modern cpu. > > Can you explain how your program works in some more human readable way? Be sure to read the notes after the program. If you run the program you will see that the total number of possibilites enumerated is indeed 377893220518123106330800, which is the product (25 over 13)*(74 over 18). The trick is to group together all the possibilites which share two properties. (This is why "table" is a two-dimensional array.) The first index of the array is the index of the last number chosen. For the men this ranges from 1 to 25, with the zero index of the table being reserved for the intial state in which no prime has yet been chosen. For the women, the first index ranges from 1 to 74, with the zero index of the table being reserved for the initial state in which no composite has yet been chosen. The second index of the array is the accumulated total of all the choices so far, modulo 103. The procedure "update" takes the table of enumerated possibilites and produces a new table for the possibilites for the choices made by a new person. The way it works is this: We start with a new table filled with zeros. For each non-zero entry in the old table, we tabulate the possible choices for the new person in the new table. Suppose we have already tabulated the possibilities for the first 10 men. The value of table[20][17] is now 818. This means that so far there were 818 ways in which the tenth man chose the 20th prime and the total of all the choices was 17 modulo 103. To calculate the corresponding possibilities for the eleventh man we would add 818 to table[21][90] because for each of the original possibilites, the eleventh man may now choose the 21st prime (73) which will bring the total to 17+73 = 90 mod 103. We would also add 818 to table[22][96] and add 818 to table[23][100] and add 818 to table[24][3] and add 818 to table[25][11]. (If you examine the code to update (and read the notes) you will see that the procedure is able to update "table" in place, without using memory for a new table.) My program does all of the choices for the men first, then the women. The initial value of table has only a single non-zero entry, table[0][0]=1, because there is only one way that none of the men have yet made a choice, and the total is equal to 0 mod 103. So "update" is then called 13 times. If you add up all the entries in the table, you will find that their total is 5200300, which is (25 over 13). All of the ways in which the total is k mod 103 are tabulated in column k. So a new table is created in which the totals of the columns is placed in row zero, and the rest of the table is zero. This is the initial table for the women. It contains the number of ways that none of the women have made a choice, and the total is equal to k mod 103. Update is then called 18 more times for the women, and "total" is calculated, which is the sum of all the entries in the table. I then loop over the table, summing in "count" all the ways that the 19th woman could pick a larger composite that brings the sum of the choices to 0 mod 103. It would also have been possible to just call update one more time and sum the entries in column zero, since there can never be more than one way to choose a number that will bring the sum to 0 mod 103. The C program produces a value for the probability in which the accuracy is limited only by roundoff error. My first program was in Mathematica, which produced an exact fraction. My C program, when compiled with an optimizing compiler, takes less than 0.02 seconds to run. Scott -- Scott Hemphill hemphill(a)alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear From: Yann on 1 Dec 2009 16:04 > (There are times that I really> wished that RPL arrays had PostScript semantics, i.e. that when you > DUP an array, you DUP the reference, not the memory.) Is that not the case ? I though that DUP does only duplicate the pointer to array memory allocation, so that if you really want to Duplicate the array itself, you need to do : DUP NEWOB From: Scott Hemphill on 1 Dec 2009 19:20 Yann writes: >> (There are times that I really >> wished that RPL arrays had PostScript semantics, i.e. that when you >> DUP an array, you DUP the reference, not the memory.) > > Is that not the case ? > I though that DUP does only duplicate the pointer to array memory > allocation, > so that if you really want to Duplicate the array itself, you need to > do : > DUP NEWOB Oops. I guess I knew less about RPL than I thought. :-) Thanks for bringing this to my attention. Scott -- Scott Hemphill hemphill(a)alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear From: Bastian Erdnuess on 2 Dec 2009 08:48 Scott Hemphill wrote: > earthnut(a)web.de (Bastian Erdnuess) writes: > > >> To get the > >> exact answer (I think!) I enumerated all the ways the choices could be > >> made. > > > > I didn't took my time to read your code, yet, but I almost cannot > > beleave that you really enumerated all possibilities. > > Be sure to read the notes after the program. Now, I took the time to do this. > If you run the program > you will see that the total number of possibilites enumerated is > indeed 377893220518123106330800, which is the product > (25 over 13)*(74 over 18). The trick is to group together all the > possibilites which share two properties. So, you actually didn't _enumerate_ all possibilities, you just counted them in some clever way. It looks like you found a pretty good way to count the number of ways they can make their choices such that the sum is in a certain coset modulo 103 in dependence of how many already picked their number and the biggest number already picked. What you basically use is the fact that when you already know that there are w ways that k men can choose their primes so that they sum up to m (mod 103) with the biggest chosen prime is p, and the k+1st man choses the prime q > p, then that w ways count also in the number of ways that k+1 men can choose their primes so that they sum up to m+q (mod 103) with the biggest chosen prime is q. A little bit rephrased this fact can also described as follows: Let f(k,p,[m]) the number of ways that k men can choose their primes, so that they sum up to m (mod 103) with the bigest chosen number is p, then it holds that f(k,p,[m]) = sum[q : q prime, q < p] f(k-1,q,[m-p]). Or in other words: The number of ways k men can choose primes so that they sum up to m (mod 103) with the biggest prime chosen is p is equal to the sum (over q < p) of all possible ways k-1 men can choose their primes so that they sum up to m-p (mod 103) with the biggest chosen prime is q. I think I see in this way to rephrase your solution some possibilities to improve your algorithm, especially with the view on how to port it to the HP later on. But I need to play a little bit around with it before I can continue on that. Bastian From: Scott Hemphill on 2 Dec 2009 16:54 earthnut(a)web.de (Bastian Erdnuess) writes: > Scott Hemphill wrote: > >> earthnut(a)web.de (Bastian Erdnuess) writes: >> >> >> To get the >> >> exact answer (I think!) I enumerated all the ways the choices could be >> >> made. >> > >> > I didn't took my time to read your code, yet, but I almost cannot >> > beleave that you really enumerated all possibilities. >> >> Be sure to read the notes after the program. > > Now, I took the time to do this. > >> If you run the program >> you will see that the total number of possibilites enumerated is >> indeed 377893220518123106330800, which is the product >> (25 over 13)*(74 over 18). The trick is to group together all the >> possibilites which share two properties. > > So, you actually didn't _enumerate_ all possibilities, you just counted > them in some clever way. I think it's clear that you know exactly what I did. :-) I don't think the first definition of enumerate at the website below requires that I list or count the possibilites one-at-a-time. I definitely did not enumerate by the second definition. http://www.merriam-webster.com/dictionary/enumerate > It looks like you found a pretty good way to count the number of ways > they can make their choices such that the sum is in a certain coset > modulo 103 in dependence of how many already picked their number and the > biggest number already picked. > > What you basically use is the fact that when you already know that there > are w ways that k men can choose their primes so that they sum up to m > (mod 103) with the biggest chosen prime is p, and the k+1st man choses > the prime q > p, then that w ways count also in the number of ways that > k+1 men can choose their primes so that they sum up to m+q (mod 103) > with the biggest chosen prime is q. > > A little bit rephrased this fact can also described as follows: Let > f(k,p,[m]) the number of ways that k men can choose their primes, so > that they sum up to m (mod 103) with the bigest chosen number is p, then > it holds that f(k,p,[m]) = sum[q : q prime, q < p] f(k-1,q,[m-p]). > > Or in other words: The number of ways k men can choose primes so that > they sum up to m (mod 103) with the biggest prime chosen is p is equal > to the sum (over q < p) of all possible ways k-1 men can choose their > primes so that they sum up to m-p (mod 103) with the biggest chosen > prime is q. Right. > I think I see in this way to rephrase your solution some possibilities > to improve your algorithm, especially with the view on how to port it to > the HP later on. But I need to play a little bit around with it before > I can continue on that. Yes, I think I see the same improvement you do. I'll be interested to see what you come up with. Scott -- Scott Hemphill hemphill(a)alumni.caltech.edu "This isn't flying. This is falling, with style." -- Buzz Lightyear First  |  Prev  |  Next  |  Last