Gregory (Greg) L. Snow Ph.D.
Statistical Data Center
Intermountain Healthcare
greg.snow at imail.org
801.408.8111
> -----Original Message-----
> From: baptiste auguie [mailto:baptiste.auguie at googlemail.com]
> Sent: Tuesday, January 12, 2010 12:20 PM
> To: Greg Snow
> Cc: r-help
> Subject: Re: [R] expand.grid game
>
> 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.Snow at 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.snow at imail.org
> > 801.408.8111
> >
> >
> >> -----Original Message-----
> >> From: r-help-bounces at r-project.org [mailto:r-help-bounces at 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 <dwinsemius at 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 at 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.
> >