How to enumerate/count the numbers of a particular form below N in an efficient way?

Primes, divisors, arithmetic, number properties, ...
Post Reply
castrate
Posts: 17
Joined: Mon Aug 19, 2019 2:34 pm

How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by castrate »

For a sorted array of integers L={$a_1,a_2,...,a_k$}(Eg. L=[3,3,2,2,1]), consider numbers n which can be factored in the form:
$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}$, where $p_1, p_2,..., p_k$ are distinct primes.

Let E(L, N) be the enumerating function of all numbers n, not exceeding N, which has the prime factorization form given by L, and C(L, N) be the counting function of those numbers.

For example:
E({2,1}, 100)={12, 18, 20, 28, 44, 45, 50, 52, 63, 68, 75, 76, 92, 98, 99}
C({2,1}, 100)=15
E({2,2,1},1000)={180, 252, 300, 396, 450, 468, 588, 612, 684, 700, 828, 882, 980}
C([2,2,1], 1000)=13

For trivial or specific cases, such as L={1,1,1,1} or L={2,1}, it is easy to come up with an efficient algorithm(I have a recursive algorithm for L={1,1,1,1}). But for more general and complicated cases like E({5,5,3},$10^{18}$), it really beats me. Could anyone give me some hints to an efficient approach? The algorithm for E(L,N) and C(L,N) is useful in many PE problems. Thanks :D
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by pjt33 »

I think you are already familiar with inclusion-exclusion, fast evaluation of the prime counting function, and sums of Dirichlet convolutions. Just put them together...
castrate
Posts: 17
Joined: Mon Aug 19, 2019 2:34 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by castrate »

Thanks for your advice, but how may Dirichlet convolution work in this problem? I'm still new to that concept and its applications.
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by pjt33 »

The sums involved are of the form $\sum_{k=1}^N f(k)\, g(\lfloor\tfrac{n}{k}\rfloor)$ where $f,g$ are indicator functions for $E(?,N)$.
castrate
Posts: 17
Joined: Mon Aug 19, 2019 2:34 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by castrate »

Sorry, I don't fully understand your method. Is your $f(k)$, $g(\lfloor \dfrac n k \rfloor )$ equivalent to C(..., k) and C(..., $\lfloor \dfrac n k \rfloor$) as I described above?
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by pjt33 »

No, they're indicator functions $I_L(n) = C(L, n) - C(L, n-1)$.
castrate
Posts: 17
Joined: Mon Aug 19, 2019 2:34 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by castrate »

Got it, but can this implementation compute C(L,N) efficiently? For example, for the case C({5,5,3},$10^{18}$), we need an $O(N^{1/3})$ approach, and for the case C({7,7,5},$10^{30}$),we need an $O(N^{1/5})$ approach.
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by pjt33 »

castrate wrote: Sat Sep 05, 2020 3:59 am Got it, but can this implementation compute C(L,N) efficiently? For example, for the case C({5,5,3},$10^{18}$), we need an $O(N^{1/3})$ approach, and for the case C({7,7,5},$10^{30}$),we need an $O(N^{1/5})$ approach.
I'm not quite sure why $O(\sqrt[\min(a_i)]{N})$ is the cutoff for "efficient".

Looking at both theoretical and empirical asymptotics, with a tuned Python implementation timed with the python3 executable (not pypy3) and perf_counter:

L = (5,5,3), times with far more precision than is justified:
$$\begin{align}
a\quad & \quad C(L, 10^a) \quad & secs \\
18\quad & \quad 21583 \quad & 0.070889 \\
20\quad & \quad 85042 \quad & 0.1722676 \\
22\quad & \quad 338768 \quad & 0.423248 \\
24\quad & \quad 1368575 \quad & 1.0821172 \\
26\quad & \quad 5602937 \quad & 2.7531969 \\
28\quad & \quad 23227987 \quad & 7.1780077 \\
30\quad & \quad 97357633 \quad & 18.6326169
\end{align}$$
Theoretical asymptotics are $O(N^{1/5})$; trend line is $\Theta(N^{\sim 0.202})$.

L = (7,7,5), ditto:
$$\begin{align}
a\quad & \quad C(L, 10^a) \quad & secs \\
30\quad &\quad 55234 \quad & 0.2966877 \\
32\quad &\quad 126864 \quad & 0.5474201 \\
34\quad &\quad 291824 \quad & 1.0065869 \\
36\quad &\quad 672424 \quad & 1.8919887 \\
38\quad &\quad 1553904 \quad & 3.6109696 \\
40\quad &\quad 3602041 \quad & 6.9154236 \\
42\quad &\quad 8378870 \quad & 12.6932378 \\
44\quad &\quad 19561905 \quad & 23.7022166
\end{align}$$
Theoretical asymptotics are $O(N^{782/5475}) \approx O(N^{0.1428})$; trend line is $\Theta(N^{\sim 0.137})$.

NB I'm not entirely surprised if some empirical exponents are slightly better than the theoretical ones, because in my theoretical analysis I drew the line at trying to take into account caching of subcomputations.
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by pjt33 »

Actually, I'm now curious about:
castrate wrote: Thu Sep 03, 2020 2:13 pm For trivial or specific cases, such as L={1,1,1,1} or L={2,1}, it is easy to come up with an efficient algorithm(I have a recursive algorithm for L={1,1,1,1}).
My technique gives theoretical asymptotics of $O(N^{23/24})$ for $\{1,1,1,1\}$, which doesn't really seem practical. Does your recursive approach have better asymptotics?
castrate
Posts: 17
Joined: Mon Aug 19, 2019 2:34 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by castrate »

My algorithm for {1,1,1,...,1} takes roughly O(N). By saying "efficient" here I mean to enumerate numbers of that form without brute force. In other words, an $O(\sqrt[\min(L)]N)$ implementation is efficient enough for me. (Of course, your $O(\sqrt[\max(L)]N)$ approach is much better)
pjt33
Posts: 56
Joined: Mon Oct 06, 2008 6:14 pm

Re: How to enumerate/count the numbers of a particular form below N in an efficient way?

Post by pjt33 »

Maybe worth a quick note, then, that a basic sieve can enumerate all squarefree numbers, grouping them by number of prime factors, in $\tilde O(n)$ time.
Post Reply