Bounds for the sequence $a(n,A)=n*a(\lfloor (1-A)n \rfloor,A)$ Related to this question and possibly the open problem
of the exponential time hypotheses.
Let $A$ be rational number, $0 < A < 1$.
For positive integer $n$, define the sequence
$a(1,A)=1$ and $(n,A)=n *a(\lfloor (1-A) n\rfloor,A)$.
What are asymptotics and upper bounds for $a(n,A)$?
We are especially interested in finding out when it is that $a(n,A)$ is $\exp(o(n))$,
small oh on purpose.
Related OEIS sequence suggests
the growth is closely to $n^{\log{n}}$.
Based on numerical evidence, we conjecture that solution will be of the form
$$\lim_{n \to \infty}{\frac{\log a(n,A)}{\log{n^{\log{n}}}}}.$$
for all $A$.
 A: Define the sequence $n_k$ via the recursive formula $n_0=n$ and $n_{k+1}=\lfloor(1-A)n_k \rfloor$. As $0<A<1$, the sequence is decreasing. Let $M$ be the largest solution of inequality $n_M\geq 1$. First of all, by the definition of $a(n,A)$ we have
$$
\ln a(n_k,A)=\ln n_k+\ln a(n_{k+1},A),
$$
therefore
$$
\ln a(n,A)=\sum_{k\leq M}\ln n_k.
$$
Let us now study the asymptotics of $n_k$. By the definition of the floor function, for all $k$ there is some constant $0\leq \theta_k<1$ with
$$
n_{k+1}=(1-A)n_k-\theta_k.
$$
Applying this formula several times we see that
$$
n_k=n(1-A)^k-\theta_0(1-A)^{k-1}-\theta_1(1-A)^{k-2}-\ldots-\theta_{k-1}.
$$
Since the geometric series converges, we get
$$
n_k=n(1-A)^k+O\left(\frac{1}{A}\right),
$$
where the constant in $O$ is absolute (in fact, always at most $1$). This means, first of all, that for $k\leq M$ we have
$$
\ln n_k=\ln(n(1-A)^k+O_A(1))=\ln n+k\ln(1-A)+O_A\left(\frac{(1-A)^{-k}}{n}\right).
$$
Hence
$$
\ln a(n,A)=\sum_{k\leq M}(\ln n+k\ln(1-A)+O\left(\frac{(1-A)^{-k}}{n}\right))=
$$
$$
M\ln n+\frac{M^2+M}{2}\ln(1-A)+O\left(\frac{1}{n}\sum_{k\leq M}(1-A)^{-k}\right).
$$
The sum in $O$ can be estimated by the largest term, so it is $O(n^{-1}(1-A)^M)=O(1)$. We are left with the question on asymptotics of $M$.
Now, by definition of $M$, we have $1\leq n_M<\frac{1}{1-A}$. This means that the quantity
$$
n(1-A)^M
$$
is bounded from above and from below (because the $O(1/A)$ term is always non-positive), hence
$$
M=-\frac{\ln n}{\ln(1-A)}+O(1).
$$
This means that for $n\to +\infty$ we have
$$
\ln a(n,A)\sim \alpha(A)\ln^2 n=\alpha(A)\ln n^{\ln n},
$$
where
$$
\alpha(A)=\frac{1}{2\ln^2(1-A)}-\frac{1}{\ln(1-A)}.
$$
EDIT: The last formula should actually be
$$
\alpha(A)=-\frac{1}{2\ln(1-A)},
$$
I missed the $\ln(1-A)$ factor.
