0
$\begingroup$

Denote this function as ${a}_{l}$. Here $p$ is prime but not necessary for the solution, just $p \ge 2$ is needed. This solution is for fixed $p$ with $N$ allowed to vary. Now a plot of this function shows that it oscillates until sufficiently large $N$. That is $\lim_{N\rightarrow \infty} {a}_{l} = p+1$. Also the square root term of ${a}_{l}$ establishes that $N\ge 2p(2p-1)$.

The problem is to show that the first occurrence of the global minimum of $p+1$ occurs at $N=p(p^2+p+1)$. From this value of $N$ I can show that the global minimum is $p+1$. I am interested in proving this case because this value of $N$ is a special value of the more general set of problems that I am working on.

I have tried taking the derivative of the ${a}_{l}$ with respect to $k$ with the floor functions dropped where $N\ge p*k$ or $N < (k+1)p$ from $k \le N/p < k+1$. The problem is that when set to zero to find the max/min the variable $k$ vanishes. I have also considered setting the first derivative to be less than zero and solving for $k$. This results in $N=2p(2p-1)$ which is a local max/min.

$\endgroup$
0
$\begingroup$

OK take $N=p*w$ where $w=\lfloor{N/p}\rfloor$. Set ${a}_{l} = p+1$. Then we have $$\lfloor{(1/2)(w+3-2(p+1)-\sqrt{(w+1)^2-4*p*w})}\rfloor$$ Call this function inside the floor function ${a}_{l}^{\prime}$. Then we have the condition from the floor function $0\le {a}_{l}^{\prime} < 1$. Solving for $w$ results in $w>p^2+p$ for $p\ge 2$. Thus the first valid integer solution is $w = p^2+p+1$ or $N=p(p^2+p+1)$. Substitution into the original problem indeed shows that $p+1$ is the global minimum with the first value at $N=p(p^2+p+1)$.

Once could also assume that $N = p*w+v$ where $v=N \text{ mod } p$ where $v \in \left\{{0,1,\cdots, p-1}\right\}$. Then you get $w>p^2+p+v$ where the again the first solution occurs only when $v=0$.

$\endgroup$

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.