mjhjmtu

The sequence $a_n$ given by
$$a_n=sum_k=0^nfracn!k!$$
is found at A000522 on OEIS with a description: total number of arrangements of a set with $n$ elements. Let $nu_2(x)$ denote the $2$-adic valuation of the integer $x$. My first question:

Is it true that $nu_2(a_n)=nu_2(n+13)$?

Well, that is what experiments suggest to me. My second question (curiosity) is:

What is special about the presence of the number $13$ above?

Thanks to darij grinberg the above claim has failed, which prompts me to ask:

What is the $2$-adic valuation of $a_n$ then?

To your first question: No, it is false. For $n = 256 - 13$, the number $a_n$ has $nu_2left(a_nright) = 7 < 8 = nu_2 left(n+13right)$.

HOWEVER, it is almost correct: namely, it is correct whenever $128 nmid n+13$ (so the smallest counterexample is $n = 128 - 13 = 115$). This is the following theorem:

Theorem 1. We have $nu_2left(a_nright) = nu_2left(n+13right)$ for all $n in mathbbN$ that don't satisfy $128 mid n+13$.

Proof of Theorem 1 (sketched). We observe the following facts:

1. Each nonnegative integer $n$ and each positive integer $k$ satisfy $a_n+k equiv a_n mod k$. (This is proven by induction on $n$. The base case boils down to $a_k equiv 1 mod k$, which follows from $a_k = k a_k-1 + 1$. The induction step uses the recursion $a_n = na_n-1 + 1$.)




2. Each $n in mathbbN$ satisfies $a_n+128 equiv a_n mod 128$. (This follows by applying fact 1 to $k = 128$.)




3. Each $n in mathbbN$ satisfies $128 nmid a_n$ unless $128 mid n+13$. (This needs only to be checked for the first $128$ values of $n$, due to fact 2 above.)




4. Combining facts 2 and 3, obtain $nu_2left(a_n+128right) = nu_2left(a_nright)$ for each $n in mathbbN$ unless $128 mid n+13$.

Using fact 4, the Theorem 1 can be proven by induction (with $128$ base cases, unfortunately). $blacksquare$

So what about the cases when $128 mid n+13$ ? Their behavior is weird. The smallest such case is $n = 115$, in which $nu_2 left(a_nright) = 9 > 7 = nu_2 left( n + 13 right)$. However, for all larger $n$'s of the form $2^k - 13$, the sign flips:

Theorem 2. We have $nu_2left(a_nright) = 7 < nu_2left(n+13right)$ for all $n$ of the form $n = 2^k - 13$ with $k geq 8$.

Proof of Theorem 2 (sketched). We claim that $a_2^k - 13 equiv 2^7 mod 2^8$ for each $k geq 8$. This is proven by induction on $k$. The induction base ($k = 8$) is verified by computer; the induction step relies on fact 1 from the proof of Theorem 1. $blacksquare$

Theorem 2 should not suggest that $nu_2left(a_nright)$ is always at most $7$; it is not. Higher values of $nu_2left(a_nright)$ appear when $n+13$ is a multiple of $128$ but not itself a power of $2$. For example, $nu_2left(a_2675right) = 15$.

Note that the same inductive argument that we used to prove fact 1 can be used to show the following stronger result:

Proposition 3. For any nonnegative integer $n$ and any positive integer $k$, we have
beginalign*
a_n+k-a_n & equiv%
begincases
k, & textif n+ktext or ntext is odd;\
0, & textif neither n+ktext nor ntext is odd%
endcases
mod 2k.
endalign*

This might come useful.

Code: It is not immediately obvious how to compute $a_n$ for large values of $n$ efficiently. After all, $a_n geq n!$, so we'd at least need a large integer type. Fortunately, all we care about are the $2$-adic valuations $nu_2left(a_nright)$ and the remainders of $a_n$ modulo powers of $2$. The former valuations can easily be obtained from the latter remainders, so we only need to care about the remainders. And we can easily compute the remainders of $a_n$ modulo any given integer $k$ by recursion, because the recursive relation $a_n = na_n-1 + 1$ descends to $mathbbZ/kmathbbZ$. Here, for example, is some simple Sage (or Python2) code that recursively $a_n$ modulo $2^k$ for given $n$ and $k$:

def a(n, k): # This gives `a_n` modulo `2^k`.
 if n == 0:
 return 1
 return (n * a(n-1) + 1) % (2 ** k)

This is already quite useful (e.g., you can let it compute "a(256-13, 8)" to check that $nu_2left(a_nright) = 7$ for $n = 256-13$), but not really optimal, because it's recursive and eventually (around $n = 1000$) exceeds Python's maximum recursion depth. So let us replace the recursion by dynamic programming.

Here is some better Sage (or Python2) code, which tabulates $nu_2(a_n)$ for $n = 1, 2, ldots, m$ given a positive integer $m$:

def val2(k):
 # Return the `2`-adic valuation `nu_2(k)` of the integer `k`.
 if k == 0:
 return # returns ``None``, standing for `-infty`.
 res = 0
 kk = k
 while kk % 2 == 0:
 res += 1
 kk = kk // 2
 return res

def aas(n, k):
 # Return the list `[a_0, a_1, ldots, a_n-1]` modulo `2^k`.
 pwk = 2 ** k
 res = [1] * n
 for i in range(1, n):
 res[i] = (i * res[i-1] + 1) % pwk
 return res

def output(m):
 # Return a LaTeX table of `nu_2(a_n)` for `n = 1, 2, ldots, m`.
 k = 3
 # Starting with modulo `2^3`, will later replace by better `2`-adic precision.
 nums = aas(m+1, k)
 while (0 in nums):
 k += 1
 nums = aas(m+1, k)
 vs = [val2(i) for i in nums]
 res = r"beginarrayc hline" + "n" + r"n & nu_2(a_n) \ hline "
 for i in range(1, m+1):
 res += "n "
 res += str(i) + r"&" + str(vs[i]) + r" \"
 res += " n" + r"hline endarray"
 return res

If I let it execute "print output(25)", it returns me the LaTeX code for a table of values of $nu_2(a_n)$... which I'm not quoting here, because Theorem 1 renders it obsolete. A better idea is to tabulate only those values that Theorem 1 does not cover:

def output2(m):
 # Return a LaTeX table of `nu_2(a_128n - 13)` for `n = 1, 2, ldots, m`.
 k = 3
 # Starting with modulo `2^3`, will later replace by better `2`-adic precision.
 M = 128*m - 13
 nums = aas(M+1, k)
 while (0 in nums):
 k += 1
 nums = aas(M+1, k)
 vs = [val2(i) for i in nums]
 res = r"beginarrayc hline" + "n" + r"n & nu_2(a_128n-13) & nu_2(128n) \ hline "
 for j in range(1, m+1):
 i = 128 * j - 13
 res += "n "
 res += str(j) + r"&" + str(vs[i]) + r"&" + str(val2(128 * j)) + r" \"
 res += " n" + r"hline endarray"
 return res

Now, executing "print output2(25)" yields

beginequation
beginarrayc hline
n & nu_2(a_128n-13) & nu_2(128n) \ hline
1&9&7 \
2&7&8 \
3&8&7 \
4&7&9 \
5&11&7 \
6&7&8 \
7&8&7 \
8&7&10 \
9&9&7 \
10&7&8 \
11&8&7 \
12&7&9 \
13&10&7 \
14&7&8 \
15&8&7 \
16&7&11 \
17&9&7 \
18&7&8 \
19&8&7 \
20&7&9 \
21&15&7 \
22&7&8 \
23&8&7 \
24&7&10 \
25&9&7 \
hline endarray .
endequation