Nice --- am I missing something or was this closed form solution not entirely trivial to find?
I ought to compile the various clever solutions given in this thread someday, it's fascinating! Thanks, baptiste 2010/1/12 Greg Snow <greg.s...@imail.org>: > This also has a closed form solution: > >> choose(16+8-1,7) - choose(7+8-1, 7) - 7*choose(6+8-1,7) > [1] 229713 > > > -- > Gregory (Greg) L. Snow Ph.D. > Statistical Data Center > Intermountain Healthcare > greg.s...@imail.org > 801.408.8111 > > >> -----Original Message----- >> From: r-help-boun...@r-project.org [mailto:r-help-boun...@r- >> project.org] On Behalf Of Brian Diggs >> Sent: Thursday, December 31, 2009 3:08 PM >> To: baptiste auguie; David Winsemius >> Cc: r-help >> Subject: Re: [R] expand.grid game >> >> 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. > ______________________________________________ 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.
