baptiste auguie wrote:
> 2009/12/19 David Winsemius <dwinsem...@comcast.net>:
>> On Dec 19, 2009, at 9:06 AM, baptiste auguie wrote:
>>
>>> Dear list,
>>>
>>> In a little numbers game, I've hit a performance snag and I'm not sure
>>> how to code this in C.
>>>
>>> The game is the following: how many 8-digit numbers have the sum of
>>> their digits equal to 17?
>> And are you considering the number "00000089" to be in the acceptable set?
>> Or is the range of possible numbers in 10000079:98000000 ?
>>
>
> The latter, the first digit should not be 0. But if you have an
> interesting solution for the other case, let me know anyway.
>
> I should also stress that this is only for entertainment and curiosity's sake.
>
> baptiste
>
I realize I'm late coming to this, but I was reading it in my post-vacation
catch-up and it sounded interesting so I thought I'd give it a shot.
After coding a couple of solutions that were exponential in time (for the
number of digits), I rearranged things and came up with something that is
linear in time (for the number of digits) and gives the count of numbers for
all sums at once:
library(plyr)
nsum3 <- function(digits) {
digits <- as.integer(digits)[[1L]]
if (digits==1) {
rep(1,9)
} else {
dm1 <- nsum3(digits-1)
Reduce("+", llply(0:9, function(x) {c(rep(0,x),dm1,rep(0,9-x))}))
}
}
nsums <- llply(1:8, nsum3)
nsums[[5]][17]
# [1] 3675
nsums[[8]][17]
# [1] 229713
The whole thing runs in well under a second on my machine (a several years old
dual core Windows machine). In the results of nsum3, the i-th element is the
number of "numbers" whose digits sum to i. The basic idea is recursion on the
number of digits; if n_{t,d} is the number of d-digit "numbers" that sum to t,
then n_{t,d} = \sum_{i\in(0,9)} n_{t-i,d-1}. (Adding the digit i to each of
those "numbers" makes their sum t and increases the digits to d). When
digits==1, then 0 isn't a valid choice and that also implies the sum of digits
can't be 0, which fits well with the 1 indexing of arrays.
--
Brian Diggs, Ph.D.
Senior Research Associate, Department of Surgery, Oregon Health & Science
University
______________________________________________
R-help@r-project.org mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
