partial_sums_of_exponential_prime_omega_functions.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 16 March 2021
# https://github.com/trizen

# Compute partial sums of the following three functions in sublinear time:
#   S1(n) = Sum_{k=1..n} v^bigomega(k)
#   S2(n) = Sum_{k=1..n} v^omega(k)
#   S3(n) = Sum_{k=1..n} v^omega(k) * mu(k)^2

func S1(n,v=2) {    # Sum_{k=1..n} v^bigomega(k)
    sum(0..n.ilog2, {|k|
        v**k * k.almost_primepi(n)
    })
}

func S2(n,v=2) {    # Sum_{k=1..n} v^omega(k)
    sum(0..n.ilog2, {|k|
        v**k * k.omega_prime_count(n)
    })
}

func S3(n,v=2) {    # Sum_{k=1..n} v^omega(k) * mu(k)^2
    sum(0..n.ilog2, {|k|
        v**k * k.squarefree_almost_primepi(n)
    })
}

say 20.of(S1)   #=> A069205: [0, 1, 3, 5, 9, 11, 15, 17, 25, 29, 33, 35, 43, 45, 49, 53, 69, 71, 79, 81]
say 20.of(S2)   #=> A064608: [0, 1, 3, 5, 7, 9, 13, 15, 17, 19, 23, 25, 29, 31, 35, 39, 41, 43, 47, 49]
say 20.of(S3)   #=> A069201: [0, 1, 3, 5, 5, 7, 11, 13, 13, 13, 17, 19, 19, 21, 25, 29, 29, 31, 31, 33]

__END__

# A069205(n) = Sum_{k=1..n} 2^bigomega(k)

A069205(10^1)  = 33
A069205(10^2)  = 811
A069205(10^3)  = 15301
A069205(10^4)  = 260615
A069205(10^5)  = 3942969
A069205(10^6)  = 55282297
A069205(10^7)  = 746263855
A069205(10^8)  = 9613563919
A069205(10^9)  = 120954854741
A069205(10^10) = 1491898574939
A069205(10^11) = 17944730372827
A069205(10^12) = 212986333467973
A069205(10^13) = 2498962573520227
A069205(10^14) = 28874142998632109

# A002819(n) = Sum_{k=1..n} (-1)^bigomega(k)
# See also: A090410

A002819(10^1) = 0
A002819(10^2) = -2
A002819(10^3) = -14
A002819(10^4) = -94
A002819(10^5) = -288
A002819(10^6) = -530
A002819(10^7) = -842
A002819(10^8) = -3884
A002819(10^9) = -25216
A002819(10^10) = -116026
A002819(10^11) = -342224
A002819(10^12) = -522626
A002819(10^13) = -966578
A002819(10^14) = -7424752

# A064608(n) = Sum_{k=1..n} 2^omega(k)
# See also: A180361

A064608(10^1)  = 23
A064608(10^2)  = 359
A064608(10^3)  = 4987
A064608(10^4)  = 63869
A064608(10^5)  = 778581
A064608(10^6)  = 9185685
A064608(10^7)  = 105854997
A064608(10^8)  = 1198530315
A064608(10^9)  = 13385107495
A064608(10^10) = 147849112851
A064608(10^11) = 1618471517571

# A174863(n) = Sum_{k=1..n} (-1)^omega(k)

A174863(10^1)  = -4
A174863(10^2)  = 14
A174863(10^3)  = 64
A174863(10^4)  = -16
A174863(10^5)  = -720
A174863(10^6)  = -1908
A174863(10^7)  = -1650
A174863(10^8)  = 10734
A174863(10^9)  = 53740
A174863(10^10) = 108654
A174863(10^11) = 195702

# A069201(n) = Sum_{k=1..n} mu(k)^2 * 2^omega(k)

A069201(10^1)  = 17
A069201(10^2)  = 211
A069201(10^3)  = 2825
A069201(10^4)  = 34891
A069201(10^5)  = 414813
A069201(10^6)  = 4808081
A069201(10^7)  = 54684335
A069201(10^8)  = 612868643
A069201(10^9)  = 6788951097
A069201(10^10) = 74492096539
A069201(10^11) = 810947010335
A069201(10^12) = 8769730440341

# A002321(n) = Sum_{k=1..n} (-1)^omega(k) * mu(k)^2 = Sum_{k=1..n} mu(k)
# See also: A084237

A002321(10^1) = -1
A002321(10^2) = 1
A002321(10^3) = 2
A002321(10^4) = -23
A002321(10^5) = -48
A002321(10^6) = 212
A002321(10^7) = 1037
A002321(10^8) = 1928
A002321(10^9) = -222
A002321(10^10) = -33722
A002321(10^11) = -87856

# A013928(n) = Sum_{k=1..n} mu(k)^2
# See also: A071172

A013928(10^1)  = 7
A013928(10^2)  = 61
A013928(10^3)  = 608
A013928(10^4)  = 6083
A013928(10^5)  = 60794
A013928(10^6)  = 607926
A013928(10^7)  = 6079291
A013928(10^8)  = 60792694
A013928(10^9)  = 607927124
A013928(10^10) = 6079270942
A013928(10^11) = 60792710280