Skip to content

Powerful Number Sieve

Definition

The powerful number (PN) sieve is similar to Du's sieve, or rather an extension of it. It computes prefix sums of certain multiplicative functions.

Requirements:

  • There is a function \(g\) such that:
    • \(g\) is multiplicative.
    • Prefix sums of \(g\) are easy to compute.
    • \(g(p) = f(p)\) for every prime \(p\).

Suppose we want the prefix sum \(F(n) = \sum_{i=1}^{n} f(i)\) of a multiplicative function \(f\).

Powerful numbers

Definition: Let \(n = \prod_{i=1}^{m} p_{i}^{e_{i}}\) be the prime factorization of a positive integer \(n\). Then \(n\) is a PN if and only if \(\forall 1 \le i \le m, e_{i} > 1\).

Property 1: Every PN can be written in the form \(a^{2}b^{3}\).

Proof: If \(e_i\) is even, merge \(p_{i}^{e_{i}}\) into \(a^{2}\). If \(e_i\) is odd, first merge \(p_{i}^{3}\) into \(b^{3}\), then merge \(p_{i}^{e_{i}-3}\) into \(a^{2}\).

Property 2: There are at most \(O(\sqrt{n})\) PNs up to \(n\).

Proof: Enumerate \(a\) and count the values of \(b\) that fit. The number of PNs is approximately

\[ \int_{1}^{\sqrt{n}} \sqrt[3]{\frac{n}{x^2}} \mathrm{d}x = O(\sqrt{n}) \]

How do we find all the PNs up to \(n\)? Find all primes up to \(\sqrt{n}\) with a linear sieve, then run a DFS over the exponents of these primes. Since there are at most \(O(\sqrt{n})\) PNs up to \(n\), the search takes at most \(O(\sqrt{n})\) steps.

The PN sieve

First, construct a multiplicative function \(g\) whose prefix sums are easy to compute and which satisfies \(g(p) = f(p)\) for every prime \(p\). Let \(G(n) = \sum_{i=1}^{n} g(i)\).

Next, construct the function \(h = f / g\), where \(/\) denotes division under Dirichlet convolution. By the properties of Dirichlet convolution, \(h\) is also multiplicative, so \(h(1) = 1\). We have \(f = g * h\), where \(*\) denotes Dirichlet convolution.

For a prime \(p\), \(f(p) = g(1)h(p) + g(p)h(1) = h(p) + g(p) \implies h(p) = 0\). Since \(h(p)=0\) and \(h\) is multiplicative, \(h(n) = 0\) for every \(n\) that is not a PN. In other words, \(h\) takes useful values only at PNs.

Now \(f = g * h\) gives

\[ \begin{aligned} F(n) &= \sum_{i = 1}^{n} f(i)\\ &= \sum_{i = 1}^{n} \sum_{d|i} h(d) g\left(\frac{i}{d}\right)\\ &= \sum_{d=1}^{n} \sum_{i=1}^{\lfloor \frac{n}{d}\rfloor} h(d) g(i)\\ &= \sum_{d=1}^{n} h(d) \sum_{i=1}^{\lfloor \frac{n}{d}\rfloor} g(i) \\ &= \sum_{d=1}^{n} h(d) G\left(\left\lfloor \frac{n}{d}\right\rfloor\right)\\ &= \sum_{\substack{d=1 \\ d \text{ is PN}}}^{n}h(d) G\left(\left\lfloor \frac{n}{d}\right\rfloor\right) \end{aligned} \]

Find all the PNs in \(O(\sqrt{n})\) time and compute all the useful values of \(h\). For this it suffices to compute the values \(h(p^c)\): every useful value of \(h\) then follows because \(h\) is multiplicative. Finally, for each useful value \(d\), compute \(h(d)G\left(\left\lfloor \dfrac{n}{d} \right\rfloor\right)\); the sum of these terms is \(F(n)\).

There are two ways to compute \(h(p^c)\). The first is to derive a formula for \(h(p^c)\) that depends only on \(p\) and \(c\), and evaluate it. The second starts from \(f = g * h\), which gives \(f(p^c) = \sum_{i=0}^c g(p^i)h(p^{c-i})\). Rearranging, \(h(p^c) = f(p^c) - \sum_{i=1}^{c}g(p^i)h(p^{c-i})\), so enumerating the primes \(p\) and, for each, the exponents \(c\) yields every \(h(p^c)\).

Procedure

  1. Construct \(g\).
  2. Find a fast way to compute \(G\).
  3. Compute \(h(p^c)\).
  4. Search for the PNs, accumulating the answer along the way.
  5. Obtain the result.

Step 3 can be done in three ways: evaluate the formula directly, precompute a table by enumeration, or derive each value on the fly when the search first reaches it.

Properties

We analyze the case where \(h(p^c)\) is computed by the second method. The analysis has two parts: computing \(h(p^c)\), and the search.

For the first part, there are \(O\left(\dfrac{\sqrt{n}}{\log n}\right)\) primes up to \(O(\sqrt{n})\), the exponent \(c\) of each prime \(p\) is at most \(\log n\), and computing \(h(p^c)\) takes a loop of \((c - 1)\) iterations. The first part therefore runs in \(O\left(\dfrac{\sqrt{n}}{\log n} \cdot \log n \cdot \log n\right) = O(\sqrt{n}\log{n})\) time, and this is a loose upper bound. Depending on the problem, further optimizations can lower the time complexity of the first part.

For the search, there are at most \(O(\sqrt{n})\) PNs up to \(n\), so the search takes at most \(O(\sqrt{n})\) steps. The time spent on each PN depends on how \(G\) is computed. For example, if computing \(G\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)\) takes \(O(1)\) time, the second part runs in \(O(\sqrt{n})\).

In particular, if \(G\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)\) is computed with Du's sieve, the time complexity of the second part is that of Du's sieve, namely \(O(n^{\frac{2}{3}})\). The reason is this. Compute \(G(n)\) once beforehand, using the linear sieve optimization and storing the larger values in a data structure with fast random access (such as std::map and std::unordered_map in C++). Then every \(G\left(\left\lfloor \dfrac{n}{d}\right\rfloor\right)\) used during Du's sieve is already stored, either by the linear sieve or in the std::map. You can check this directly with a program.

The bottleneck of the space complexity is storing \(h(p^c)\). With a two-dimensional array \(a\) in which \(a_{i,j}\) holds the value of \(h(p_i^j)\), the space complexity is \(O\left(\dfrac{\sqrt{n}}{\log n} \cdot \log n\right) = O(\sqrt{n})\).

Example problems

Luogu P5325 [Template] Min_25 Sieve

Problem statement: Given the multiplicative function \(f(p^k) = p^k(p^k-1)\), compute \(\sum_{i=1}^{n} f(i)\).

Clearly \(f(p) = p(p-1) = \operatorname{id}(p)\varphi(p)\), so construct \(g(n) = \operatorname{id}(n)\varphi(n)\).

Compute \(G(n)\) with Du's sieve: \((\operatorname{id}\cdot \varphi) * \operatorname{id} = \operatorname{id}_2\) gives \(G(n)= \sum_{i=1}^{n} i^2 - \sum_{d=2}^{n} d \cdot G\left(\left\lfloor \dfrac{n}{d} \right\rfloor\right)\).

The values of \(h(p^k)\) can then be computed by enumeration; we do not go over that method again.

In this problem you can also derive a formula for \(h(p^k)\) that depends only on \(p\) and \(k\), as follows:

\[ \begin{aligned} & f(p^k) = \sum_{i=0}^{k} g(p^{k-i})h(p^i)\\ \iff & p^k(p^k-1) = \sum_{i=0}^{k} p^{k-i}\varphi(p^{k-i}) h(p^i)\\ \iff & p^k(p^k-1) = \sum_{i=0}^{k} p^{2k-2i-1}(p - 1) h(p^i)\\ \iff & p^k(p^k-1) = h(p^k) + \sum_{i=0}^{k-1} p^{2k-2i-1}(p - 1) h(p^i)\\ \iff & h(p^k) = p^k(p^k-1) - \sum_{i=0}^{k-1} p^{2k-2i-1}(p - 1) h(p^i)\\ \iff & h(p^k) - p^2h(p^{k-1}) = p^{k}(p^k-1)-p^{k+1}(p^{k-1}-1) - p(p-1)h(p^{k-1})\\ \iff & h(p^k) - ph(p^{k-1}) = p^{k+1} - p^k\\ \iff & \frac{h(p^k)}{p^k} - \frac{h(p^{k-1})}{p^{k-1}} = p - 1\\ \end{aligned} \]

Together with \(h(p) = 0\), summing these equations over the exponent gives \(h(p^k) = (k-1)(p-1)p^k\).

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <map>
using namespace std;

constexpr int MOD = 1e9 + 7;

template <typename T>
int mint(T x) {
  x %= MOD;
  if (x < 0) x += MOD;
  return x;
}

int add(int x, int y) { return x + y >= MOD ? x + y - MOD : x + y; }

int mul(int x, int y) { return (long long)1 * x * y % MOD; }

int sub(int x, int y) {
  return x < y ? x - y + MOD : x - y;  // avoid negative values
}

int qp(int x, int y) {
  int r = 1;
  for (; y; y >>= 1) {
    if (y & 1) r = mul(r, x);
    x = mul(x, x);
  }
  return r;
}

int inv(int x) { return qp(x, MOD - 2); }

namespace PNS {
constexpr int N = 2e6 + 5;
constexpr int M = 35;

long long global_n;

int g[N], sg[N];

int h[N][M];
bool vis_h[N][M];

int ans;

int pcnt, prime[N], phi[N];
bool isp[N];

void sieve(int n) {
  pcnt = 0;
  for (int i = 2; i <= n; ++i) isp[i] = true;  // array marking the primes
  phi[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (isp[i]) {
      ++pcnt;
      prime[pcnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= pcnt; ++j) {  // sieve out the non-primes
      long long nxt = (long long)1 * i * prime[j];
      if (nxt > n) break;
      isp[nxt] = false;
      if (i % prime[j] == 0) {  // the case where i is not prime
        phi[nxt] = phi[i] * prime[j];
        break;
      }
      phi[nxt] = phi[i] * phi[prime[j]];
    }
  }

  for (int i = 1; i <= n; ++i) g[i] = mul(i, phi[i]);

  sg[0] = 0;
  for (int i = 1; i <= n; ++i) sg[i] = add(sg[i - 1], g[i]);  // prefix sums of the function g
}

int inv2, inv6;

void init() {
  sieve(N - 1);
  for (int i = 1; i <= pcnt; ++i) h[i][0] = 1, h[i][1] = 0;
  for (int i = 1; i <= pcnt; ++i) vis_h[i][0] = vis_h[i][1] = true;
  inv2 = inv(2);
  inv6 = inv(6);
}

int S1(long long n) { return mul(mul(mint(n), mint(n + 1)), inv2); }

int S2(long long n) {
  return mul(mul(mint(n), mul(mint(n + 1), mint(n * 2 + 1))), inv6);
}

map<long long, int> mp_g;

int G(long long n) {
  if (n < N) return sg[n];
  if (mp_g.count(n)) return mp_g[n];

  int ret = S2(n);
  for (long long i = 2, j; i <= n; i = j + 1) {
    j = n / (n / i);
    ret = sub(ret, mul(sub(S1(j), S1(i - 1)), G(n / i)));
  }
  mp_g[n] = ret;
  return ret;
}

void dfs(long long d, int hd, int pid) {
  ans = add(ans, mul(hd, G(global_n / d)));

  for (int i = pid; i <= pcnt; ++i) {
    if (i > 1 && d > global_n / prime[i] / prime[i]) break;  // pruning

    int c = 2;
    for (long long x = d * prime[i] * prime[i]; x <= global_n;
         x *= prime[i], ++c) {  // compute the functions f and g
      if (!vis_h[i][c]) {
        int f = qp(prime[i], c);
        f = mul(f, sub(f, 1));
        int g = mul(prime[i], prime[i] - 1);
        int t = mul(prime[i], prime[i]);

        for (int j = 1; j <= c; ++j) {
          f = sub(f, mul(g, h[i][c - j]));
          g = mul(g, t);
        }
        h[i][c] = f;
        vis_h[i][c] = true;
      }

      if (h[i][c]) dfs(x, mul(hd, h[i][c]), i + 1);
    }
  }
}

int solve(long long n) {
  global_n = n;
  ans = 0;
  dfs(1, 1, 1);
  return ans;
}
}  // namespace PNS

int main() {
  PNS::init();
  long long n;
  cin >> n;
  cout << PNS::solve(n) << '\n';
  return 0;
}

LOJ #6053 Simple Function

The function \(f(n)\) is given by:

\[ f(n) = \begin{cases} 1 & n = 1 \\ p \oplus c & n=p^c \\ f(a)f(b) & n=ab \text{ and } a \perp b \end{cases} \]

Clearly:

\[ f(p) = \begin{cases} p + 1 & p = 2 \\ p - 1 & \text{otherwise} \\ \end{cases} \]

Construct \(g\) as

\[ g(n) = \begin{cases} 3 \varphi(n) & 2 \mid n \\ \varphi(n) & \text{otherwise} \\ \end{cases} \]

It is easy to verify that \(g(p) = f(p)\) and that \(g\) is multiplicative.

Now compute \(G(n)\).

\[ \begin{aligned} G(n) &= \sum_{i=1}^{n}[i \bmod 2 = 1] \varphi(i) + 3 \sum_{i=1}^{n}[i \bmod 2 = 0] \varphi(i)\\ &= \sum_{i=1}^{n} \varphi(i) + 2\sum_{i=1}^{n} [i \bmod 2 = 0]\varphi(i) \\ &= \sum_{i=1}^{n} \varphi(i) + 2\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor} \varphi(2i) \end{aligned} \]

Let \(S_1(n) = \sum_{i=1}^{n} \varphi(i)\) and \(S_2(n) = \sum_{i=1}^{n} \varphi(2i)\). Then \(G(n) = S_1(n) + 2S_2\left(\left\lfloor \dfrac{n}{2} \right\rfloor\right)\).

When \(2 \mid n\),

\[ \begin{aligned} S_2(n) &= \sum_{i=1}^{n} \varphi(2i) \\ &= \sum_{i=1}^{\frac{n}{2}} (\varphi(2(2i-1)) + \varphi(2(2i))) \\ &= \sum_{i=1}^{\frac{n}{2}} (\varphi(2i-1) + 2\varphi(2i)) \\ &= \sum_{i=1}^{\frac{n}{2}} (\varphi(2i-1) + \varphi(2i)) + \sum_{i=1}^{\frac{n}{2}} \varphi(2i) \\ &= \sum_{i=1}^{n} \varphi(i) + S_2\left(\frac{n}{2}\right)\\ &= S_1(n) + S_2\left(\left\lfloor \frac{n}{2} \right\rfloor\right)\\ \end{aligned} \]

When \(2 \nmid n\),

\[ \begin{aligned} S_2(n) &= S_2(n-1) + \varphi(2n) \\ &= S_2(n-1) + \varphi(n) \\ &= \sum_{i=1}^{n-1} \varphi(i) + S_2\left(\frac{n-1}{2}\right) + \varphi(n)\\ &= S_1(n) + S_2\left(\left\lfloor \frac{n}{2} \right\rfloor\right)\\ \end{aligned} \]

In both cases, \(S_2(n) = S_1(n) + S_2\left(\left\lfloor \dfrac{n}{2} \right\rfloor\right)\).

Compute \(S_1\) with Du's sieve and \(S_2\) directly from this formula. This gives \(G\) as well.

Reference code
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <iostream>
#include <map>
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr int inv2 = (MOD + 1) / 2;

template <typename T>
int mint(T x) {
  x %= MOD;
  if (x < 0) x += MOD;
  return x;
}

int add(int x, int y) {
  return x + y >= MOD ? x + y - MOD : x + y;  // keep the result below the modulus
}

int mul(int x, int y) { return (long long)1 * x * y % MOD; }

int sub(int x, int y) {
  return x < y ? x - y + MOD : x - y;  // avoid negative values
}

namespace PNS {
constexpr int N = 2e6 + 5;
constexpr int M = 35;

long long global_n;

int s1[N], s2[N];

int h[N][M];
bool vis_h[N][M];

int ans;

int pcnt, prime[N], phi[N];
bool isp[N];

void sieve(int n) {
  pcnt = 0;
  for (int i = 2; i <= n; ++i) isp[i] = true;  // array marking the primes
  phi[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (isp[i]) {
      ++pcnt;
      prime[pcnt] = i;
      phi[i] = i - 1;
    }
    for (int j = 1; j <= pcnt; ++j) {  // sieve out the non-primes
      long long nxt = (long long)1 * i * prime[j];
      if (nxt > n) break;
      isp[nxt] = false;
      if (i % prime[j] == 0) {  // the case where i is not prime
        phi[nxt] = phi[i] * prime[j];
        break;
      }
      phi[nxt] = phi[i] * phi[prime[j]];
    }
  }

  s1[0] = 0;
  for (int i = 1; i <= n; ++i) s1[i] = add(s1[i - 1], phi[i]);

  s2[0] = 0;
  for (int i = 1; i <= n / 2; ++i) {
    s2[i] = add(s2[i - 1], phi[2 * i]);
  }
}

void init() {
  sieve(N - 1);
  for (int i = 1; i <= pcnt; ++i) h[i][0] = 1;
  for (int i = 1; i <= pcnt; ++i) vis_h[i][0] = true;
}

map<long long, int> mp_s1;

int S1(long long n) {
  if (n < N) return s1[n];
  if (mp_s1.count(n)) return mp_s1[n];

  int ret = mul(mul(mint(n), mint(n + 1)), inv2);
  for (long long i = 2, j; i <= n; i = j + 1) {
    j = n / (n / i);
    ret = sub(ret, mul(mint(j - i + 1), S1(n / i)));
  }
  mp_s1[n] = ret;
  return ret;
}

map<long long, int> mp_s2;

int S2(long long n) {
  if (n < N / 2) return s2[n];
  if (mp_s2.count(n)) return mp_s2[n];
  int ret = add(S1(n), S2(n / 2));
  mp_s2[n] = ret;
  return ret;
}

int G(long long n) { return add(S1(n), mul(2, S2(n / 2))); }

void dfs(long long d, int hd, int pid) {
  ans = add(ans, mul(hd, G(global_n / d)));

  for (int i = pid; i <= pcnt; ++i) {
    if (i > 1 && d > global_n / prime[i] / prime[i]) break;  // pruning

    int c = 2;
    for (long long x = d * prime[i] * prime[i]; x <= global_n;
         x *= prime[i], ++c) {
      if (!vis_h[i][c]) {
        int f = prime[i] ^ c, g = prime[i] - 1;

        // special-case p = 2
        if (i == 1) g = mul(g, 3);

        for (int j = 1; j <= c; ++j) {
          f = sub(f, mul(g, h[i][c - j]));
          g = mul(g, prime[i]);
        }
        h[i][c] = f;
        vis_h[i][c] = true;
      }

      if (h[i][c]) dfs(x, mul(hd, h[i][c]), i + 1);
    }
  }
}

int solve(long long n) {
  global_n = n;
  ans = 0;
  dfs(1, 1, 1);
  return ans;
}
}  // namespace PNS

int main() {
  PNS::init();  // preprocessing function
  long long n;
  cin >> n;
  cout << PNS::solve(n) << '\n';
  return 0;
}

Practice problems

References