prime_omega_function_generalized.pl

#!/usr/bin/perl

# Author: Daniel "Trizen" Șuteu
# Date: 25 November 2018
# https://github.com/trizen

# Generalization of the prime omega functions `ω_m(n)` and `Ω_m(n)`, for `m>=0`:
#
#     ω_m(n) = n^m * Sum_{p|n} 1/p^m
#
# and:
#
#     Ω_m(n) = Sum_{p^k|n} Sum_{j=1..k} n^m / p^(j*m)
#            = Sum_{p^k|n} n^m * (p^(m*k) - 1) / (p^m - 1) / p^(m*k)
#

# Where we have the following identities:
#   ω(n) = ω_0(n)
#   Ω(n) = Ω_0(n)

# See also:
#   https://oeis.org/A069359
#   https://oeis.org/A322068
#   https://en.wikipedia.org/wiki/Prime_omega_function
#   https://trizenx.blogspot.com/2018/11/partial-sums-of-arithmetical-functions.html

use 5.020;
use strict;
use warnings;

use experimental qw(signatures);
use ntheory qw(factor_exp vecsum);

sub omega ($n, $m) {
    vecsum(map { $n**$m / $_->[0]**$m } factor_exp($n));
}

sub bigomega ($n, $m) {
    vecsum(
        map {
            my $p = $_;
            vecsum(map { $n**$m / $p->[0]**($_ * $m) } 1 .. $p->[1])
        } factor_exp($n)
    );
}

foreach my $k (0 .. 5) {
    say "ω_$k(n) = [", join(', ', map { omega($_, $k) } 1 .. 25), "]";
    say "Ω_$k(n) = [", join(', ', map { bigomega($_, $k) } 1 .. 25), "]\n";
}

__END__
ω_0(n) = [0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 2, 1, 2, 1]
Ω_0(n) = [0, 1, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2]

ω_1(n) = [0, 1, 1, 2, 1, 5, 1, 4, 3, 7, 1, 10, 1, 9, 8, 8, 1, 15, 1, 14, 10, 13, 1, 20, 5]
Ω_1(n) = [0, 1, 1, 3, 1, 5, 1, 7, 4, 7, 1, 13, 1, 9, 8, 15, 1, 17, 1, 19, 10, 13, 1, 29, 6]

ω_2(n) = [0, 1, 1, 4, 1, 13, 1, 16, 9, 29, 1, 52, 1, 53, 34, 64, 1, 117, 1, 116, 58, 125, 1, 208, 25]
Ω_2(n) = [0, 1, 1, 5, 1, 13, 1, 21, 10, 29, 1, 61, 1, 53, 34, 85, 1, 121, 1, 141, 58, 125, 1, 253, 26]

ω_3(n) = [0, 1, 1, 8, 1, 35, 1, 64, 27, 133, 1, 280, 1, 351, 152, 512, 1, 945, 1, 1064, 370, 1339, 1, 2240, 125]
Ω_3(n) = [0, 1, 1, 9, 1, 35, 1, 73, 28, 133, 1, 307, 1, 351, 152, 585, 1, 953, 1, 1189, 370, 1339, 1, 2483, 126]

ω_4(n) = [0, 1, 1, 16, 1, 97, 1, 256, 81, 641, 1, 1552, 1, 2417, 706, 4096, 1, 7857, 1, 10256, 2482, 14657, 1, 24832, 625]
Ω_4(n) = [0, 1, 1, 17, 1, 97, 1, 273, 82, 641, 1, 1633, 1, 2417, 706, 4369, 1, 7873, 1, 10881, 2482, 14657, 1, 26209, 626]

ω_5(n) = [0, 1, 1, 32, 1, 275, 1, 1024, 243, 3157, 1, 8800, 1, 16839, 3368, 32768, 1, 66825, 1, 101024, 17050, 161083, 1, 281600, 3125]
Ω_5(n) = [0, 1, 1, 33, 1, 275, 1, 1057, 244, 3157, 1, 9043, 1, 16839, 3368, 33825, 1, 66857, 1, 104149, 17050, 161083, 1, 289619, 3126]