Prev: mini-challenge from UH contest
Next: Analogon to 28S' FORM on the HP 50g
From: Bastian Erdnuess on 3 Dec 2009 04:00
Scott Hemphill <hemphill(a)hemphills.net> wrote:

> > 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. :-)

Now it is :-)

***

> > 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]).

> > 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.

Well, no I did something. I changed the update routine to

void updateB(int *nums, int lastrow, int run)
{
int i, j;

for (i = 1; i <= lastrow; i++) {
for (j = 0; j < MOD; j++) {
table[i][j] += table[i-1][j];
}
}
for (i = lastrow; i > run; i--) {
for (j = 0; j < MOD; j++) {
table[i][(j+nums[i])%MOD] = table[i-1][j];
}
}
for (j = 0; j < MOD; j++) {
table[run][j] = 0;
}
}

You now need to call it 'update(primes,NP,i)' or
'update(composites,NC,i)' with a third parameter i that gives the number
of the run.

It runs an order faster this way, the running time of update is now
linear in NP (or NC) instead of quadratic before.

The first 'for' makes a cumulative sum of the rows in table. The second
'for' rotates each line by the number according to what the last person
has chosen. The second 'for' also moves all rows back in position one
down. The last 'for' then finally whipes out the first non-zero line.
I.e. while the third man had still one chance to chose the 5, it's not
possible anymore for the fourth one.

Note that it would be actually not necessary to calculate the last
'NM/NW-run' rows since they get killed in the next steps anyway, and
also not the first 'run' rows, since they are zero anyway. So one could
transform it into inplace algorithm on just NP-NM (or NC-NW) rows
(probably with a +1 or -1 somewhere). I tried, but failed on that.

***

If the HP can manage a collection of vectors, do their cumulative sum,
and rotate vectors, this should be easy to implement.

Does anybody knows how to perform a cumulative sum and a vector rotation
on the HP?

To explain this a little bit more, the cumulative sum of the three
vectors

[1 1 1 1]
[1 2 3 4]
[1 3 5 3]

should be the following three vectors

[1 1 1 1] = [1 1 1 1]
[1 2 3 4] + [1 1 1 1] = [2 3 4 5]
[1 3 5 3] + [1 2 3 4] + [1 1 1 1] = [3 6 9 8]

and the rotation by 2 to the right of

[1 2 3 4 5] should be [4 5 1 2 3] .

Thanks,
Bastian
From: Dave Hayden on 3 Dec 2009 08:30
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. 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 3 Dec 2009 12:01
earthnut(a)web.de (Bastian Erdnuess) writes:

[snip]

> If the HP can manage a collection of vectors, do their cumulative sum,
> and rotate vectors, this should be easy to implement.
>
> Does anybody knows how to perform a cumulative sum and a vector rotation
> on the HP?
>
> To explain this a little bit more, the cumulative sum of the three
> vectors
>
> [1 1 1 1]
> [1 2 3 4]
> [1 3 5 3]
>
> should be the following three vectors
>
> [1 1 1 1] = [1 1 1 1]
> [1 2 3 4] + [1 1 1 1] = [2 3 4 5]
> [1 3 5 3] + [1 2 3 4] + [1 1 1 1] = [3 6 9 8]
>
> and the rotation by 2 to the right of
>
> [1 2 3 4 5] should be [4 5 1 2 3] .

I've got a version of the program running right now on my 49G. (My
48GX has a mysterious key ailment where it doesn't work during the
winter months, but then starts working again in the summer.) I'm
using exact integers in symbolic arrays, and it will probably have an
answer in an hour or two. If I used real arrays or had a 50g it would
be a lot faster. I don't know if there are really good ways of
handling these situations, but here's what I did:

The cumulative sum:

[1 1 1 1]
[1 2 3 4]
[1 3 5 3]

In this case "n" (the number of vectors) is 3.

n ROLL
2. n FOR k
DUP
n k - 3. + ROLLD
n k - 2. + ROLL
+
NEXT

for the rotation, I did:

[1 2 3 4 5]

Let "j" be the number of elements to rotate to the right

DUP OBJ\-> DROP 6. ROLL DUP OBJ\-> DROP 10. \->ARRY
6. j - DUP 4. + SUB

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Scott Hemphill on 3 Dec 2009 12:54
Scott Hemphill <hemphill(a)hemphills.net> writes:

> for the rotation, I did:
>
> [1 2 3 4 5]
>
> Let "j" be the number of elements to rotate to the right
>
> DUP OBJ\-> DROP 6. ROLL DUP OBJ\-> DROP 10. \->ARRY
> 6. j - DUP 4. + SUB

Oops, I inadvertently left in an unwanted DUP. This is the way it
should read:

DUP OBJ\-> DROP 6. ROLL OBJ\-> DROP 10. \->ARRY
6. j - DUP 4. + SUB

Scott
--
Scott Hemphill hemphill(a)alumni.caltech.edu
"This isn't flying. This is falling, with style." -- Buzz Lightyear
From: Scott Hemphill on 3 Dec 2009 13:49
Scott Hemphill <hemphill(a)hemphills.net> writes:

> The cumulative sum:
>
> [1 1 1 1]
> [1 2 3 4]
> [1 3 5 3]
>
> In this case "n" (the number of vectors) is 3.
>
> n ROLL
> 2. n FOR k
> DUP
> n k - 3. + ROLLD
> n k - 2. + ROLL
> +
> NEXT

This looks like it can be improved:

n ROLL
2. n START
n ROLL OVER +
NEXT

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