This may help in finding a solution: Note that we can always find a polynomial $P_k(x)$ of degree $k-1$ and with integer coefficients such that $xP_k(x)=P_k(x-1)+x^k+r_k$, where $r_k$ is some residual constant to be determined; just express $P_k(x)=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\dots+c_1x+c_0$, and work the coefficients down from $c_{k-1}$ to $c_0$, finding the coefficient $c_m$ by comparing the terms of degree $m+1$ at both sides of the equation. Clearly $c_{k-1}=1$, and all other coefficients are a linear combination with integral weights of higher-order coefficients, hence the polynomial coefficients are all integral. The residual constant $r_k$ is the one that makes the constant term in the RHS equal to zero, and is also clearly integral. Note now that a sequence as described in the problem statement exists for $k$ iff $r_k=0$; indeed, if $r_k=0$, take $a_n=P_k(n)$ for $n\geq0$, and we got the right sequence, whereas is the sequence exists, define $d_n=P_k(n)-a_n$, or $d_n=\frac{d_{n-1}+r_k}{n}$. After trivial induction, we find that $d_n=\frac{d_0}{n!}+r_k\frac{0!+1!+\dots+(n-1)!}{n!}$. Take now $n$ large enough that $\left|\frac{d_0}{n!}\right|<\frac{1}{2}$, and $|r_k|\frac{0!+1!+\dots+(n-1)!}{n!}<\frac{1}{2}$ (*), and since $d_n$ is clearly integral, then $d_n=0$, and since the same applies to $n+1$ because it is even larger, then $d_n=d_{n+1}=0$, yielding $r_k=0$. (*) It can be shown by induction that for $n\geq4$, $\frac{0!+1!+\dots+(n-1)!}{n!}<\frac{1}{\sqrt{n}}$, or it suffices to take $n>4r_k^2$. Once we have all this, it suffices to show that if $r_k=0$, then $k\equiv2\pmod 3$, which can probably obtained as follows: note that $P_1(x)=1$ and $r_1=-1$, $P_2(x)=x+1$ and $r_2=0$, and $P_3(x)=x^2+x-1$ and $r_3=1$, but after this $r_k$ increases rapidly in absolute value, with parity odd,even,odd,odd,even,odd,odd,even,odd,... or we may postulate that $r_k$ is even iff $k\equiv2\pmod3$; if we manage to prove that, then we are done... Somebody cares to finish it? Note: I have worked $r_k$ for $k=2,5,8,11$, but it is only zero for $k=2$, yielding sequence $a_n=n+1$, clearly satisfying the condition in the problem statement, hence I'd settle just for proving the parity of $r_k$, since it is clearly false that $r_k=0$ for all $k\equiv2\pmod3$...

Lemma 1: If there exist integers $k$ and $c$ such that $n! | (1! + 2! + \cdots + (n-1)!) k + c$, then $k = c = 0$. Proof: Suppose for the sake of contradiction that $k \neq 0$. We may assume without loss of generality that $k > 0$. It is obvious that for sufficiently large $n$, \begin{align*} k(1! + 2! + \cdots + (n-1)!) + c &< 1 \cdot 1! + 2 \cdot 2! + \cdots + (n-1)! \cdot (n-1)! \\ &= (2! - 1!) + (3! - 2!) + \cdots + (n! - (n-1)!) \\ &= n! - 1 < n! \end{align*} which is a contradiction. Lemma 2: $n(n+k)! = (n+k+1)! - (k+1)(n+k)!$. Proof: \begin{align*} n(n+k)! &= (n+k)(n+k)! - k(n+k)! \\ &= (n+k+1)! - (n+k)! - k(n+k)! \\ &= (n+k+1)! - (k+1)(n+k)!. \end{align*} Lemma 3: Let $\left \{ \begin{matrix} n \\ k \end{matrix} \right \}$ denote the number of ways to partition $n$ objects into $k$ groups (a Stirling number of the second kind.) Then \[n^{k} n! = \sum_{i=0}^{k} \left\{\begin{matrix} k+1 \\ i+1 \end{matrix}\right\} (-1)^{i+k} (n+i)!. \] Proof: We will use induction and lemma 2. The base case, $k=0$, is trivial. Suppose the result is true for all integers less than some $k > 0$ now. Then \begin{align*} n^{k+1} n! &= \sum_{i=0}^{k} \left\{\begin{matrix} k+1 \\ i+1 \end{matrix}\right\} (-1)^{i+k} (-1)^{i+k} n (n+i)! \\ &= \sum_{i=0}^{k} \left\{\begin{matrix} k+1 \\ i+1 \end{matrix}\right\} (-1)^{i+k} (-1)^{i+k} ((n+i+1)! - (i+1)(n+i)!) \\ &= \left( (n+k+1)! + \sum_{i=1}^{k} \left\{\begin{matrix} k+1 \\ i \end{matrix}\right \} -(-1)^{i+k}(n+i)! \right) - \left((-1)^k n! + \sum_{i=1}^{k} \left\{\begin{matrix} k+1 \\ i+1 \end{matrix}\right \} (-1)^{i+k} (i+1)(n+i)!\right) \\ &= (n+k+1)! - (-1)^k n! + \sum_{i=1}^k (-1)^{i+(k+1)} (n+i)! \left ( \left \{ \begin{matrix} k+1 \\ i \end{matrix} \right \} + (i+1) \left \{ \begin{matrix} k+1 \\ i+1 \end{matrix} \right \} \right ) \\ &= (n+k+1)! - (-1)^k n! + \sum_{i=1}^k (-1)^{i+(k+1)}(n+i)! \left \{ \begin{matrix} k+2 \\ i+1 \end{matrix} \right \} \\ &= \sum_{i=0}^{k+1} \left \{ \begin{matrix} (k+1)+1 \\ i+1 \end{matrix} \right \} (-1)^{i+(k+1)}(n+i)!, \end{align*} as desired. Let $a_0 = c$. It can easily be shown by induction that $a_n = \frac{c + 1^{k-1} 1! + 2^{k-1} 2! + \cdots + n^{k-1} n!}{n!}$. It is clear that $a_n$ is an integer if and only if $n! | c + 1^{k-1} 1! + 2^{k-1} 2! + \cdots + (n-1)^{k-1} (n-1)!$, so we wish to show that if $n! | c + 1^{k-1} 1! + 2^{k-1} 2! + \cdots + (n-1)^{k-1} (n-1)!$ for all integers $n$, then $3 | k - 2$. Applying lemma 4, we find that there is a constant $C_1$ and a function $f_k(n) : \mathbb{Z} \to \mathbb{Z}$ for which \[ 1^{k-1} 1! + 2^{k-1} 2! + \cdots + (n-1)^{k-1} (n-1)! = C_1 + \left(1! + 2! + \cdots + (n-1)!\right) \left( \sum_{i=0}^{k-1} \left\{\begin{matrix} k \\ i+1 \end{matrix}\right\} (-1)^{i+k-1} \right) + f(n)(n!).\] (Essentially, when we add these sums, almost all of the terms "telescope" to a sum of $1! + 2! + \cdots + (n-1)!$ multiplied by an alternating sum of Stirling numbers. The terms past $n!$ together form the $f(n)(n!)$ term in our sum and the beginning terms that were not handled, added to the $c = a_0$ yield the constant $C_1$.) By lemma 1, in order for $n!$ to divide each term of the $1^{k-1} 1! + 2^{k-1} 2! + \cdots + (n-1)^{k-1} (n-1)!$, we must have \[ \sum_{i=0}^{k-1} \left\{\begin{matrix} k \\ i+1 \end{matrix}\right\} (-1)^{i+k-1} = 0.\] In order for the sum to be 0, it must be even. We claim that the sum is even if and only if $3 | k - 2$. Note that \begin{align*} \sum_{i=0}^{k-1} \left\{\begin{matrix} k \\ i+1 \end{matrix}\right\} (-1)^{i+k-1} &\equiv \sum_{i=0}^{k-1} \left\{\begin{matrix} k \\ i+1 \end{matrix}\right\} \\ &= \sum_{i=0}^k \left\{\begin{matrix} k \\ i \end{matrix}\right\} \\ &= B_k \pmod{2}, \end{align*} where $B_{k}$ is the $k$th Bell number. The Bell numbers satisfy $B_0 = B_1 = 1$ and Touchard's congruence; in the case of $p=2$, we have $B_{n+2} \equiv B_{n+1} \equiv B_n \pmod{2}$. It is easily seen that $(B_{3k}, B_{3k+1}, B_{3k+2}) \equiv (1, 1, 0) \pmod{2}$, i.e., the Bell numbers are even only if $3 | k - 2$, which completes our proof. Comment: Alternating sums of Stirling numbers are called Complementary Bell Numbers, or Uppuluri-Carpenter numbers. A result proven here seems to imply that there actually exist at most two $k$ for which the alternating sum is 0, that is, for which every term in our sequence is a positive integer (one of which is $k=2$).

Suppose that the $a_n$ are all integers. Let $S_k(n)=\sum_{i=1}^{n}i^k (i-1)!$, so $n!a_n-a_0=S_k(n)$. Then $S_1(n)\equiv S_0(n)-1\pmod{n!}$ and for $k\ge1$ (to avoid $0^0$), the binomial theorem yields \begin{align*} \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}S_j(n) = \sum_{i=1}^{n}(i-1)^k (i-1)! = \sum_{i=2}^{n}(i-1)^{k+1}(i-2)! &= \sum_{i=1}^{n-1}i^{k+1}(i-1)! \\ &\equiv \sum_{i=1}^{n}i^{k+1}(i-1)! = S_{k+1}(n) \pmod{n!}. \end{align*}Now define $p_0=1$, $q_0=0$, $p_1=1$, $q_1=-1$, and \[p_{k+1} = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} p_j,\; q_{k+1} = \sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j} q_j\]for $k\ge1$ (these sequences are independent of $n$) so that $-a_0\equiv S_k(n) \equiv p_k S_0(n) + q_k \pmod{n!}$ for all $n\ge1$. We can prove by strong induction that $p_k$ is even iff $3|k-2$. Indeed, \[p_{k+1} \equiv \sum_{j=0}^{k}\binom{k}{j}p_j \pmod{2}\]for all $k\ge1$, so by the inductive hypothesis, \[p_{k+1} \equiv 2^k - \sum_{3|j-2}\binom{k}{j} \equiv \omega^{2k+1}+\omega^{k+2} \equiv 1-[3|k-1] \pmod{2}\]by a third roots of unity filter. Now fix $k$ not congruent to $2\pmod{3}$ and assume for the sake of contradiction that the $a_n$ are all integers. From our induction we have $p_k$ odd and therefore nonzero, so for sufficiently large $n$, $n!$ divides \[|p_k S_0(n) + (a_0+q_k)| \in (0,n!),\]a contradiction (see the first lemma in the previous post for a proof of this bound).

We start with the observations that: 1) $a_n=\dfrac{a_0+\sum_{j=1}^n j^k\cdot (j-1)!}{n!}$. 2) There always exists a polynomial $p$ with integer coefficients such that $xp(x)-p(x-1)=x^k-r_k$ where $r_k$ is some constant dependent on $k$. This is easy to show by repeatedly determining the coefficients of the polynomial. 3) Let $s_k(n)=\sum_{j=1}^n j^k(j-1)!$. Then for some fixed $t_k$, $s_k(n)=p(n)\cdot n!+r_k\cdot s_0 (n)+t_k$. This is trivial to show with induction, where $t_k$ is just defined by taking $n=1$. Thus, the problem becomes finding all $k$ such that for some $a_0$, $n!\mid \left(p(n)\cdot n!+r_k s_0 (n)+t_k+a_0\right)$. It's clear that for this to happen, $r_k$ must be $0$ by a size argument. In other words, we want to show that if $xp(x)-p(x-1)=x^k$ then $k\equiv 2\pmod{3}$. Working in $\mathbb{Z}[x]/(x^6-1)$ gives us $p(x)\equiv ax^5+bx^4+cx^3+dx^2+ex+f$. Take $\zeta$ to be a $6$th root of unity. Note that $\zeta - 1 = \zeta ^2$. Thus $\zeta p(\zeta) - p(\zeta ^2 ) = \zeta ^k$. It follows that $\zeta (a-2b-c+d+f)+(a+2b-c-d-f)=\zeta ^k$. It's easy to see that $a-2b-c+d+f$ and $a+2b-c-d-f$ have the same parity. Thus, it is impossible for one of them to be 1 and the other to be 0, ruling out $k\equiv 0, 1\pmod{3}$, therefore implying $k\equiv 2\pmod{3}$ as desired.

April wrote: ...Show that if there exists a consequence... Hmm... nobody's mentioned this yet (just a technicality) but I think in the OP this should be "sequence" instead of "consequence". Fixed ~dj

Finally solved this .

Solution from ~2 years ago when I still knew what "Stirling Numbers" are... (not that this knowledge is required, but it's helpful to motivate the solution below) First, a general formula for the sequence $(a_i)$: $$a_n = \frac{a_0 + \sum_{m=1}^n m^k(m-1)!}{n!}.$$Note that there are integer coefficients $s_{k,0},...,s_{k,k-1}$ such that $m^k = \sum_{i=0}^{k-1} s_{k,i}\prod_{j=0}^i(m+j)$, which means that $$a_n = \frac{1}{n!}(a_0 + \sum_{m=1}^n \sum_{i=0}^{k-1}s_{k,i}(m+i)!).$$Consider the double sum mod $n!$. $$\sum_m \sum_i s_{k,i}(m+i)! \equiv \sum_{c=1}^{k-1} c! \sum_{i=0}^{c-1} s_{k,i} + \sum_{c=k}^n c!\sum_{i=0}^{k-1} s_{k,i}.$$Thus we have, for some $a_0' \in \mathbb Z$, that $$a_n^* := \frac{1}{n!}(a_0' + \sum_{c =k}^{n-1} c! \left(\sum_{i=0}^{k-1}s_{k,i}\right)) \in \mathbb Z \forall n \text{ large}.$$The denominator will be larger than the numerator in absolute value for all $n$ large, hence $a_n^*$ is an integer for all $n$ if and only if $a_0' = \sum_{i=0}^{k-1} s_{k,i} = 0$. Note that the sequence $s_{k,i}$ satisfies the relation $s_{k,i} = s_{k-1,i-1} - (i+1)s_{k-1,i}, s_{k,j} = 0 \quad \forall \ \ j \ne 0,...,k-1$, and the initial condition $s_{1,0} = 1$. Let $B_k = \sum_{i=0}^{k-1} s_{k,i}$. We'll prove that $B_k\equiv 0 \pmod 2$ if and only if $k \equiv 2 \pmod 3$, which will finish the problem. We have $B_k= \sum_{i=0}^{k-1} \left(s_{k-1,i-1} - (i+1)s_{k-1,i}\right) \equiv B_{k-1} + \sum_{t \ge 0} s_{k-1, 2t}$ $$\implies B_k - B_{k-1} \equiv \sum_{t\ge 0} s_{k-1,2t} \equiv \sum_{t\ge 0} s_{k-2, 2t-1} - (2t+1)s_{k-2,2t} \equiv \sum_{t\ge 0} s_{k-2,2t-1} + s_{k-2,2t} = B_{k-2}.$$Moreover, we also have $B_1 = 1, B_2 = 0$. We can compute from the above recurrence mod 2 that $B_3 = 1, B_4 = 1 = B_1, B_5 = 0 = B_2$, from here the result is immediate.

April wrote: Let $k$ be a positive integer. Show that if there exists a sequence $a_0,a_1,\ldots$ of integers satisfying the condition \[a_n=\frac{a_{n-1}+n^k}{n}\text{ for all } n\geq 1,\]then $k-2$ is divisible by $3$. Proposed by Okan Tekman, Turkey Solution. Define $S_m(n)=1^m\cdot 1!+2^m\cdot 2!+\cdots+n^m\cdot n!.$ Note that $n!\cdot a_{n+1}=(n-1)!\cdot a_n+n^k\cdot (n-1)!,$ hence $$a_{n+1}=\frac{1}{n!}(a+S_t(n))$$where $t=k-1$ and $a=a_0.$ Claim 1. For all $t\ge 1$ and $n\ge 2$ it follows that $$S_t(n-1)\equiv (-1)^tS_0(n-1)+\sum_{i=1}^t\binom{t}{i}(-1)^{t-i}(S_{i-1}(n-1)-1)\pmod{n!}.$$Proof. By computing, \begin{align*} S_t(n) = \sum_{m=1}^n m^t\cdot m! &= \sum_{m=1}^n((m+1)-1)^t\cdot m!\\ &= \sum_{m=1}^n\left(\sum_{i=0}^{t}(m+1)^i(-1)^{t-i}\binom{t}{i}\right)m!\\ &= \sum_{i=0}^{t}\sum_{m=1}^n(m+1)^i(-1)^{t-i}\binom{t}{i}m!\\ &= \sum_{i=0}^{t}(-1)^{t-i}\binom{t}{i}\sum_{m=1}^n(m+1)^im!\\ &= (-1)^tS_0(n)+\sum_{i=0}^{t}(-1)^{t-i}\binom{t}{i}(S_{i-1}(n+1)-1). \end{align*}Now consider modulo $n!$ to get our claim.$~~\square$ Define the sequences $\{a_n\}_{n=1}^{\infty}$ and $\{b_n\}_{n=1}^{\infty}$ as $$\begin{cases}a_0 &= 1\\ a_k&=(-1)^k+\sum_{i=1}^k(-1)^{k-i}\binom{k}{i}a_{i-1}~~\forall~k\ge 1\end{cases}$$$$\begin{cases}b_0 &= 0\\ b_k&=\sum_{i=1}^k(-1)^{k-i}\binom{k}{i}(b_{i-1}-1)~~\forall~k\ge 1\end{cases}$$ Claim 2. For all $k\ge 0$ and $n\ge 1,$ $$S_k(n-1)\equiv a_k S_0(n-1)+b_k\pmod{n!}.$$Proof. Induct on $k$ and use claim 1. $~~\square$ Coming back to our original problem, We are given that $S_t(n-1)\equiv -a\pmod{n!}$ holds for all positive integers $n.$ Using our second claim, we have that $$\frac 1{n!}(a_t S_0(n-1) +b_t+a)$$is an integer for all $n\ge 1.$ Using Stolz-Cesaro theorem, $$\lim_{n\to\infty}\frac{S_0(n-1)}{n!}=\lim_{n\to\infty}\frac{1!+2!+\cdots+(n-1)!}{n!}=\lim_{n\to\infty}\frac{n!}{(n+1)!-n!}=0.$$Therefore, for all sufficiently large $n,$ it follows that $a_t S_0(n-1) +b_t+a=0,$ which forces $a_t=0.$ Claim 3. $a_n$ is even if and only if $n\equiv 1\pmod 3.$ Proof. Easy. Omitted. $~~\square$ Our last claim finishes the problem since $t=k-1.~~\blacksquare$

Obviously $k\neq 1$ so suppose $k\ge 2$. Note that we can write $a_n$ as $\frac{a_0+0!\cdot 1^k+1!\cdot 2^k+2!\cdot 3^k+\ldots +(n-1)!n^k}{n!}$, so it suffices to have $$a_0\equiv -\sum_{i=0}^{n-1}i!\cdot(i+1)^k\equiv -\sum_{i=1}^{n-1}i^{k-1}i!\pmod{n!}$$We will use $S(m,n)$ to denote $\sum_{i=0}^{m-1} i^n\cdot i!\pmod{m!}$. Also, for convenience, we denote $P_m=S(m,0)$ Claim 1: $\frac{P_m}{m!}$ approaches $0$ as $m$ grows large. Proof: As we have $\sum_{i=1}^{m-1}i!<m!$, this means that we want $\lim_{m\to\infty}\frac{0!+1!+\ldots+(m-1)!}{m!}=0$. To prove, this, it suffices to show $\frac{P_m}{m!}<\frac{2020}{\sqrt{m}}$, which is evident by induction since it's true for $1,2$ and $$P_{m+1}=\frac{P_m+1}{m+1}<\frac{\frac{2020}{\sqrt{m}}+1}{m+1}\le\frac{2021}{m+1}<\frac{2020}{\sqrt{m+1}}$$for $m>2$. Claim 2: We have $S(m,n)\equiv S(m+1,n-1)-\sum_{i=0}^{n-1}S(m,i)\cdot\binom{n}{i}$ for $n>1$ Proof: This is because $S(m+1,n-1)\equiv \sum_{i=1}^m i^{n-1}i!\equiv \sum_{i=1}^m i^n(i-1)!\equiv\sum_{i=0}^{m-1}(i+1)^ni!\pmod{(m+1)!}$, so $$S(m+1,n-1)-S(m,n)\equiv\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}\binom{n}{j}i^ji!\equiv\sum_{j=0}^{n-1}\binom{n}{j}\sum_{i=0}^{m-1}i^ji!\equiv\sum_{j=0}^{n-1}\binom{n}{j}S(m,j)$$as desired. Now, with Claim 2, we can show that $S(m,n)$ for fixed $n$ is a linear equation in $P_m$ through induction. If it is true for numbers $<n$, then $\sum_{i=0}^{n-1}S(m,i)\binom{n}{i}$, and $S(m+1,n-1)$ is one in $P_{m+1}\equiv P_m\pmod{m!}$, as desired. Thus, for the original question, we want fixed constants $A>0,B$ such that $AS_m+B\equiv 0\pmod{n!}$ for all $m$. However, if $A\neq 0$, this is impossible by Claim 1, since $AS_m+B$ will be $<n!$ for large enough $m$. Hence, we need $A=0$, and it suffices to show that $S(m,n)$ can only be a constant if $n\equiv 1\pmod 3$. In fact, we can show the statement that the coefficient of $P_m$ is even if and only if $n\equiv 1\pmod{3}$. For this, we once again use strong induction. If we denote the coefficient of $S_m$ as $A_n$, our base cases of $0,1$ yield $(A_0,A_1)\equiv(1,0)\pmod 2$, as desired. For the inductive step, note that $$A_n\equiv A_{n-1}-\sum_{i=0}^{n-1}A_i\binom{n}{i}\equiv A_{n-1}+\sum_{\stackrel{i\not\equiv 1\pmod 3}{i\le n-1}}\binom{n}{i}\equiv\sum_{i\equiv 1\pmod 3}\binom{n}{i}+\begin{cases}1&\text{ if }n\equiv 1\pmod 3\\0&\text{ otherwise }\end{cases}\pmod 2$$By Roots of Unity Filter, $$\sum_{i\equiv 1\pmod 3}\binom{n}{i}\equiv \omega^2(1+\omega)^n+\omega(1+\omega^2)^n\equiv \omega^{2n+2}+\omega^{n+1}\equiv\begin{cases}0&\text{ if }n\equiv2\pmod 3\\1&\text{ otherwise }\end{cases}\pmod 2$$Putting these two together, $A_n\equiv \begin{cases}0&\text{ if }n\equiv1\pmod 3\\1&\text{ otherwise }\end{cases}\pmod 2$, as desired.

Hopefully correct

We can clearly write $$a_n=\frac{a_0+0!\cdot 1^k+1!\cdot 2^k+\cdots+(n-1)!\cdot n^k}{n!}=\frac{a_0+1!\cdot 1^{k-1}+2!\cdot 2^{k-1}+\cdots+n!\cdot n^{k-1}}{n!}.$$Let $p=k-1$; I will show that $p \equiv 1 \pmod{3}$. Let $S(n,p)=1!\cdot 1^p+\cdots+n!\cdot n^p$. If this above expression is an integer for all $n \geq 1$, then $S(n,p) \equiv S(n-1,p)$ must be congruent to a fixed integer modulo $n!$. The idea is to write $S(n,p)$ in terms of $S(n,q)$, where $q<p$. We first need the following lemma. Lemma: $\lim_{n \to \infty} \frac{S(n-1,0)}{n!}=0$. Proof: It suffices to show that $\frac{S(n-1,0)}{n!} \leq \frac{10^{10}}{\sqrt{n}}$ for all $n \geq 1$. This is true for $n=1$, and then for $n \geq 2$ we have $$S(n-2,0) \leq \frac{10^{10}(n-1)!}{\sqrt{n-1}} \implies \frac{S(n-1,0)}{n!}=\frac{S(n-2,0)+(n-1)!}{n!}\leq \frac{\frac{10^{10}}{\sqrt{n-1}}+1}{n},$$whic is clearly at most $\frac{10^{10}}{\sqrt{n}}$. $\blacksquare$ We now set up the key recurrence relation. Claim: We have $S(n,p)\equiv S(n,p-1)-1-\sum_{q=0}^{p-1} \binom{p}{q}S(n,q) \pmod{(n+1)!}$. Proof: Write $$S(n+1,p-1)=\sum_{i=1}^{n+1} i!\cdot i^{p-1}=\sum_{i=1}^{n+1} (i-1)!\cdot i^p=\sum_{i=0}^n i!\cdot (i+1)^p=\sum_{i=0}^n i!\sum_{q=0}^p\binom{p}{q}i^q=\sum_{q=0}^p \binom{p}{q}\sum_{i=0}^n i!\cdot i^q=1+\sum_{q=0}^p \binom{p}{q}S(n,q),$$where the $1$ comes from the fact that for $q>0$, $\sum_{i=0}^n i!\cdot i^q=\sum_{i=1}^n i!\cdot i^q=S(n,q)$, but for $q=0$ we have an extra $1$ on the LHS. Hence $S(n,p)=S(n+1,p-1)-1-\sum_{q=0}^{p-1} \binom{p}{q}S(n,q)$. Since $S(n+1,p-1) \equiv S(n,p-1) \pmod{(n+1)!}$, we obtain the desired result. $\blacksquare$ Now, by our lemma, and the fact that $S(n-1,0)$ is unbounded, $S(n-1,0)$ cannot be congruent to a fixed integer modulo $n!$. On the other hand, it is both well-known and easily proven by induction that $S(n-1,1) \equiv -1 \pmod{n!}$. From our recursion, we can express $S(n-1,p)$ as a linear combination of $S(n-1,0)$ and $S(n-1,1)$ (working modulo $n!$) whose coefficients depend only on $p$, so if $S(n-1,p)$ is congruent to a fixed integer modulo $n!$ then the coefficient of $S(n-1,0)$ must be zero. I will actually show that if the coefficient of $S(n,0)$ in $S(n,p)$ is divisible by $2$ only when $p \equiv 1 \pmod{3}$. Let $a_p \in \{0,1\}$ be the coefficient of $S(n,0)$ in $S(n,p)$ when taken modulo $2$, so $a_0=1$, $a_1=0$, and $a_p\equiv a_{p-1}+\sum_{q=0}^{p-1} \binom{p}{q}a_q \pmod{2}$ for all $p \geq 2$. We now use strong induction, with the bases cases done already. By inductive hypothesis, it is sufficient to show that $\sum_{\substack{0 \leq q \leq p-1\\q \not \equiv 1 \pmod{3}}} \binom{p}{q}$ is even only when $p \equiv 0 \pmod{3}$, or equivalently $\sum_{\substack{0 \leq q \leq p\\q \equiv 1 \pmod{3}}} \binom{p}{q}$ is even only when $p \equiv 2 \pmod{3}$, since $\sum_{0 \leq q \leq p} \binom{p}{q}=2^p \equiv 0 \pmod{2}$. When $p \equiv 0 \pmod{3}$, we have $\sum_{\substack{0 \leq q \leq p\\q \equiv 1 \pmod{3}}}\binom{p}{q}=\sum_{\substack{0 \leq q \leq p\\q \equiv 2 \pmod{3}}} \binom{p}{q}$, hence it suffices to show that $\sum_{\substack{0 \leq q \leq p\\3 \mid q}} \binom{p}{q}$ is not divisible by $4$. Letting $\omega=e^{2\pi i/3}$, this is equivalent to $(1+\omega)^p+(1-\omega)^p$ never being divisible by $4$ when $3 \mid p$, which is true since this quantity is evidently always $\pm 2$ since $1\pm \omega$ are primitive sixth roots of unity. When $p \equiv 1 \pmod{3}$, we have $\sum_{\substack{0 \leq q \leq p\\q \equiv 1 \pmod{3}}}\binom{p}{q}=\sum_{\substack{0 \leq q \leq p\\3 \mid q}} \binom{p}{q}$, hence defining $\omega$ as before, it is equivalent to show that $(1+\omega)^p+(1-\omega)^p$ is odd when $p \equiv 1 \pmod{3}$. It is clear that this quantity is always $\pm 1$ for the same reason as above. When $p \equiv 2 \pmod{3}$, we can pair every $\binom{p}{q}$ with $\binom{p}{p-q}$ in the summation, except for $\binom{p}{p/2}$ if it appears. Therefore, if $\binom{p}{p/2}$ doesn't appear, the summation is clearly even, otherwise we just need to show that $\binom{p}{p/2}$ is even which is just true by Lucas/Kummer. Therefore, if $S(n,p)$ is congruent to a fixed integer modulo $(n+1)!$ for all $n$, $p \equiv 1 \pmod{3}$, hence $k \equiv 2 \pmod{3}$, which is the desired result. $\blacksquare$ Edit: I have realized that I also need to handle p=2 mod 3 because we’re doing strong induction but you basically do it the same way. I am sick rn though so I will edit it in a few days later ok fixed

daniel73 wrote: This may help in finding a solution: Note that we can always find a polynomial $P_k(x)$ of degree $k-1$ and with integer coefficients such that $xP_k(x)=P_k(x-1)+x^k+r_k$, where $r_k$ is some residual constant to be determined; just express $P_k(x)=c_{k-1}x^{k-1}+c_{k-2}x^{k-2}+\dots+c_1x+c_0$, and work the coefficients down from $c_{k-1}$ to $c_0$, finding the coefficient $c_m$ by comparing the terms of degree $m+1$ at both sides of the equation. Clearly $c_{k-1}=1$, and all other coefficients are a linear combination with integral weights of higher-order coefficients, hence the polynomial coefficients are all integral. The residual constant $r_k$ is the one that makes the constant term in the RHS equal to zero, and is also clearly integral. Note now that a sequence as described in the problem statement exists for $k$ iff $r_k=0$; indeed, if $r_k=0$, take $a_n=P_k(n)$ for $n\geq0$, and we got the right sequence, whereas is the sequence exists, define $d_n=P_k(n)-a_n$, or $d_n=\frac{d_{n-1}+r_k}{n}$. After trivial induction, we find that $d_n=\frac{d_0}{n!}+r_k\frac{0!+1!+\dots+(n-1)!}{n!}$. Take now $n$ large enough that $\left|\frac{d_0}{n!}\right|<\frac{1}{2}$, and $|r_k|\frac{0!+1!+\dots+(n-1)!}{n!}<\frac{1}{2}$ (*), and since $d_n$ is clearly integral, then $d_n=0$, and since the same applies to $n+1$ because it is even larger, then $d_n=d_{n+1}=0$, yielding $r_k=0$. (*) It can be shown by induction that for $n\geq4$, $\frac{0!+1!+\dots+(n-1)!}{n!}<\frac{1}{\sqrt{n}}$, or it suffices to take $n>4r_k^2$. Once we have all this, it suffices to show that if $r_k=0$, then $k\equiv2\pmod 3$, which can probably obtained as follows: note that $P_1(x)=1$ and $r_1=-1$, $P_2(x)=x+1$ and $r_2=0$, and $P_3(x)=x^2+x-1$ and $r_3=1$, but after this $r_k$ increases rapidly in absolute value, with parity odd,even,odd,odd,even,odd,odd,even,odd,... or we may postulate that $r_k$ is even iff $k\equiv2\pmod3$; if we manage to prove that, then we are done... Somebody cares to finish it? Note: I have worked $r_k$ for $k=2,5,8,11$, but it is only zero for $k=2$, yielding sequence $a_n=n+1$, clearly satisfying the condition in the problem statement, hence I'd settle just for proving the parity of $r_k$, since it is clearly false that $r_k=0$ for all $k\equiv2\pmod3$...

This is not a number theory problem. Also how one motivates the second step would be much appreciated (I got carried there ) First Step: We find an integer polynomial $P$ such that there is a sequence $\{b_n\} = \{a_n - P(n)\}$ that satisfies $b_n = \frac{b_{n-1} + \ell}n$ for some constant $\ell$. This is simply a matter of equating coefficients: setting $P(n) = n^{k-1} + a_{k-2} n^{k-2} + \cdots + a_0$, we must have \[a_{k-2} n^{k-1} + a_{k-3} n^{k-2} + \cdots + a_0 n = (n-1)^{k-1} + a_{k-2} (n-1)^{k-2} + \cdots + a_0+ r.\]This is a linear system where $a_i$ is written in terms of linear combinations of $a_j$ for $j \geq i$ (in particular $a_{k-2} = 1$), so it is given by a nonsingular $k \times k$ matrix. Thus such coefficients $a_0, a_1, \dots, a_{k-2}, r$ exist and are unique. Second Step: Observe that $a_n$ is an integer if and only if $b_n$ is an integer. If $\ell \neq 0$, then notice that for sufficiently large $n$, $b_n$ will not be an integer; thus we must have $\ell = 0$. In other words, our polynomial $P$ satisfies \[xP(x) = x^k + P(x-1).\]In fact, for $\omega$ a third root of unity, we have \begin{align*} -\omega P(-\omega) &= P(\omega^2) + (-\omega)^k \\ -\omega^2 P(-\omega^2) &= P(\omega) + (-\omega^2)^k. \end{align*}Now some black magic: taking this equation modulo $2$ and adding the first equation to $\omega$ times the second, we need $\omega^k + \omega^{2k + 1} \equiv 0$ which can only happen when $k \equiv 2 \pmod 3$, as needed. Remark: The last step still feels like black magic. A lot of more *natural* things one would do with the cube root of unity (filter to get $2$ mod $3$ exponent coefficients, etc) don't work, but this somehow restricts to $k \equiv 2 \pmod 3$.