123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124 |
- #!/usr/bin/perl
- # Three sublinear algorithms for computing the sum of prime powers <= n,
- # based on the sublinear algorithm for computing the sum of primes <= n.
- # See also:
- # https://oeis.org/A074793
- use 5.036;
- use Math::GMPz;
- use ntheory qw(:all);
- use Math::Prime::Util::GMP qw(faulhaber_sum);
- sub sum_of_primes ($n, $k = 1) { # Sum_{p prime <= n} p^k
- return sum_primes($n) if ($k == 1); # optimization
- $n > ~0 and return undef;
- $n <= 1 and return 0;
- my $r = sqrtint($n);
- my @V = map { divint($n, $_) } 1 .. $r;
- push @V, CORE::reverse(1 .. $V[-1] - 1);
- my $t = Math::GMPz::Rmpz_init_set_ui(0);
- my $u = Math::GMPz::Rmpz_init();
- my %S;
- @S{@V} = map { Math::GMPz::Rmpz_init_set_str(faulhaber_sum($_, $k), 10) } @V;
- foreach my $p (2 .. $r) {
- if ($S{$p} > $S{$p - 1}) {
- my $cp = $S{$p - 1};
- my $p2 = $p * $p;
- Math::GMPz::Rmpz_ui_pow_ui($t, $p, $k);
- foreach my $v (@V) {
- last if ($v < $p2);
- Math::GMPz::Rmpz_sub($u, $S{divint($v, $p)}, $cp);
- Math::GMPz::Rmpz_submul($S{$v}, $u, $t);
- }
- }
- }
- $S{$n} - 1;
- }
- sub sum_of_prime_powers ($n) {
- # a(n) = Sum_{p prime <= n} p
- # b(n) = Sum_{p prime <= n^(1/2)} p^2
- # c(n) = Sum_{p prime <= n^(1/3)} f(p)
- # sum_of_prime_powers(n) = a(n) + b(n) + c(n)
- my $ps1 = sum_of_primes($n);
- my $ps2 = sum_of_primes(sqrtint($n), 2);
- # f(p) = (Sum_{k=1..floor(log_p(n))} p^k) - p^2 - p
- # = (p^(1+floor(log_p(n))) - 1)/(p-1) - p^2 - p - 1
- my $ps3 = 0;
- foreach my $p (@{primes(rootint($n, 3))}) {
- $ps3 += divint(powint($p, logint($n, $p) + 1) - 1, $p - 1) - $p * $p - $p - 1;
- }
- return vecsum($ps1, $ps2, $ps3);
- }
- sub sum_of_prime_powers_2 ($n) {
- # a(n) = Sum_{p prime <= n} p
- # b(n) = Sum_{p prime <= n^(1/2)} f(p)
- # sum_of_prime_powers(n) = a(n) + b(n)
- my $ps1 = sum_of_primes($n);
- # f(p) = (Sum_{k=1..floor(log_p(n))} p^k) - p
- # = (p^(1+floor(log_p(n))) - 1)/(p-1) - p - 1
- my $ps2 = 0;
- forprimes {
- $ps2 += divint(powint($_, logint($n, $_) + 1) - 1, $_ - 1) - $_ - 1;
- } sqrtint($n);
- return vecsum($ps1, $ps2);
- }
- sub sum_of_prime_powers_3 ($n) {
- # a(n) = Sum_{k=1..floor(log_2(n))} Sum_{p prime <= n^(1/k)} p^k.
- vecsum(map { sum_of_primes(rootint($n, $_), $_) } 1 .. logint($n, 2));
- }
- foreach my $n (0 .. 10) {
- say "a(10^$n) = ", sum_of_prime_powers(powint(10, $n));
- }
- foreach my $k (1 .. 100) {
- my $n = int(rand(1e3)) + 1;
- my $x = sum_of_prime_powers($n);
- my $y = sum_of_prime_powers_2($n);
- my $z = sum_of_prime_powers_3($n);
- $x == $y or die "error";
- $x == $z or die "error";
- }
- __END__
- a(10^0) = 0
- a(10^1) = 38
- a(10^2) = 1375
- a(10^3) = 82674
- a(10^4) = 5850315
- a(10^5) = 457028152
- a(10^6) = 37610438089
- a(10^7) = 3204814813355
- a(10^8) = 279250347324393
- a(10^9) = 24740607755154524
- a(10^10) = 2220853189506845580
- a(10^11) = 201467948093608962539
- a(10^12) = 18435613572072500152927
|