Prev: mini-challenge from UH contest
Next: Analogon to 28S' FORM on the HP 50g
From: Bastian Erdnuess on 4 Dec 2009 03:07
Dave Hayden <dave(a)larou.com> wrote:

> On Dec 1, 1:46 am, earth...(a)web.de (Bastian Erdnuess) wrote:
> > Scott Hemphill <hemph...(a)hemphills.net> wrote:
> > > composite numbers in increasing order. What is the probability that
> > > she can choose a composite number in the set...
> >
> > How exact does it need to be? Without a calculator I would have said
> > that after the first 31 picked their numbers there are 74 - 18 = 56
> > possible composite numbers for Ms. 32 left, each with a chance of 1/103
> > to fill up the sum to the next multiple of 103. Furthermore, the
> > chances are 1/19 that this is the biggest composite number chosen.
> >
> > Thus, the chances are about 56/103/19 ~ 2.71% that Ms. 32 can make her
> > choice.
>
> I think you've misread the problem. It asks for the probability that
> she CAN choose the number, not the probability that she DOES choose
> it.

That should be fine. One of the 56 numbers could fill-up to the next
multiple of 103, so the chances are 56/103 that there is any number
which fills up to the next multiple of 103.

> So I think one can rephrase the question as "what is the
> probability that there exists a number larger than any of the
> composites chosen by the first 31 women and smaller than 101 such that
> the sum of all numbers chosen is an integral multiple of 103. There
> is at most one such number.
>
> This may greatly simplify the problem, so it may be a trick question.
From: Scott Hemphill on 6 Dec 2009 16:14
earthnut(a)web.de (Bastian Erdnuess) writes:

> Bastian Erdnuess <earthnut(a)web.de> wrote:

[snip]

> MEN
> { 4 6 8 9 ... 100 } // list with the first 74 composite numbers
> 18
> CNT
>
> and I got the answer after 769 seconds. I stored the resulting list in
> WOMEN and right now I think about a clever way to count the 'good'
> outcomes.

It's probably not the fastest, but a very simple way to count the 'good'
outcomes would be:

{ 4 6 8 9 ... 100 }
1
CNT
\GSLIST
1. GET

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Bastian Erdnuess on 6 Dec 2009 18:46
Scott Hemphill <hemphill(a)hemphills.net> wrote:

> earthnut(a)web.de (Bastian Erdnuess) writes:
>
> > Bastian Erdnuess <earthnut(a)web.de> wrote:
>
> [snip]
>
> > MEN
> > { 4 6 8 9 ... 100 } // list with the first 74 composite numbers
> > 18
> > CNT
> >
> > and I got the answer after 769 seconds. I stored the resulting list in
> > WOMEN and right now I think about a clever way to count the 'good'
> > outcomes.
>
> It's probably not the fastest, but a very simple way to count the 'good'
> outcomes would be:
>
> { 4 6 8 9 ... 100 }
> 1
> CNT
> \GSLIST
> 1. GET

I can't imagine what this does, yet. Is the first of the three
arguments CNT takes the list WOMAN? Does CNT threads over lists? Hmm.
I hope, I'll figure out tomorrow.

Btw. I identified the elements to count. In WOMAN stored is the
following table

0 1 2 3 4 5 6 ... 70 71 72 73 74 75 ... 102
---------------------------------------------------
28: X X X . . . X . . X . X x X
30: X X X . . . X . . X x X x X
32: X X X . . . X . x X x X x X
33: X X X . . . X x x X x X x X
34: X X X . . . X x x X x X x X
:
95: X X X . . . X x x X x X x X
96: X X X . . . X x x X x X x X
98: X X X . . x X x x X x X x X
99: X X X . x x X x x X x X x X
100: X X X x x x X x x X x X x X
---------------------------------------------------
100 99 98 33 32 30 28

In the headers the cosets (0 1 2 3 ... 102) modulo 103 are written, the
columns are numbered by the number the 18th woman has chosen.

The first three columns are /categorically/ 'bad' since the 19th women
would have to chose a number greater then 100, also the last since she'd
have to chose a number smaller than 2. Furthermore, columns like 6 or
72 are /categorically/ 'bad', since she would need to chose a prime,
like 97 or 31.

Line 3 is /principally/ 'good', since she can chose 100, but only before
row '100'. Also columns like 5 or 73 are /principally/ good, since she
can chose 98, or 30, but only in rows before '98' or '30' respectively.
All columns from 75 are /totally/ 'bad' anyway, since she would need to
chose a number smaller or equal to 28, and they're all already gone.

So, removing the /categorically/ and /totally/ 'bad' columns (and the
last row '100') leves a 55x55-square matrix (actually list of
(row-)vectors) from which the left upper triangle (with diagonal) summed
up yields the number of 'good' outcomes.

The indices of the /principally/ good columns (in usual HP indexing
starting by 1) can be found by

{ 4 6 8 9 10 ... 98 99 100 }
19 74 SUB
104 SWAP -
'GC' STO

Now, in GC contains the list { 74 72 71 70 ... 9 8 6 5 4 }.

Something like

'total' <-- 0
for i = 1 .. 55
take i-th row of WOMEN
pick the elements in GC from that row
sum them up
add the sum to 'total'
remove the first (biggest) element from GC (and thus change GC)
end for

could now do the job.

Bastian
From: Scott Hemphill on 6 Dec 2009 22:26
earthnut(a)web.de (Bastian Erdnuess) writes:

> Scott Hemphill <hemphill(a)hemphills.net> wrote:
>
>> earthnut(a)web.de (Bastian Erdnuess) writes:
>>
>> > Bastian Erdnuess <earthnut(a)web.de> wrote:
>>
>> [snip]
>>
>> > MEN
>> > { 4 6 8 9 ... 100 } // list with the first 74 composite numbers
>> > 18
>> > CNT
>> >
>> > and I got the answer after 769 seconds. I stored the resulting list in
>> > WOMEN and right now I think about a clever way to count the 'good'
>> > outcomes.
>>
>> It's probably not the fastest, but a very simple way to count the 'good'
>> outcomes would be:
>>
>> { 4 6 8 9 ... 100 }
>> 1
>> CNT
>> \GSLIST
>> 1. GET
>
> I can't imagine what this does, yet. Is the first of the three
> arguments CNT takes the list WOMAN? Does CNT threads over lists? Hmm.
> I hope, I'll figure out tomorrow.

Yes, my idea was to process the list WOMAN. However, I didn't fully
understand your code. You will have to strip the first 18 composites
out of the list { 4 6 8 9 ... 100 }. Also, I think you have to drop
the last vector from WOMAN before you start processing. The idea is
produce a list of vectors that hold the complete state of 19
successful choices by women. The totals you are interested in are all
in the first position of the vectors (zero mod 103). So, use \GSLIST
to sum the list to get a total vector, then GET the first element.

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: John H Meyers on 7 Dec 2009 20:13
On Mon, 07 Dec 2009 17:11:34 -0600, Scott Hemphill wrote:

> I've discovered a disadvantage to these DOLIST implementations:
> they use a lot more memory! I'm guessing that they keep the
> original arrays in memory until the whole command is finished.
> When I'm calculating the value of WOMEN using exact arithmetic,
> I run out of memory.

All user commands keep their original arguments in memory
while flag -55 is clear; set that flag to not save arguments
for potential restoration upon either errors or LASTARG command.

You can also adjust this in 69 MENU, which includes
other settings that are not flag-based, such as
Last Stack (for UNDO) and Last Commands (last four edited input texts);
clear the "dot" from the last three menu items to save the least stuff.

[r->] [OFF]
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