2
$\begingroup$

Given a fixed $p \in \{3,4,5,\ldots\}$, we define the strictly increasing sequence $\{a_k\}_{k\in \mathbb N}$ as follows. We set $a_{p,1}=1$ and for each $k>1$, we set $a_{p,k}$ to be the least integer strictly greater than $a_{p,k-1}$ such that $$a_{p,k}=b_1+b_2+\ldots+b_p$$ for some $\{b_j\}_{j=1}^{p} \subset \{a_{p,1},\ldots,a_{p,k-1}\}$.

For example, it is clear that $a_{p,2}=p$ and $a_{p,3}=2p-1$, $a_{p,4}=3p-2$,...

My question is whether there is a strictly increasing sequence $\{p_\ell\}_{\ell\in \mathbb N}\subset \{3,4,\ldots\}$ such that the following statement holds: There are infinitely many $j\in \mathbb N$ that do not belong to any $\{a_{p_{\ell},k}\}_{k=1}^{\infty}$ for all $\ell\in \mathbb N$.

$\endgroup$

1 Answer 1

4
$\begingroup$

Unless I'm confused, this is true. The key fact is that your sequences are just infinite arithmetic progressions, i.e. $a_{p,k} = 1 + (p-1)(k-1)$ for all $p,k$.

We can prove this formula by strong induction on $k$: clearly $a_{p,1} = 1$ by definition. Assume that $a_{p,k} = 1 + (p-1)(k-1)$ for $k < K$. Then all $a_{p,k}$ for $k < K$ are equal to $1 \pmod{p-1}$, so by definition, $a_{p,K}$ is the sum of $p$ integers equal to $1 \pmod{p-1}$ and must itself equal $1 \pmod{p-1}$. Therefore, $a_{p,K} \geq 1 + (p-1)(K-1)$, since this is the smallest integer greater than $a_{p,K-1} = 1 + (p-1)(K-2)$ equal to $1 \pmod{p-1}$.

But clearly $a_{p,K} \leq 1 + (p-1)(K-1)$, since we can write $1 + (p-1)(K-1) = 1 + \cdots + 1 + 1 + (p-1)(K-2) = a_{p,1} + \cdots + a_{p,1} + a_{p,K-1}$. So, $a_{p,K} = 1 + (p-1)(K-1)$, completing the proof by induction.

But with this formula, we can just give a density argument for your question. Take any sequence $\{p_\ell\}$ for which $\sum_{\ell} (p_{\ell}-1)^{-1} < 1$. (For future reference, note that this implies $p_{\ell}/\ell \rightarrow \infty$.)

Then, for every $N$, the number of integers in $\{1, \ldots, N\} \cap \{a_{p_\ell,k}\}_k$ is at most $\lceil N/(p_{\ell}-1) \rceil \leq N/(p_{\ell} - 1) + 1$. Therefore,

$\frac{|\{1, \ldots, N\} \cap \{a_{p_\ell,k}\}_{\ell,k}|}{N} \leq N^{-1} \sum_{\ell \ s.t. \ p_\ell \leq N} (N/(p_{\ell} - 1) + 1) \leq \frac{L}{N} + \sum_{\ell} (p_{\ell} - 1)^{-1} $,

where $L$ is the maximal $\ell$ so that $p_{\ell} \leq N$. As $N$ approaches infinitely, the final term approaches $\sum_{\ell} (p_{\ell} - 1)^{-1} < 1$, since $L/N \rightarrow 0$ by the fact noted for future reference above.

The limiting density of positive integers in $\{a_{p_\ell,k}\}_{\ell,k}$ is strictly less than $1$, so clearly there are infinitely many positive integers not in this set. (In fact, you can make the limiting proportion of positive integers in the set as small as desired, but not zero, since the set contains an infinite arithmetic progression.)

$\endgroup$
1
  • $\begingroup$ For the second part: if all the $p_i$ are odd, then all the terms in the sequences are odd as well. $\endgroup$ Commented Nov 26, 2022 at 12:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .