Using $\color{darkorange}{\rm UF}$ = universal property of floor, i.e. $\ k\le \lfloor r\rfloor\!\!\iff\! k\le r;\ $ $\ \color{#90f}{k \le -\lfloor r\rfloor\!\!\iff\! k\!-\!1< -r},\ $
the proof reduces to trivial algebra, i.e. apply $\,\lfloor(r\!-\!12)/3\rfloor^{\phantom{|^|}}\!\!\! = \lfloor r/3\rfloor - 4\,$ followed by below.
$\begin{align} {\bf Theorem}\ \quad \lfloor \color{#0a0}{\tfrac{1}{25}(8n+3)}\rfloor &= \lfloor \tfrac{1}{3}(n - \lfloor(n-17)/25\rfloor)\rfloor,\ \ {\rm for}\ \ n\in\Bbb Z\\[.4em]
{\bf Proof}\ \ {\rm for}\ \ k\in\Bbb Z\!:\ \ \qquad k&\ \le\, \tfrac{1}{3}(n - \lfloor(n-17)/25\rfloor)\\[.2em]
\iff\ 3k-n&\,\le\,\ \ \ \ \ \ \ -\lfloor(n-17)/25\rfloor\\[.3em]
\iff\ 3k-n &\,\le\, (-n+41)/25,\ \ {\rm by\ Lemma\ below}\\[.3em]
\smash[t]{\overset{\times\ 25}\iff}\ \ \ \ \ \ \ \ 75k &\,\le\,\ 24n+41\\[.3em]
\smash[t]{\overset{\div\,3}\iff}\ \ \ \ \ \ \ \,25k &\,\le\ \ \ 8n+ 13,\ \ {\rm by}\ \ 25k\in\Bbb Z\\[.2em]
\iff\qquad\ \ \ k &\,\le \color{#0a0}{\tfrac{1}{25}(8n+3)}
\end{align}$
Lemma $\ \ \ \ \color{#90f}{j \,\le\, -\lfloor a/b\rfloor}\iff j\!\color{darkorange}{-\!1}\le (-a\!\color{darkorange}{-\!1})/b,\ \ {\rm for}\,\ \color{#c00}{b>0}\,$ (wlog), $\,a,b\in\Bbb Z$
Pf: $
\overset{\rm\color{darkorange}{UF}}\iff\! \color{#90f}{j\!-\!1 < {-}a/b}\!\!\underset{\color{#c00}{\times\ b}}\iff\! b(j\!\color{darkorange}{-\!1})\!\,\le -a\!\color{darkorange}{-\!1}\ $ [by $\ m<n\!\iff m\le n\!\color{darkorange}{-\!1}$]
The required condition is that $$\left\lfloor\frac{n}{2^{k+1}}\right\rfloor=0$$
This is only true if
$$0\leq n<2^{k+1}\iff k > \log_2\left(\frac{n}{2}\right)$$
Best Answer
From the well known $$x-1<\lfloor x\rfloor \leq x \tag{1}$$ Thus $$\frac{1+na^2}{a}-1< \left\lfloor \frac{1+na^2}{a}\right\rfloor\leq \frac{1+na^2}{a}$$ and $$n<n+\frac{1}{a^2}< \frac{1+\left\lfloor \frac{1+na^2}{a}\right\rfloor}{a}\leq n+\frac{1}{a^2}+\frac{1}{a}\tag{2}$$
Finally, for $\color{red}{a>\phi}$ $$\frac{1}{a}+\frac{1}{a^2} <\frac{2}{1+\sqrt{5}}+\frac{4}{(1+\sqrt{5})^2}= \frac{2+2\sqrt{5}+4}{(1+\sqrt{5})^2}\\ =\frac{6+2\sqrt{5}}{6+2\sqrt{5}}=1$$ and from $(2)$ $$n< \frac{1+\left\lfloor \frac{1+na^2}{a}\right\rfloor}{a}< n+1\tag{3}$$ the result follows from $(3)$.
The corner case for $\color{red}{a=\phi}$ leads to $$\left\lfloor \frac{1+n\phi^2}{\phi}\right\rfloor= \left\lfloor \frac{\sqrt{5}-1}{2}+n\cdot\frac{\sqrt{5}+1}{2}\right\rfloor=\\ \left\lfloor (n+1)\cdot\frac{\sqrt{5}}{2}+\frac{n+1}{2}-1\right\rfloor= \left\lfloor (n+1)\cdot\frac{\sqrt{5}+1}{2}-1\right\rfloor=\\ \left\lfloor (n+1)\cdot\phi-1\right\rfloor < ...$$ because $\phi$ is irrational, thus $(n+1)\cdot\phi-1$ can never be an integer $$...< (n+1)\cdot\phi-1$$ Then $(2)$ becomes $$n< \frac{1+\left\lfloor \frac{1+n\phi^2}{\phi}\right\rfloor}{\phi}< n+1$$
I wanted to make it a short answer, but the corner case and the explanatory notes spoiled the effort.