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
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
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
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