12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 14 November 2019
- # https://github.com/trizen
- # Single summation formula for a double summation.
- # Given any function f(k), let:
- # F(n) = Sum_{k=1..n} f(k)
- # S(n) = Sum_{k=1..n} F(k)
- # then:
- # S(n) = Sum_{k=1..n} Sum_{j=1..k} f(j)
- # S(n) = Sum_{k=1..n} f(k) * (n - k + 1)
- # By splitting the sum into two sums, we get:
- # A(n) = Sum_{k=1..n} f(k)
- # B(n) = Sum_{k=1..n} f(k)*k
- # Which allows us to represent S(n) as:
- # S(n) = (n+1)*A(n) - B(n)
- func f(k) { # any function f(k)
- k.euler_phi
- }
- func F(n) { # partial sums of f(k)
- sum(1..n, {|k|
- f(k)
- })
- }
- func S1(n) { # partial sums of F(k)
- sum(1..n, {|k|
- F(k)
- })
- }
- func S2(n) { # equivalent with S1(n)
- sum(1..n, {|k|
- f(k) * (n - k + 1)
- })
- }
- #-------------------------------
- func A(n) {
- sum(1..n, {|k|
- f(k)
- })
- }
- func B(n) {
- sum(1..n, {|k|
- k * f(k)
- })
- }
- func S3(n) {
- (n+1)*A(n) - B(n)
- }
- #-------------------------------
- say F(100) #=> 3044
- say S1(100) #=> 104359
- say S2(100) #=> 104359
- say S3(100) #=> 104359
|