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)}
endTest.describe('Special tests') do
Test.assert_equals(calc(1), 1,"calc(1) = 1")
Test.assert_equals(calc(2), 4, "calc(2) = 4")
Test.assert_equals(calc(11), 2, "calc(11) = 2")
Test.assert_equals(calc(12), 5, "calc(12) = 5")
Test.assert_equals(calc(123), 14, "calc(123) = 14")
Test.assert_equals(calc(512), 30, "calc(512) = 30")
Test.assert_equals(cumulate(12), 293, "cumulate(12) = 293")
Test.assert_equals(cumulate(1728), 137470, "cumulate(1728) = 137470")
Test.assert_equals(cumulate(123456), 16870001, "cumulate(123456) = 16870001")
Test.assert_equals(cumulate(1234567), 203884928, "cumulate(1234567) = 203884928")
Test.assert_equals(cumulate(12345678), 2390700939, "cumulate(12345678) = 2390700939")
Test.assert_equals(cumulate(123456789), 27425527905, "cumulate(123456789) = 27425527905")
Test.assert_equals(cumulate(1234567890), 309440461350, "cumulate(1234567890) = 309440461350")
Test.assert_equals(cumulate(1234565890), 309440025966, "cumulate(1234565890) = 309440025966")
Test.assert_equals(cumulate(1231165890), 308794956217, "cumulate(1231165890) = 308794956217")
Test.assert_equals(cumulate(12345678901234567890), 6612923097811292310285, "cumulate(12345678901234567890) = 6612923097811292310285")
end
def cumulate_test 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
Test.describe('Random tests') do
10.times do
amt = rand(10**15) + 1
Test.assert_equals(cumulate(amt), cumulate_test(amt), "cumulate(#{amt}) = #{cumulate_test(amt)}")
end
end