Dartboard Question

[lavalamp]

I'd made a couple of mistakes (I'd specifically tuned my code for the previous set of scores and hadn't re-tuned it for these, so it missed some combos), also somehow I missed out the second 24. Also I stopped at 14 darts instead of running to 17.

So yeah, NOW I also get 82339371.

Unfortunately I have no idea how FFTs work, so I don't know what specific methods you're refering to. However, I will read around and have a think as to how I could speed up my code (this last run 93 mins ).

[ckdo]

Somewhat optimized results:

kossy@leela:~/darts2> time ./darts2
Value for N=100 is 82339371.
Peak at N=667: 17496397018818748.
Peak at N=668: 17496397018818748.

real    0m0.002s
user    0m0.001s
sys     0m0.001s
kossy@leela:~/darts2>

Code might run faster with mprime stopped, but ... nah.

Where did the 1072 come from, again?

[retina]

Originally Posted by ckdo

Value for N=100 is 82339371.
Peak at N=667: 17496397018818748.
Peak at N=668: 17496397018818748.

Yes, I concur with that.

Originally Posted by ckdo

Where did the 1072 come from, again?

1072 was for the original problem with 43 unique targets. Your answer is for 62 unique targets with maximal sum of 1335, hence the peaks at floor[1335/2] and ceil[1335/2].

[ckdo]

Originally Posted by retina

You need a better algorithm. It is a trivial Q actually. I ran all sums up to 1072 in <1 second. Think about using divide and conquer methods similar to FFT

[edit]For all area scores (62 areas will bullseye) I get 82339371 for N=100[/edit]

Ah, yes. It escaped me that the 1072 was in the unedited part of the message and I didn't conclude you were talking about the original problem.

[retina]

Originally Posted by retina

[edit]For all area scores (62 areas will bullseye) I get 82339371 for N=100[/edit]

Oops, that should be ... (62 areas with bullseye) ...

[davar55]

Originally Posted by R.D. Silverman

Compute the coefficient of x^100 in the generating function
1/[(1-x)(2-x)(3-x)(4-x)............(60-x)]

Is this the right generating function?
Shouldn't it be the coefficient of x^100 in
(1+x)(1+x^2)(1+x^3)(1+x^4).....(1+x^57)(1+x^60) [43 terms]?

And then if we want to allow for one dart per area,
just raise the appropriate term to the power = #areas with that value,
e.g. (1+x^6)^3 because 6 is the value of three areas.
(Which yields 62 terms.)

[grandpascorpion]

I think Davar is right.

If you wanted up to three terms, I believe the term would be

(1 + x^6 + x^12 + x^18) rather than (1+x^6)^3

[Kees]

An interesting link, slightly related

http://www.maa.org/mathland/mathland_5_19.html

[davieddy]

I'm still intrigued by Davar's choice of 43 numbers.

[bsquared]

Originally Posted by davieddy

I'm still intrigued by Davar's choice of 43 numbers.

Intrigued by something other than the fact they are a list of all possible point values one can score by throwing one dart?

[davieddy]

Doh

Originally Posted by bsquared

Intrigued by something other than the fact they are a list of all possible point values one can score by throwing one dart?