Page 1 of 1

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

Posted: Thu Sep 03, 2020 2:13 pm
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

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

Posted: Thu Sep 03, 2020 11:12 pm
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...

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

Posted: Fri Sep 04, 2020 4:16 am
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.

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

Posted: Fri Sep 04, 2020 8:08 am
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)$.

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

Posted: Fri Sep 04, 2020 1:16 pm
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?

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

Posted: Fri Sep 04, 2020 6:56 pm
by pjt33
No, they're indicator functions $I_L(n) = C(L, n) - C(L, n-1)$.

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

Posted: Sat Sep 05, 2020 3:59 am
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.

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

Posted: Mon Sep 07, 2020 5:44 pm
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.

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

Posted: Wed Sep 09, 2020 8:51 am
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?

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

Posted: Fri Sep 11, 2020 5:00 am
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)

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

Posted: Mon Sep 14, 2020 8:21 am
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.