Hi,
Thanks for the link, I guess it's some kind of a classic game. I'm a
bit surprised by your timing, my ugly eval(parse()) "solution"
definitely took less than one hour with a machine not so different
from yours,
system.time( for (i in 10000079:11000079) if (sumdigits(i)==17) {idx<-c(idx,i)})
user system elapsed
34.050 1.109 35.791
I'm surprised by idx<-c(idx,i), isn't that considered a sin in the R
Inferno? Presumably growing idx will waste time for large N.
Thanks,
baptiste
2009/12/19 David Winsemius <dwinsem...@comcast.net>:
>
> 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.
