From: Bastian Erdnuess on 3 Dec 2009 04:00 Scott Hemphill 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 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 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 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