<p>Given an ordered array of distinct prime numbers <span class="math-container">$p_{i, 1 \le i \le n}$</span> and a number <span class="math-container">$m$</span>, can you calculate the <span class="math-container">$m$</span>th natural number generated by <span class="math-container">$p$</span>? I need something optimized preferably logarithmic but it can also be linear.</p>
<p>For example given the array of primes <span class="math-container">$[2, 5, 7]$</span> the first 6 numbers generated by it are:
<span class="math-container">$[2, 2^2, 5, 7, 2^3, 2 \cdot 5]$</span>.</p>

CC BY-SA 4.0
2022-06-13T16:44:32.947Z
This is basically equivalent to the following task: given $\alpha_1,\dots,\alpha_n$ and $\beta$, count the number of values of the form $k_1 \alpha_1 + \dots + k_n \alpha_n$ that are $\le \beta$, such that $k_1,\dots,k_n \in \mathbb{N}$.  (Simply take $\alpha_i=\log p_i$ and $\beta=\log m$.)  This is a special case of counting the number of lattice points in a polytope, which can be done in polynomial time in fixed dimension (and here we are working in one dimension), so perhaps there is some hope for a solution to your problem.
D.W.
CC BY-SA 4.0
2022-06-26T08:29:08.330Z
I don't know if it's quite equivalent to @D.W.'s example ... $\beta$ is not known beforehand - the question asks for an $i^{th}$ item. Seems like all such numbers can be generated up to some $\beta$ (for sufficiently large $\beta$ but then these need to be stored in some data structure that supports maintaining a sorted collection (or just generate all the values unsorted and apply a solution of $k^{th}$-smallest element, like O(n)-time median-finding)
JimN
<primes>
How to generate arbitrarily in-order from a set of primes?
Marc Grec
# How to generate arbitrarily in-order from a set of primes?

(Asked by: username_0 on 2022-06-13)

Given an ordered array of distinct prime numbers $p\_{i, 1 \le i \le n}$ and a number $m$, can you calculate the $m$th natural number generated by $p$? I need something optimized preferably logarithmic but it can also be linear.

For example given the array of primes $[2, 5, 7]$ the first 6 numbers generated by it are:
$[2, 2^2, 5, 7, 2^3, 2 \cdot 5]$.

**Tags:** primes
> **Comments:**
> **username_1**: This is basically equivalent to the following task: given $\alpha_1,\dots,\alpha_n$ and $\beta$, count the number of values of the form $k_1 \alpha_1 + \dots + k_n \alpha_n$ that are $\le \beta$, such that $k_1,\dots,k_n \in \mathbb{N}$.  (Simply take $\alpha_i=\log p_i$ and $\beta=\log m$.)  This is a special case of counting the number of lattice points in a polytope, which can be done in polynomial time in fixed dimension (and here we are working in one dimension), so perhaps there is some hope for a solution to your problem.  
> **username_2**: I don't know if it's quite equivalent to @D.W.'s example ... $\beta$ is not known beforehand - the question asks for an $i^{th}$ item. Seems like all such numbers can be generated up to some $\beta$ (for sufficiently large $\beta$ but then these need to be stored in some data structure that supports maintaining a sorted collection (or just generate all the values unsorted and apply a solution of $k^{th}$-smallest element, like O(n)-time median-finding)  

---

## 0 answers

