Can one generate a sequence of natural numbers whose density has a given distribution?

Question

Suppose $\{ p_{k} \}$ is a collection of real numbers with the following properties:

1) $p_k \in (0,1)$ $~~~~$(i.e. $0$ and $1$ are not allowed values)

2) $\sum_{k=1}^{\infty} p_k =1$

An example of such a collection is $p_k := \frac{6}{\pi^2 k^2}$. You are free to choose any such collection in order to answer the following question:

Can you generate a sequence of natural numbers $\{x_n\}$ with the following property: $$ \lim_{N \rightarrow \infty}\frac{\#\{n \in [1,N]: x_n = k \}}{N} = p_k \qquad \forall k.$$

My criteria for "generating" a sequence means I should actually be able write a program to generate these $\{x_n\}$. I am not looking for an abstract existential result; ideally the $x_n$ should be given by an explicit formula.

To clarify my question; you can choose whatever $p_k$ you want to answer my question, as long as it satisfies conditions $1)$ and $2)$. You can take the specific example $p_k := \frac{6}{\pi^2 k^2}$ I gave, but that is not necessary. Again, the only condition is that given $k$ I should actually be able to evaluate $p_k$; it should not be something that is given indirectly or which is merely shown to exist theoretically. Ideally, $p_k$ should be a formula in terms of $k$.

Answer 1

Let $p_k = 1/2^k$ and $x_k = n$ if $k = 2^{n-1}(2m - 1)$ for some integer $m>0$. I believe this works.

Answer 2

Let me provide an algorithm for arbitrary $\ (p_k)$.

Let $\ (p_k: k=1\ 2\ \ldots)\ $ be an arbitrary sequence of positive real numbers $\ p_k>0\ $ such that $\ \sum_{k=1}^\infty p_k=1.\ $ Then define $\ x_n\ $ as the smallest natural number $\ x_n=k\ $ such that:

$$\frac 1n\cdot \left|\{m<n:x_m=k\}\right|\ \ <\ \ p_k$$

(This indeed is an algorithm rather than a closed formula).

REMARK   This would work even for a little more general (weaker) assumption $\ p_k\ge 0$.

Answer 3

Another example is the following:
Let $p_k=\frac{1}{s_k}$ where $s_k$ denotes the $k$-th term of the Sylvester sequence.

It is well known that the sum of its reciprocals converges to $1$, and of course $p_k=\frac{1}{s_k}\in (0,1)$

Answer 4

Bill J's example from above admits a simple generalization. Consider an arbitrary integer $\ a>1.\ $ Let

• $\ \forall_{k=1\ 2\ \dots}\ \ p_k := \frac{a-1}{a^k}$
• $\ \forall_{k\ n=1\ 2\ \ldots}\ \ \left(x_n:=k\quad\Leftarrow:\Rightarrow\quad a^{k-1}\, |\, n\not\equiv 0 \mod a^k\right)$

REMARK   The above example, including the one by Bill J, is a special case of my general algorithm above.