123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990 |
- #!/usr/bin/ruby
- # Daniel "Trizen" Șuteu
- # Date: 10 March 2021
- # https://github.com/trizen
- # Let's consider the following function:
- # a(n,v) = Sum_{k=1..n} (v mod k)
- # The goal is to compute a(n,v) in sublinear time with respect to v.
- # Formula:
- # a(n,v) = n*v - A024916(v) + Sum_{k=n+1..v} k*floor(v/k).
- # Formula derived from:
- # a(n,v) = Sum_{k=1..n} (v - k*floor(v/k))
- # = n*v - Sum_{k=1..n} k*floor(v/k)
- # = n*v - Sum_{k=1..v} k*floor(v/k) + Sum_{k=n+1..v} k*floor(v/k)
- # Related problem:
- # Is there a sublinear formula for computing: Sum_{1<=k<=n, gcd(k,n)=1} k*floor(n/k) ?
- # See also:
- # https://oeis.org/A099726 -- Sum of remainders of the n-th prime mod k, for k = 1,2,3,...,n.
- # https://oeis.org/A340976 -- Sum_{1 < k < n} sigma(n) mod k, where sigma = A000203.
- # https://oeis.org/A340180 -- a(n) = Sum_{x in C(n)} (sigma(n) mod x), where C(n) is the set of numbers < n coprime to n, and sigma = A000203.
- func T(n) { # Sum_{k=1..n} k = n-th triangular number
- n.faulhaber(1)
- }
- func S(n) { # A024916(n) = Sum_{k=1..n} sigma(k) = Sum_{k=1..n} k*floor(n/k)
- #with (n.isqrt) { |s| sum(1..s, {|k| T(idiv(n,k)) + k*idiv(n,k) }) - T(s)*s }
- if (n < 0) {
- return (T(n.abs) + __FUNC__(n.abs-1))
- }
- n.dirichlet_sum({1}, {_}, {_}, {.faulhaber(1)})
- }
- func g(a,b) { # g(a,b) = Sum_{k=a..b} k*floor(b/k)
- if (b < 0) {
- return (T(b.abs) - T(a.abs-1) + __FUNC__(a, b.abs-1))
- }
- var total = 0
- while (a <= b) {
- var t = idiv(b, a)
- var u = idiv(b, t)
- total += t*(T(u) - T(a-1))
- a = u+1
- }
- return total
- }
- func sum_remainders(n, v) { # sub-linear formula
- sgn(v) * (n*v.abs - S(v) + g(n+1, v))
- }
- say {|n| sum_remainders(n, n.prime) }.map(1..20) #=> A099726
- say {|n| sum_remainders(n-1, n.sigma) }.map(1..20) #=> A340976
- for k in (1..8) {
- say ("A099726(10^#{k}) = ", sum_remainders(10**k, prime(10**k)))
- }
- # Positive v
- assert_eq(
- 20.of {|n| 20.of {|v| sum(1..n, {|k| v % k }) } },
- 20.of {|n| 20.of {|v| sum_remainders(n,v) } }
- )
- # Negative v
- assert_eq(
- 20.of {|n| 20.of {|v| sum(1..n, {|k| -v % k }) } },
- 20.of {|n| 20.of {|v| sum_remainders(n,-v) } }
- )
- __END__
- A099726(10^1) = 30
- A099726(10^2) = 2443
- A099726(10^3) = 248372
- A099726(10^4) = 25372801
- A099726(10^5) = 2437160078
- A099726(10^6) = 252670261459
- A099726(10^7) = 24690625139657
- A099726(10^8) = 2516604108737704
|