Ad
Algorithms
Logic
Mathematics
Numbers
Data Types

John likes numbers and digits. He takes digits of numder and sums squares of them.
Write function calc with input natural number n and output sum of squares of digits.

calc(1) = 1 // 1*1
calc(2) = 4 // 2*2
calc(123) = 14 // 1*1 + 2*2 + 3*3
calc(512) = 30 // 5*5 + 1*1 + 2*2

Also write function cumulate with input natural number n and output sum of function calc result for numbers from 1 to n.

cumulate(1) = 1 // calc(1) = 1
cumulate(2) = 5 // calc(1) + calc(2) = 1 + 4
cumulate(3) = 14 // calc(1) + calc(2) + calc(3) = 1 + 4 + 9
cumulate(12) = 293 // calc(1) + calc(2) + .. calc(11) + calc(12) = 1 + 4 + ... 2 + 5

Using special algorithm John found that

cumulate(12345678) = 2390700939
cumulate(123456789) = 27425527905
def calc n
  n.to_s.chars
		.map{|x|x.to_i**2}
		.reduce(:+)
end

def cumulate n
  sum_sq = ->(a,m){(a/m)*(a/m-1)*(a/m*2-1)/6*m+(a%m+1)*(a/m)**2}
  sum_bi = lambda do |a,u,v|
    t = (a/u)*(a/u/v)*(a+1-(a/u)*u)
	  ht = (a/u/v)*(a/u%v)*(2*(a/u)-1-a/u%v)/2
	  hha = v*sum_sq.(a/u/v*v-1,v)
	  hhb = (a/u/v)*(a/u/v-1)*v*(v-1)/4
	  (hhb+hha+ht)*u+t
  end
  (0..Math.log(n,10).ceil)
    .reduce(0){|s,d|s+sum_sq.(n,10**d)+100*sum_sq.(n,10*10**d)-20*sum_bi.(n,10**d,10)}
end