41 votes
Accepted

Wrong asymptotics of OEIS A000607 (number of partitions of an integer in prime parts)?

Your data is compatible with the more refined estimates proved by Vaughan in Ramanujan J. 15 (2008), 109–121. His Theorems 1 and 2 (together with his (1.9)) reveal that $$\log(A000607(n)) = 2 \pi \...
22 votes
Accepted

The coupon collector's earworm

For the asymptotic case: Let $t_1=n \log n - Cn$ and $t_2 = n \log n + Cn$, where $C$ is slowly tending to infinity. It is a classic result that as $C$ tends to infinity the probability all coupons ...
22 votes

A new way of approaching the pole of the Riemann zeta function - and a new conjectured formula

The paper entitled Euler constant as a renormalized value of Riemann zeta function at its pole by Andrei Vieru contains a derivation of the first formula in the OP (Benoȋt Cloitre's formula), and ...
19 votes
Accepted

Asymptotic expansion of $\sum\limits_{n=1}^{\infty} \frac{x^{2n+1}}{n!{\sqrt{n}} }$

I sketch the arguments for $C(x)$, the arguments for $L(x)$ are essentially the same. The specific form of the sum suggests probabilistic arguments. Let $X_x$ be a $\mathrm{Poiss}(x^2)$-distributed ...
  • 2,945
16 votes

A new way of approaching the pole of the Riemann zeta function - and a new conjectured formula

The first formula is trivial. $$f(s)= \frac1{s-1}+\gamma +O(s-1)$$ $$g(z)=1+2^{-z}+3^{-z}+4^{-z}+O(5^{-z})=1+2^{-z}(1+(3/2)^{-z}+(4/2)^{-z}+O(5/2)^{-z})$$ $$f(g(z)) = \frac1{2^{-z}(1+(3/2)^{-z}+(4/2)^...
  • 2,979
16 votes
Accepted

How does the number of trees on $n$ vertices *up to isomorphism* grow as $n \to \infty$?

For Q1 the answer is known to be $\sim C_1C_2^n n^{-5/2} $ for $C_1\approx 0.5349496061...$ and $C_2\approx 2.9955765856...$. This can be found in Flajolet and Sedgewick's "Analytic Combinatorics&...
16 votes
Accepted

Density of the set of numbers whose sum of digits is prime

Yes, $A(n)$ has zero natural density. It suffices to prove this for $n$ which is a power of $10$. and it is possible to make this more precise. To see this, first let $n=10^k$ and note that for $X$ ...
  • 12.9k
15 votes
Accepted

Cubic-exponential enumerative combinatorics

Since you mentioned Cayley's theorem for spanning trees, I believe one important example is its higher dimensional analogue due to Kalai. Indeed the number of simplicial spanning trees of the k-...
15 votes
Accepted

Distinct exponents in the factorization of the factorial, a problem of Erdős

The primes $p \leq \sqrt{n}$ can be ignored as the number of them is $$\approx \sqrt{n} / \log (\sqrt{n} )= 2 \sqrt{n}/\log n = o (1) \cdot \sqrt { n/\log n}$$ For primes $p> \sqrt{n}$, the ...
  • 119k
14 votes
Accepted

Probability that a positive integer is the euler phi function of another positive integer

See Erick Wong's response here. In particular, Kevin Ford proved (in more precise form) that $$ f(n) = \frac{n}{\log n} \exp\left(O(\log \log \log n)^2\right),$$ whence $f(n)/n$ tends to zero. The ...
14 votes
Accepted

Asymptotic behavior of $\sum_{k=1}^{\infty} \sqrt{\max\{1 - k^2/x^2,0\}}$ as $x\to\infty$

Use the Euler-MacLaurin formula, $$\sum_{k=1}^\infty F(k)=\int_0^\infty F(k)\,dk+\tfrac{1}{2}[F(\infty)-F(0)]+\int_0^\infty (k-\text{Int}\,[k]-\tfrac{1}{2})F'(k)\,dk.$$ In this case $F(k)=\sqrt{\max\{...
13 votes
Accepted

What is (approximately) the expected value of $X\log{ X}$ where $X$ is binomial (or Poisson)?

$\newcommand{\ep}{\varepsilon} $ Let $X$ be any nonnegative random variable (r.v.) with finite mean $\mu>0$ and variance $\sigma^2<\infty$. For any real $u>0$, we have $\ln\frac xu\le\frac xu-...
12 votes
Accepted

Asymptotics of product of Euler's totient function (A001088)?

We may just write down $\varphi(k)=k\cdot \prod_{p|k} (1-1/p)$, $p$ runs over the primes which divide $k$, then $$ \frac{\left(\prod_{k\leqslant n}\varphi(k)\right)^{1/n}}{n}=\frac{\sqrt[n]{n!}}n\...
  • 90.4k
12 votes
Accepted

Asymptotics of a special function

Gradshteyn & Ryzhik equation 3.773.1 gives (for $q>0$) $$\frac{1}{q}B(q)=\int_0^\infty \frac{\sin x}{x(q^2/4+x^2)^{1/2}}\,dx=\frac{1}{q}G^{21}_{13}\left(\frac{q^2}{16}\biggl|^1_{1/2,1/2,0}\...
12 votes
Accepted

About the logarithmic derivative of the Riemann zeta function

I think your final goal follows by taking the logarithmic derivative of the functional equation: $$\frac{\zeta'}{\zeta}(s)+\frac{\zeta'}{\zeta}(1-s)=\log\pi-\frac{1}{2}\frac{\Gamma'}{\Gamma}\left(\...
12 votes
Accepted

The number of representations of an integer as the inner product of integral lattice points

The asymptotic formula is true for even dimensions $k\geq 2$. We can prove this by induction on $k$, inspired by Rodrigo's observation on Eisenstein series. The case $k=2$ is classical and addressed ...
12 votes
Accepted

On approximation of $\sum_{a,b=1}^n\gcd(a,b)$

The asymptotic you want does not hold just because the "last-term fluctuation" $$ g(n)-g(n-1) = 2\sum_{a=1}^n \gcd(a,n)-n $$ is too large. Indeed, denoting the sum in the right-hand side by $\sigma(...
  • 21.8k
12 votes

What is the asymptotic of the irregular blue curve? Is it $(8x)^{1/2}$ or is it something else?

Let us denote the left hand side of $(1)$ by $\psi(x)$. It is known that $|\psi(x)-x|$ is not bounded by a constant times $x^{1/2}$. In fact Littlewood (1914) proved that $$\psi(x)-x=\Omega_{\pm}(x^{1/...
12 votes
Accepted

Prove or disprove that $\sup_{n\in\mathbb{N}}\left|\sum_{\substack{d|n \\d<Q}}\mu(d)\right|\sim\pi(Q)$

This is not true. In fact $$ x(\log x)^{-1+1/\pi} \gg \sup_n \Big| \sum_{\substack{ d|n \\ d\le x}} \mu(d) \Big| \gg x (\log x)^{-1+1/\pi}. $$ The upper bound is due to Montgomery and Vaughan (see ...
  • 42.6k
12 votes
Accepted

Is there a real-analytic way to derive the asymptotics of $\int_{-\infty}^\infty e^{ikx} e^{-k^4}\,dk$ as $|x|\to\infty$?

A differential equation for ${\cal A} (x) $ can be obtained as follows, $$ \frac{d^3}{dx^3 } {\cal A} (x) = \int_{-\infty }^{\infty } dk\, (-ik^3 ) e^{ikx} e^{-k^4 } = \frac{x}{4} \int_{-\infty }^{\...
11 votes
Accepted

Maximum of the Vandermonde determinant / minimum of the logarithmic energy

Write $V(a)$ for the determinant $\prod_{0\leq i<j\leq n-1} |a_i-a_j|$. Selberg's formula tells you that $$\int_0^1 \cdots \int_0^1 V(a)^{2\beta} \prod_{i=0}^{n-1} da_i= n! \prod_{j=0}^{n-1} \frac{...
11 votes
Accepted

Asymptotics of a recurrence relation

It is not hard prove the bounds you want by purely real variable techniques. First note that the $a_n$ are non-negative for all $n$. For a general non-negative sequence $a_n$, and real numbers $N>...
  • 42.6k
11 votes
Accepted

For a round-robin tournament, what is the favorite's least favorite size?

I can show that $N(\epsilon)$ is equal to $\epsilon^{-2}$ up to a log factor on each side. The strategy I'll use is to give an upper bound for $\pi(1/2+\epsilon,n)$. Optimizing it, we obtain an upper ...
  • 119k
11 votes
Accepted

Differentiating an integral that grows like log asymptotically

The answer is no, even in the smooth case. Take for example: $$ f(x) = \frac{2}{x} + \frac{\cos(\log(x))}{x} $$ Alter it on a small neighborhood of $0$ in such a way that there is no singularity ...
  • 3,023
11 votes
Accepted

Asymptotic of integral $\int_{1}^{e^n}(1-\frac{\ln(x)}{n})^n\,dx$

Denote $t=\ln(x)/n$, then $t$ varies from 0 to 1 and the the integral reads as $$n\int_0^1 ((1-t) e^{t})^ndt.$$ We have $(1-t)e^t=(1-t)(1+t+t^2/2+\ldots)=1-t^2/2+O(t^3)=\exp(-t^2/2+O(t^3))$ for small $...
  • 90.4k
11 votes
Accepted

How hard is it to say "not exactly $p$" with a Horn sentence?

I will show how to improve Tulipani’s construction from $O(p^5)$ symbols to $O(p^3)$ symbols, or $O(p^3\log p)$ bits. Recall that Tulipani’s sentence is $$H_p=\forall\vec x\,\exists\vec s\,\exists\vec ...
11 votes
Accepted

Asymptotics for $\int\exp( -x t / \log t)dt$

Denote $t/\log t=y$. Then $y$ increases from $e$ to $\infty$ when $x$ goes from $e$ to $\infty$, and $dt(1/\log t-1/\log^2 t)=dy$, thus $dt\sim \log t\cdot dy\sim \log y\cdot dy$ for large $t$ (since $...
  • 90.4k
11 votes

Asymptotics for $\int\exp( -x t / \log t)dt$

Take any real $a>e$. Then \begin{equation*} f(x)=f_{1,a}(x)+f_{2,a}(x), \tag{1}\label{1} \end{equation*} where \begin{equation*} f_{1,a}(x):=\int_e^a dt\,e^{-xg(t)},\quad f_{2,a}(x):=\...
10 votes
Accepted

Bound on sum of complex summands involving binomial coefficients

Assuming that $|x+y|<1$ and $4|xy| \le 1$, here's a proof of the decay. First suppose that $|x|> |y|$. The desired sum is $$ \le \binom{2n}{n} |xy|^n \sum_{j=0}^{n} |y/x|^j \le \binom{2n}{...
  • 42.6k
10 votes

Asymptotics of a recurrence relation

Let $A(x)$ denote the formal generating function of $\{ a_n\}$. The recurrence relation can be written as $A(x)=e^x A(x^2)$. Applying this repeatedly, we find $A(x) = e^x e^{x^2} \cdots = e^{f(x)}$, ...

Only top scored, non community-wiki answers of a minimum length are eligible