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

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$.

## migrated from mathoverflow.netJan 19 '15 at 3:16

This question came from our site for professional mathematicians.

• This really isn't research level, but you can get a very elegant solution by splitting $[0,1]$ into intervals of length $p_k$ and taking multiples of any irrational number mod 1. – Eric Wofsey Jan 18 '15 at 19:13
• @Eric: Can you explain a bit more? I split [0,1] into those intervals and choose any irrational number $\alpha$. After that what is x_n? – Ritwik Jan 18 '15 at 20:39
• Eric means the following: let $(I_k)_{k=1}^\infty$ be a sequence of pairwise disjoint intervals whose union is equal to $[0,1]$, and such that each interval $I_k$ has length $p_k$. Let $\alpha \in \mathbb{R}\setminus \mathbb{Q}$. Define $x_k:=p_n$ if and only if the fractional part of $k\alpha$ belongs to $I_n$. The property which you require then follows from Weyl's Criterion on equidistributed sequences. – Ian Morris Jan 18 '15 at 22:05
• @Ian: Thank you, thats clear now. This is actually the sort of answer I was looking for (i.e. there is some starting seed and then the rest of the numbers are generated from the seed). – Ritwik Jan 19 '15 at 3:39

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.

• I don't think this is what OP wants, because you only gave an example for single specific choice of $p_k$. – Wojowu Jan 18 '15 at 10:21
• When Ritwik wrote "you can choose whatever $p_k$ you want" I took that to mean that all that was wanted was a solution for a particular $p_k$, not for a general $p_k$, but I could be wrong. – user24142 Jan 18 '15 at 10:24
• Ah, okay, I didn't read the last part of a question. – Wojowu Jan 18 '15 at 10:25
• @Wojowu: Bill is correct; I wanted the answer for a specific $p_k$. – Ritwik Jan 18 '15 at 11:41

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$.

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.

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)$