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
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 ### 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
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
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
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
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
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
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
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
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?
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)
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.