On Dec 19, 2009, at 1:36 PM, 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.
The sequence of numbers whose digit sum is 13 is one of the ATT
integer sequences:
http://www.research.att.com/~njas/sequences/A143164
No R implementations there, only Maple and Mathematica. Rather than
doing strsplit()'s, I thought that a mathematical approach would be
faster for a sumdigits function:
sumdigits <- function(x) { s=0; for (i in 1:(1+floor(log(x,
base=10))) ){
s<-s+x%%10; x<-x%/%10}
return(s) }
# what follows would be expected to take roughly 1/100th and 1/50th
of the time of a complete enumeration but is useful for estimating the
size of the result and the time of an exhaustive search:
> system.time( for (i in 10000079:11000079) if (sumdigits(i)==17)
{idx<-c(idx,i)})
user system elapsed
30.997 3.516 34.403
> system.time( for (i in 10000079:12000079) if (sumdigits(i)==17)
{idx<-c(idx,i)})
user system elapsed
55.975 2.433 58.218
> head(idx)
[1] 10000079 10000088 10000097 10000169 10000178 10000187
> length(idx)
[1] 31572
So it looks as though an exhaustive strategy would take a bit under an
hour on my machine (a 2 year-old device) and be a vector around
1578600 elements in length. (Takes very little memory, and would
undoubtedly be faster if I could use more than one core.)
baptiste
David Winsemius, MD
Heritage Laboratories
West Hartford, CT
______________________________________________
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.
