Counting how many natural numbers satisfy a given condition.

Question

I've defined a sequence of sequences $\{x^n\}$ as follows

$x^1=(1^2,2^2,3^2,4^2,5^2,...)$

$x^2=(1,2^2,3^2,4^2,5^2,....)$

$x^3=(1,2,3^2,4^2,5^2,...)$

.

and for each $n$ fixed, I am trying to determine $|\{j: x^n_{j} \leq k\}|$. In other words, for a sequence $x^n$, if I look at the term $x^n_{k}$, I want to calculate how many terms of the sequence satisfy $x^n_{j} \leq k$.

If $k \geqslant n^2$, there are $\lfloor \sqrt{k}\rfloor$ terms, otherwise $\min{n-1,k}$. — Daniel Fischer, Nov 17 '13 at 16:08
I got that estimate just for the sequence $x^1$, I was trying to understand what happens with $x^n$ for an arbitrary $n$, thanks. — user100106, Nov 17 '13 at 16:11
More precisely, if $k<0$ then $0$, if $0\le k<n^2$ then $\min(n-1, \lfloor k\rfloor)$, if $k\ge n^2$ then $\lfloor \sqrt k\rfloor$. — peterwhy, Nov 17 '13 at 16:14

Ross Millikan · Answer 1 · 2013-11-17T16:40:03.443

1

Hint: Note that as long as you are in the squares, you have the same number of terms. The term $p^2$ is the $p^{\text{th}}$ term. If you are in the first powers, $q$ is the $q^{\text{th}}$ term. When are you in each regime?

edited Nov 17 '13 at 16:40

answered Nov 17 '13 at 16:15

Ross Millikan

374,822

Counting how many natural numbers satisfy a given condition.

1 Answers1