6
(This is more like a comment with images)
Here are some simulations of the values $c = c(p)$ using the grid of size $1000\times1000$ and $500$ steps together with some fitting curves.
$\hspace{8em}$
The data clearly deviates from the polynomial $2p^2$, and although the above plot may seem to suggest that $c(p)$ assumes a nice closed form, I believe that ...
3
Seems fine but it is easier to note that
$$
n+1\leq 2n
$$
for $n\geq 1$ whence
$$
(n+1)^3\leq (2n)^3=8n^3
$$
for $n\geq 1$ as desired.
2
By the most recent bound on Linnik's Theorem, there is an absolute constant $c$ such that for every prime $q < cp_n^{1/5}$, there is a prime $p < p_n$ such that $p \equiv 1 \pmod{q}$. Your least common multiple is therefore divisible by all primes below $cp_n^{1/5}$. The prime number theorem implies that the product of all primes below $cp_n^{1/5}$ is $...
2
Your differential equation has closed-form solutions
$$ \eqalign{f \left( t \right) &=c_{{1}}{t}^{1/2-a/2}{{ J}_{-\sqrt {{a}^{2}-2\,a
+4\,b+1}}\left(2\,{\frac {\sqrt {b\epsilon}}{\sqrt {t}}}\right)}\cr &+c_{{2
}}{t}^{1/2-a/2}{{ Y}_{-\sqrt {{a}^{2}-2\,a+4\,b+1}}\left(2\,{\frac
{\sqrt {b\epsilon}}{\sqrt {t}}}\right)}}
$$
where $J$ and $Y$ are Bessel ...
1
Here is a key lemma (which you can and should prove for yourself) that helps to resolve so many questions of this type. I'll phrase it in terms of functions of $x$ where $x\to\infty$, although it holds for other domains as well.
Lemma: Let $f,g\colon [1,\infty)\to[2,\infty)$ be functions. If $\log f(x) = o(\log g(x))$ as $x\to\infty$, then $f(x) = o(g(x))$ ...
1
$\log((1/n) + n^2 )$
If we just focus on the term inside of the logarithm.
$ let x = 1/n + n^2$
As n grows, we notice that the 1/n term effectively becomes zero and the overpowering term is $n^2$
We can now state that $\log((1/n) + n^2 )$ has growth $log(n^2)$ when n gets large.
We know from logarithms that $log(a^b) = b* log(a)$
So $log(n^2)$ can be ...
1
Yes it does. Let $t_N$ denote the algorithm time. Let $f_N = \max\{t_M/M^2:M\le N\}$. Suppose $f_N$ diverges. Then $t_N$ fails to be $O(\sqrt{f_N} N^2)$. Therefore $f_N$ does not diverge. Since $f_N$ is a non-decreasing sequence, it must be bounded. Set $C= \sup f_N$. Then $t_N \le C N^2$.
Only top voted, non community-wiki answers of a minimum length are eligible
