let x=2^m*(2n+1)
then m is the largest power of 2 dividing x
and 2n+1 is the largest odd number dividing x
thus d(x)=2n+1
let L=2^99
now we need
2^m*(2n+1)<=L
n<=floor((L-1)/2^(m+1))
and since 2n+1>=1 we have
2^m<=L -> 2^m<=2^99 -> m<=99
thus we can represent the sum
Sum(d(x), x=1 to L) as the nested summation
Sum(2n+1,m=0 to 99,n=0 to floor((L-1)/2^(m+1)))
lets deal with the inner summation first
let F=floor((L-1)/2^(m+1))
sum(2n+1,n=0 to F)
2*F(F+1)/2 + F+1
F(F+1)+F+1
(F+1)^2
thus we have
sum((F+1)^2,m=0 to 99)
now
F=floor((L-1)/2^(m+1))=Floor((2^99-1)/(2^(m+1))
=Floor(2^(98-m)-2^(-m-1))
now for m=99 this equal zero
for all other m 0 to 98 this equal 2^(98-m)-1
thus we have
sum(2^(98-m)-1,m=0 to 98)
sum(2^98*(1/2)^m-1,m=0 to 98)
2^98*sum((1/2)^m,m=0 to 98)-99
2^98*(2^99-1)/2^98 - 99
2^99-1-99
2^99-100
since we want the last 3 digits we need this value mod 10^3
to calculate 2^99 mod 10^3 we can build up from lower powers
2^10=1024=24 mod 10^3
2^30=24^3 mod 10^3 = 13824 mod 10^3 = 824 mod 10^3
2^90=824^3 mod 10^3 = 559476224 mod 10^3 = 224 mod 10^3
2^99 = 2^9*224 mod 10^3 = 114688 mod 10^3 = 688 mod 10^3
thus the last three digits of the sum is 588

Posted by Daniel on 2013-10-12 08:20:26