For a natural number $n$ and non-negative integers $i,j$ I want to evaluate:


For this, I need to know how many possible combinations of $i$ and $j$ can give a certain value $k$, but I can't find any solution. Where $n$ is some natural number constant and $i$ and $j$ can get any non-negative integer value. Obviously, $k{\geq}n$ or $k=0$.

I've played a little with the numbers, and I reached the expression $\left\lfloor\frac{k}{2^n}\right\rfloor+1$ which seems to be an upper limit on the value, but I can't prove it analytically, see graph below.

enter image description here

Number indicates the value of $n$, "upper lim" is the graph of $\left\lfloor\frac{k}{2^n}\right\rfloor+1$


Since $$k=n(i+j)+j\iff \frac{k-ni}{n+1}=j$$ for any given $k$ and $n$, the maximum possible value of $j$ occurs when $i=0$ and it is $\frac{k}{n+1}$.

Since $j$ must be a nonnegative integer, it follows that $j$ will lie in $\{0,1,2,\dots,\left\lfloor \frac{k}{n+1}\right \rfloor\}$.

We perform the substitution $p=i+j$. It will suffice to find the number of pairs of values of $p$ and $j$ s.t. $k=np+j$. Since $k$ is fixed, it is enough that we find the number of possible values of $p$ (for which constraints on both $p$ and $j$ are satisfied).

Since $j\in \{0,1,2,\dots,\left\lfloor \frac{k}{n+1}\right \rfloor\}$, $k-j\in \{k,k-1,k-2,\dots,k-\left\lfloor\frac{k}{n+1}\right\rfloor\}$. But $k-j=np$ assuming that $j$ and $p$ satisfy the equation.

This means that the number of possible values of $p$ (i.e. the number of pairs of values for $i$ and $j$) equals the number of multiples of $n$ in $\{k,k-1,k-2,\dots,k-\left\lfloor\frac{k}{n+1}\right\rfloor\}$.

This gives us that the number of pairs of values of $i$ and $j$ satisfying the conditions (for nonzero $k$) is $$\left\lfloor\frac{k}{n}\right\rfloor-\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor-1}{n}\right\rfloor$$

I think this can be simplified to $$\left\lfloor\frac{k}{n}\right\rfloor-\left\lfloor\frac{k-1}{n+1}\right\rfloor$$

(I'm not entirely sure why this is well-bounded by $\left\lfloor\frac{k}{2^n}\right\rfloor$+1, but I did notice that the 'number-of-pairs' function grows very slowly with $k$ - perhaps the large denominator of $2^n$ is a significant limiting factor in the size of $\left\lfloor\frac{k}{2^n}\right\rfloor$+1, rendering its growth comparable to that of the 'number-of-pairs' function initially but for very large values the upper bound and the function grow disparate.)

Note: If there's anything wrong or confusing in my answer, feel free to edit it (and comment please) or just comment

| cite | improve this answer | |
  • $\begingroup$ Where does the $-1$ in $\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor-1}{n}\right\rfloor$ come from? $\endgroup$ – SIMEL Jan 30 at 22:39
  • $\begingroup$ Say it was just $\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor}{n}\right\rfloor$. In $\left\lfloor\frac{k}{n}\right\rfloor-\left\lfloor\frac{k-\left\lfloor\frac{k}{n+1}\right\rfloor}{n}\right\rfloor$, we'd be subtracting the no. of multiples of $n+1$ $\leq k-\left\lfloor\frac{k}{n+1}\right\rfloor$ from the no. that are $\leq k$. But this means that even if $k-\left\lfloor\frac{k}{n+1}\right\rfloor$ was a multiple of $n$ it wouldn't be counted, even though the interval $\{k,k-1,k-2,\dots,k-\left\lfloor\frac{k}{n+1}\right\rfloor\}$ contains $k-\left\lfloor\frac{k}{n+1}\right\rfloor$ $\endgroup$ – Cardioid_Ass_22 Jan 31 at 11:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.