A question about a function $q(b)$

Question

User Mathphile invented the function $\ q(b)\ $ which is defined as the sum of the values $ \lfloor \frac bj \rfloor$ for $j=1,\cdots ,b$ without duplicates.

Example : The values for $b=11$ are $[11, 5, 3, 2, 2, 1, 1, 1, 1, 1, 1]$ , without duplicates we have $[1, 2, 3, 5, 11]$ , the sum is $22$ , hence $q(11)=22$

In PARI/GP $q(b)$ can be calculated with

f(b)=vecsum(Set(vector(b,j,b\j)))

I have two conjectures :

• $q(b)$ is strictly increasing
• For $b\ge 2$ : $q(b) = q(b-1) + 1$ holds , if and only if $b$ is an odd prime.

$q(1)=1$ , $q(2)=3$, hence the claim is true for $b=2$

If $b>2$, we have $\lfloor \frac{b}{b-1} \rfloor=1$ , hence the fraction for $j=b$ is a duplicate, hence does not prolong the set.

If $b$ is an odd prime, the fractions for $j=2,\cdots, b-1$ coincide for $b-1$ and $b$ , since $\frac{b}{j}$ is never an integer. For $j=1$, the fraction increases from $b-1$ to $b$. Hence the sum increases by $1$. This shows one direction of the claim.

It remains to show that the sum increases by more than $1$ in the case of a composite number , which would also show that $q(b)$ is strictly increasing. How can I do that ?

Answer 1

Let us denote $k=[\sqrt{b}]$.

If $k^2\leq b<k(k+1)$, then $q(b)=\sum_{i=1}^{k-1}i+\sum_{j=1}^k [b/j]$.

If $k(k+1)\leq b<(k+1)^2$, then $q(b)=\sum_{i=1}^ki+\sum_{j=1}^k [b/j]$.

So if $b=k^2$, then $$q(b)-q(b-1)=k+\sum_{d|b,d<k} 1=k+(\tau(b)-1)/2.$$

If $b=k(k+1)$, then $$q(b)-q(b-1)=k+\sum_{d|b,d\leq k} 1=k+\tau(b)/2.$$

Otherwise, $$q(b)-q(b-1)=\sum_{d|b,d<\sqrt{b}} 1=\tau(b)/2.$$

In any case, we can see confirmation for both your hypoteses.

Answer 2

If $b$ is composite integer then for $ 1\leq j\leq [\sqrt{b}]$ we have that $[\frac{b}{j}] > [\frac{b}{j+1}]$ because $\frac{b}{j}-\frac{b}{j+1}\geq 1$ which is true for all $1 \leq j \leq [-0.5+0.5 \sqrt{1+4b}] \leq [\sqrt{b}]$, so for $j=1,2,3,\cdots, [\sqrt{b}]$ and we have that $[\frac{b}{j}]\geq [\frac{b-1}{j}]$ and its strictly bigger when $j|b$ and we have at least two cases $j=1,a$ when $b$ is composite integer.

Let $ [\sqrt{b}]< j \leq b-1$ since $[\frac{b}{b-1}]=1 = [\frac{b}{b}]$ for all $b\geq 3$

If $b|j$ then $[\frac{b}{j}] > [\frac{b-1}{j}]$ if $\frac{b}{j}$ is repeated for the $q(b)$ series and $\frac{b}{j}-1$ is new for $q(b-1)$ this might make $q(b-1)>q(b)$, but we will prove that if this is the case then $[\frac{b}{j+1}]= [\frac{b-1}{j+1}] = \frac{b}{j}-1$ which is to prove that $ \frac{b}{j} > \frac{b}{j+1},\frac{b-1}{j+1} \geq \frac{b}{j}-1$ which is true for all $ j \geq \sqrt{b} $ and we are done.

Note : we always have $j+1$ if we extended the sum for infinity and knowing that $[\frac{b}{j}]=[\frac{b-1}{j}]=0 $ for $j\geq b+1$( to make the proof more rigorous)