Prev: mini-challenge from UH contest
Next: Analogon to 28S' FORM on the HP 50g
From: Scott Hemphill on 1 Dec 2009 12:28
earthnut(a)web.de (Bastian Erdnuess) writes:

> Scott Hemphill <hemphill(a)hemphills.net> 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 <kdo4973(a)gmail.com> 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 <hemphill(a)hemphills.net> 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 <hemphill(a)hemphills.net> 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
Pages: 1 2 3 4 5
Prev: mini-challenge from UH contest
Next: Analogon to 28S' FORM on the HP 50g