\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}


\begin{center}
\vskip 1cm{\LARGE\bf Congruence Classes of $2$-adic Valuations of \\ 
\vskip .1in
Stirling Numbers of the Second Kind
}
\vskip 1cm
\large
Curtis Bennett and Edward Mosteig\\
Department of Mathematics\\
Loyola Marymount University\\
Los Angeles, CA 90045\\
USA\\
\href{mailto:cbennett@lmu.edu}{\tt cbennett@lmu.edu}\\
\href{mailto:emosteig@lmu.edu}{\tt emosteig@lmu.edu}\\
\end{center}

\vskip .2 in

\begin{abstract}
We analyze congruence classes of $S(n,k)$, the Stirling numbers of the second kind, modulo powers of 2.
This analysis provides insight into a conjecture posed by Amdeberhan, Manna and Moll, which those authors established for $k$ at most 5.
We provide a framework that can be used to justify the conjecture by computational means, which we then complete for values of $k$ between 5 and 20.
\end{abstract}


\section{Introduction}


The Stirling numbers of the second kind were originally defined to aid in the computation of the sum of the $k$th powers of the first $n$ positive integers.  They  gained importance in mathematics as they arose in myriad contexts ranging from elementary combinatorics to topology.
For computational purposes, the Stirling numbers of the second kind can be described by the
following recurrence relation where $n \ge 0$ and $k\ge 1$:
$$
S(n+1,k)  =  k\cdot S(n,k) + S(n,k-1)
$$
with initial conditions
\begin{displaymath}
S(n,0) =
\begin{cases}
 1, & \text{if } n=0 \text{ and } k=0; \\
0, & \text{if } n \ge 1 \text{ or } n<k.
\end{cases}
\end{displaymath}


Much like the binomial coefficients, this recurrence leads to interesting divisibility properties.  Indeed, if one codes the odd Stirling numbers with a black box and the even numbers with a white box, we obtain a Sierpinski-like triangle (see Figure \ref{sierpinski}).  Here the top row corresponds to $n=0$.

\begin{figure}[ht]\label{sierpinski}
\begin{center}
\includegraphics[scale=.7]{sierpinski.eps}
\end{center}
\caption{The parity of $S(n,k)$.
}
\end{figure}

More recently, a deeper study of the behavior of the Stirling numbers with respect to primes has taken place.
Kwong  \cite{Kw} shows that for any prime $p$ and fixed  $k$, the sequence $\{S(n,k)\}_{n=1}^\infty$ is periodic modulo $p$ once $n$ is sufficiently large.  Lengyel \cite{Le1.5} then formulates (and proves several special cases of) the conjecture that the $2$-adic valuation of the Stirling number $S(2^n,k)$ is one less than the number of occurrences of the digit $1$  in the binary expansion of $k$.   Later in 2005, De Wannemaker \cite{Wa} proves this result in general.

 Amdeberhan,  Manna, and Moll \cite{Am} make a general study of the $2$-adic valuation of the Stirling numbers $S(n,k)$, noting that for fixed $k$, the sequence of $2$-adic valuations of $S(n,k)$ appears to satisfy interesting fractal-like properties.  Their paper proves a special result for the case $k\le 5$, and then makes a general conjecture (which we call AMM) about the $2$-adic valuations of these sequences in general.  The proof  provided by Amdeberhan,  Manna, and Moll \cite{Am} of the case $k=5$ appears complicated, and while one might see a way to generalize this proof for the case $k=6$, it appears that larger values of $k$ would not fall easily to similar arguments.

 The goal of the present paper is to provide a general technique for proving the AMM conjecture (see Section \ref{background} for details) for fixed $k $, and to provide a deterministic method for carrying out this technique.  This method allows us to prove the AMM conjecture for all $k\le20$ on our desktop computer.
  Further, we believe that optimizing our code would allow us to obtain results for larger values of $k$; however, there are significant limitations since the  complexity of our algorithms is exponential. This method further allows us to expose some of the difficulties in the general case by contrasting the behaviors of sequences of the form $\{ S(n,k) \}$ for different values of $k$.

\section{Background}\label{background}

Given $k,n \in {\mathbb{N}}$ such that $n\ge k$, the Stirling number of the second kind, $S(n,k)$, can be defined combinatorially  as the number of ways to partition a set of $n$ elements into $k$ nonempty subsets.
Throughout this paper, we  fix $k$ and anaylze the behavior of $S(n,k)$ for different values of $n$.  To this end, we define the function ${\rm St}_k: \{k,k+1,k+2, \dots\} \to {\mathbb{N}}$ by
$${\rm St}_k(n) := S(n,k).$$
A classical formula for Stirling numbers  of the second kind   \cite{Gr} is given by
\begin{equation} \label{Stirlingsum}
{\rm St}_k(n)=\frac{1}{k!}\sum_{t=0}^{k-1} {k\choose t}(k-t)^n (-1)^t,
\end{equation}
which can be rewritten as
\begin{equation} \label{Stirlingsum2}
k!{\rm St}_k(n)=(-1)^k\sum_{t=1}^{k}  (-1)^t {k\choose t}t^n.
\end{equation}




Our primary objective is to examine the powers of 2 that divide ${\rm St}_k(n)$
for a fixed value of $k$.  With this in mind, we define the 2-adic valuation as the function  $\nu_2: {\mathbb{Z}}^+ \to {\mathbb{N}}$ given by
\begin{equation*}
\nu_2(z) =  \max\{ i \in {\mathbb{N}} : 2^i \mid z \}.
\end{equation*}
In the future, we will compute 2-adic valuations of Stirling numbers indexed according to congruence classes modulo powers of 2.


For $n,t\in {\mathbb{N}}$, we define the congruence class
\begin{equation}
[n]_t = \{ j \in {\mathbb{N}} : j \ge \max\{n,t\} \mbox{ and } j \equiv n \pmod{t} \}.
\end{equation}
For each class of the form $[n]_{2^m}$, we refer to $m$ as the {\em level} of the class.  Note that each class of level $m$ can ``almost" be written as a disjoint union of two classes of level $m+1$:
\begin{equation}\label{almostunion}
[n]_{2^m} \cap \{j \in {\mathbb{N}} : j \ge 2^{m+1} \} = [n]_{2^{m+1}} \cup  [n+2^m]_{2^{m+1}}.
\end{equation}
We refer to $[n]_{2^{m+1}}$ and
 $[n+2^m]_{2^{m+1}}$ as the {\em children} of $[n]_{2^m}$.



Throughout this paper, whenever $f$ is a function and $S$ is a subset of the domain of $f$, we adopt the notation
$$f(S) = \{ f(s) : s \in S\},$$
and we say that $f$ is {\em constant} on $S$ if and only if $f(S)$ a singleton.





Our paper focuses on the following conjecture,  posed by Amdeberhan, Manna and Moll, which we refer to as the AMM conjecture \cite{Am}.



\begin{conjecture}\label{mollconjecture} For each $k\in {\mathbb{N}}$, there exist non-negative integers $M_k$ and $\mu_k$ such that for any $m \ge M_k$,  the following two statements hold.
\begin{enumerate}
\item[(a)] There are $\mu_k$ classes of the form $[n]_{2^m}$ on which $\nu_2 \circ {\rm St}_k$  is non-constant.

\item[(b)]  If $\nu_2 \circ {\rm St}_k$ is non-constant on the class $[n]_{2^m}$, then $\nu_2 \circ {\rm St}_k$ is non-constant on exactly one of the children of $[n]_{2^m}$.


\end{enumerate}
\end{conjecture}


Amdeberhan, Manna and Moll  \cite{Am} demonstrate  when $k=5$ that
at each level $m \ge 1$, there are exactly two classes on which $\nu_2 \circ {\rm St}_{5}$ is non-constant.   In addition, the authors demonstrate that for each such class, $\nu_2 \circ {\rm St}_{5}$ is non-constant on exactly one of the children.


The proof provided by Amdeberhan, Manna and Moll for the case $k=5$ could be adapted for the case $k=6$ with some additional effort.   However, when $k=7$, the situation is much more complex, and so a different approach is necessary.  In this paper, we produce a general framework that can be used to verify  the conjecture for many different values of $k$, which we have completed for all non-negative integers from $k=5$ to $k=20$.
In Section \ref{examples}, we use this framework to demonstrate different behaviors exhibited for different values of $k$.



In order to justify the conjecture, we first
 determine the classes
on which $\nu_2 \circ {\rm St}_k$ is constant for some initial values of $m$.  To this end, we formulate the definition below.

\begin{definition}\label{Nkm}
For any positive integers $k,m$, we define ${\mathcal N}_{k,m}$
by
\begin{equation}
{\mathcal N}_{k,m} = \{ n \in {\mathbb{N}} :   k \le n < k+ 2^m \mbox{ and } \nu_2 \circ {\rm St}_k \mbox{ is non-constant on } [n]_{2^m}\}.
\end{equation}
\end{definition}


We can compute the number of non-constant classes for small, fixed values of $k$ and $m$, as described in the table below.

\begin{table}[h]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|} \hline
$k \backslash  m$ & 1 & 2 &3 & 4 & 5 & 6 &  7 & 8 & 9 & 10  \\ \hline
5 & 2 &2  &2 & 2& 2& 2& 2& 2& 2& 2 \\ \hline
6 & 2& 2& 2& 2& 2& 2& 2& 2& 2& 2 \\ \hline
7 & 2& 2& 2& 2& 2& 2& 2& 2& 2& 2 \\ \hline
8 & 2& 2& 2& 2& 2& 2& 2& 2& 2& 2 \\ \hline
9 & 2&4 &4 &4 &4 &4 &4 &4 &4 &4  \\ \hline
10 & 2&4 &4 &4 &4 &4 &4 &4 &4 &4  \\ \hline
11 & 2&4 &4 &4 &4 &4 &4 &4 &4 &4  \\ \hline
12 & 2&4 &4 &4 &4 &4 &4 &4 &4 &4  \\ \hline
13 & 2  & 4  & 5  & 4  & 4 & 4  & 4& 4& 4& 4 \\ \hline
14 & 2& 4& 6& 6& 6& 6& 6& 6& 6& 6 \\ \hline
\end{tabular}
\end{center}
\caption{The cardinality of ${\mathcal N}_{k,m}$.
}
\label{cardNkm}
\end{table}

Note that for each fixed value of $k$, the sequence
$$\#\mathcal{N}_{k,1}, \#\mathcal{N}_{k,2}, \#\mathcal{N}_{k,3}, \dots$$
appears to stabilize.
  From empirical evidence, we
conjecture that this, indeed, is the case; in addition, it appears that
if we define
\begin{equation*}
n_k = \lim_{m \to \infty} \#{\mathcal N}_{k,m},
\end{equation*}
then  $n_1, n_2, n_3, \dots$
is a non-decreasing sequence.
In future studies, we plan to investigate the validity of this conjecture as well as determine for each $k$, the smallest index $i_k$ such that $\#{\mathcal N}_{k,i} = \#{\mathcal N}_{k,i_k}$ for all $i \ge i_k$.

Before revealing our results, we introduce some terminology and make a few additional definitions.
Our arguments heavily rely on the result established by Kwong  \cite{Kw} that if  $k$ and $m$ are positive integers such that
 $k \ge 5$,  then for sufficiently large $n$,
 \begin{equation}\label{generalcongruence}
{\rm St}_k(n) \equiv  {\rm St}_k(n+2^{m}) \pmod{2^{m-\lceil \log_2(k) \rceil+2}} .\end{equation}
Since the expression $\lceil \log_2(k) \rceil -2$ appears frequently enough throughout this paper, we make the following definition.
\begin{definition}
Given $k \ge 5$,  define
$${{b}}_k = \lceil \log_2(k) \rceil-2.$$
\end{definition}
Before proceeding, we must adopt some additional terminology.
  \begin{definition}
Given a set $S$, if there exists a constant $c$ such that all the elements of $S$ are congruent to $c$ modulo $M$, then we write
$S \equiv c \pmod{M}$,
and we say that $S$   is {\em constant modulo }$M$; otherwise, we say that $S$ is {\em not constant modulo }$M$.  Regardless of whether $S$ is constant modulo $M$,  if there exists $s \in S$ such that $s \not\equiv c \pmod{M}$, then we write
$S \not\equiv c \pmod{M}$.
\end{definition}

We are now in a position to state our main result,  which provides a step toward verifying the AMM conjecture for specific values of $k$.  In addition, the theorem provide a way to determine $\mu_k$, the number of classes at level $k$ on which $\nu_2 \circ {\rm St}_k$ is non-constant.  It also provides an upper bound on $M_k$, the level at which the number of such classes stabilizes.





\begin{theorem}\label{maintheorem}
Let $k,M$ be non-negative integers such that
$ k \ge 5$, $M \ge {{b}}_k$ and
$2^M \ge M- {{b}}_k + \nu_2(k!)$.
 For each $j \in {\mathcal N}_{k,M}$, let $\ell_j$ be a non-negative integer.
Suppose further that for every  integer $n\ge k$ such that
$n \equiv j \pmod{2^M\mbox}$ for some $j\in{\mathcal N}_{k,M},$
the following two conditions hold for all $m \ge M$.
\begin{enumerate}
\item[(i)]  ${\rm St}_k([n]_{2^{m  }})$  is not constant modulo  $2^{m-{{b}}_k + \ell_j+1}$.
\item[(ii)]${\rm St}_k([n]_{2^{m  }})$  is  constant modulo  $2^{m-{{b}}_k + \ell_j}$.
\end{enumerate}
Then the AMM conjecture holds with $\mu_k = \# {\mathcal N}_{k,M}$ and
 $M_k \le M$.
\end{theorem}

If it were possible to  determine when ${\rm St}_k([n]_{2^m})$ is constant modulo  powers of 2, then
Theorem \ref{maintheorem} would provide a concrete approach to proving the AMM conjecture.
 Fortunately, Proposition \ref{finitecheckconstant} provides conditions that are equivalent to the statement that ${\rm St}_k([n]_{2^m})$ is constant modulo $2^{m-b_k+\ell}$.  We will consider these conditions when replacing $\ell$ by the parameter $\ell_j$ (and $\ell_j+1$) found in Theorem \ref{maintheorem}.
More specifically, through the use of an auxiliary function $f_k$ defined in Lemma \ref{fStcorrespondence}, we will see that these conditions can be reduced to a finite check using Proposition \ref{finitecheckconstant}, thus making verification of the AMM conjecture possible.  We  implement the algorithms that perform these checks using {\sl Mathematica}, and produce  examples for different values of $k$ in Section \ref{examples}.




\section{Preliminary results}


To investigate the AMM conjecture and prove our main result, we first  produce a few preliminary results concerning modular arithmetic, which we explore in this section.   Since equation (\ref{Stirlingsum2}) will play a critical role in our analysis, we must first analyze the behavior of powers of the form $t^n$ that appear in the summation.   We begin by quoting the following result,  which can be attributed to Gauss \cite{Du}.
\begin{lemma} \label{odd-order}
For any integer $m\ge 1$ and any odd positive integer $t$,
\begin{equation*}
t^{2^{m}} \equiv 1 \pmod{2^{m+2}}.
\end{equation*}
\end{lemma}

Using this lemma as a basis, we demonstrate how to produce the binary representation of $t^{2^{m}}$ modulo  powers of 2.


\begin{proposition}\label{binrep}
For any odd positive integer $t$ and  non-negative integer $s$, there exists a sequence $c_0, \dots, c_s$, where $c_{i} \in \{0,1\}$, such that  for $ m \ge s+1$,
$$t^{2^{m}} \equiv 1 + \sum_{i=0}^s c_{i}2^{m+2+i} \pmod{2^{m+s+3}}.$$
The sequence $c_0, \dots, c_s$ is comprised of the first $s+1$ digits of the binary representation of the integer $(t^{2^{s+1}} - 1)/2^{s+3}$.
\end{proposition}

Before proceeding with the proof, we provide an example.   Note that if $s=2$ and $t=7$, then the base 10 and base 2 representations of $(t^{2^{s+1}} - 1)/2^{s+3}$ are given by
$$(7^8 - 1)/32  = (180150)_{10} = (101011111110110110)_2.$$
Therefore, $c_0 =0, c_1=1, c_2=2, \dots$, and so for $m \ge 3$,
$$7^{2^m} \equiv  1 + 2^{m+3} + 2^{m+4} \pmod{2^{m+5}}.$$
Repeated applications of this proposition will permit us to reduce some specific expressions modulo powers of 2, which we first encounter in Lemma \ref{fStcorrespondence}.


\begin{proof}
We  proceed by induction on $m$.
We begin with the base case $m=s+1$.
By Lemma \ref{odd-order},
$t^{2^{s+1}} - 1$ is divisible by $2^{s+3}$.
Define  the integer
$a=(t^{2^{s+1}} - 1)/2^{s+3}$, and write its binary representation as $a = \sum_{i=0}^\infty c_i 2^i,$
where $c_i = 0$ for $i\gg 0$.  Then
$a \equiv \sum_{i=0}^{s} c_i 2^i \pmod{2^{s+1}},$
and so
$a\cdot 2^{s+3} \equiv \sum_{i=0}^s c_i 2^{s+3+i} \pmod{2^{2s+4}}.$
Since $a=(t^{2^{s+1}} - 1)/2^{s+3}$, it follows that $t^{2^{s+1}} = 1 + a \cdot 2^{s+3}$, and so
$$t^{2^{s+1}}  \equiv 1 + \sum_{i=0}^s c_i 2^{s+3+i} \pmod{2^{2s+4}}.$$

For the inductive step, we assume
\begin{equation*}
t^{2^{m}} \equiv 1 + \sum_{i=0}^s c_{i}2^{m+2+i} \pmod{2^{m+s+3}},
\end{equation*}
in which case $t^{2^{m}}  = 1 + A + B  \cdot 2^{m+s+3}$, where $A = \sum_{i=0}^s c_{i}2^{m+2+i} $ and $B$ is an integer.
Since $t^{2^{m+1}}  =  \left(t^{2^{m}}\right)^2$, we can write
\begin{eqnarray*}
t^{2^{m+1}}  & = & \left( 1 + A + B \cdot 2^{m+s+3} \right)^2 \\
 & = & 1 + 2A + A^2 + 2 (1+A) \cdot B \cdot 2^{m+s+3} + \left(  B \cdot 2^{m+s+3} \right)^2 \\
 & = & 1 + 2A + A^2 +  (1+A) \cdot B \cdot 2^{m+s+4} + \left(  B \cdot 2^{m+s+3} \right)^2.
\end{eqnarray*}
It follows immediately that $t^{2^{m+1}} \equiv 1 + 2A + A^2 \pmod{2^{m+s+4}}$, and so working modulo $2^{m+s+4}$, we have
\begin{eqnarray*}
t^{2^{m+1}}
&  \equiv &  1 +  2 \cdot \sum_{i=0}^s c_{i}2^{m+2+i} +  \left(\sum_{i=0}^s c_{i}2^{m+2+i}\right)^2 \\
&  \equiv &  1 +   \sum_{i=0}^s c_{i}2^{m+3+i} +  2^{2(m+2)} \left(\sum_{i=0}^s c_{i}2^{i}\right)^2.
\end{eqnarray*}
Since $m \ge s+1$, it follows that $2^{2(m+2)} \equiv 0 \pmod{2^{m+s+4}}$,
and so
\begin{equation*}
t^{2^{m+1}}  \equiv 1 +   \sum_{i=0}^s c_{i}2^{m+3+i}  \pmod{2^{m+s+4}},
\end{equation*}
as desired.
\end{proof}


Next, we reformulate  and reprove (\ref{generalcongruence}) while adding specificity to the requirement that $n$  be
sufficiently large.




\begin{proposition}\label{kwongext}
For non-negative integers $k,m,n$ such that
$n \ge k \ge 5$, $m \ge {{b}}_k$ and $2^m \ge m- {{b}}_k + \nu_2(k!)$,
\begin{equation*}
{\rm St}_k([n]_{2^{m}})
\mbox{ is constant modulo } 2^{m-{{b}}_k} .\end{equation*}
\end{proposition}

Again, before proceeding with the proof, we provide an example.
If $k=5$, then $b_k = 1$.  The conditions $m \ge {{b}}_k$ and $2^m \ge m- {{b}}_k + \nu_2(k!)$ hold precisely when $m\ge 3$.  Reducing multiple expressions of the form ${\rm St}_k(n + j \cdot {2^{m}})$ modulo  $2^{m-{{b}}_k}$ where $j$ is a positive integer provides evidence of the following modular equivalences, all of which can be justified by the proposition:
\begin{eqnarray*}
{\rm St}_k([1]_{2^{3}}) &  \equiv &  3; \\
{\rm St}_k([2]_{2^{3}}) &  \equiv &  1; \\
{\rm St}_k([3]_{2^{3}}) &  \equiv &  2; \\
{\rm St}_k([4]_{2^{3}}) &  \equiv &  0; \\
{\rm St}_k([5]_{2^{3}}) &  \equiv &  1; \\
{\rm St}_k([6]_{2^{3}}) &  \equiv &  3; \\
{\rm St}_k([7]_{2^{3}}) &  \equiv &  0; \\
{\rm St}_k([8]_{2^{3}}) &  \equiv &  2.
\end{eqnarray*}


\begin{proof}
First, we note that since each term of $[n]_{2^m}$ is at least $2^m$, we may assume without loss of generality that
$n \ge 2^m$.  Since $2^m \ge m-{{b}}_k + \nu_2(k!)$, it follows that
\begin{equation*}
n \ge m - {{b}}_k +\nu_2(k!).
\end{equation*}
Now, for any given value of $n$,
$${\rm St}_k(n+2^{m})  \equiv {\rm St}_k(n)  \pmod{2^{m-{{b}}_k}}$$ if and only if
$$k!{\rm St}_k(n+2^{m})  - k! {\rm St}_k(n)  \equiv 0 \pmod{2^{m-{{b}}_k +\nu_2(k!)}}.$$
Using (\ref{Stirlingsum2}), we can  write
$k!{\rm St}_k(n+2^{m})  - k! {\rm St}_k(n) $
 as
\begin{eqnarray*}
(-1)^{k}\sum_{t=1}^{k} (-1)^{t} {k\choose t} t^n  \left(t^{2^{m}}-1  \right).
\end{eqnarray*}
For $n \ge m - {{b}}_k + \nu_2(k!)$,  we have that $t^n \equiv 0 \pmod{2^{m-{{b}}_k +\nu_2(k!)}}$ whenever $t$ is even, in which case
\begin{equation}\label{fncongruence}
h(n) \equiv k!{\rm St}_k(n+2^{m})  - k!{\rm St}_k(n)  \pmod{2^{m-{{b}}_k+ \nu_2(k!)}}
\end{equation}
 where
\begin{eqnarray*}
h(n)& = & (-1)^{k}\sum_{s=1}^{\lceil k/2 \rceil} (-1)^{2s-1} {k\choose 2s-1} (2s-1)^n  \left((2s-1)^{2^{m}}-1  \right) \\
  & = & (-1)^{k-1}\sum_{s=1}^{\lceil k/2 \rceil}  {k\choose 2s-1} (2s-1)^n  \left((2s-1)^{2^{m}}-1  \right)
\end{eqnarray*}
For any positive integer $s$, the sequence $\{ (2s-1)^n\}_{n=1}^\infty$  is periodic modulo $2^{m -{{b}}_k + \nu_2(k!)}$.  (More specifically, by  Lemma \ref{odd-order}, the the period of this sequence reduced modulo $2^{m -{{b}}_k + \nu_2(k!)}$ divides $2^{m -{{b}}_k + \nu_2(k!)-2}$.)
Consequently, $\{h(n)\}_{n=1}^\infty$ must be periodic modulo $2^{m - {{b}}_k + \nu_2(k!)}$.  By (\ref{fncongruence}), it follows that the sequence $$\{ k!{\rm St}_k(n+2^m) - k!{\rm St}_k(n) \}_{n=m-{{b}}_k + \nu_2(k!)}^\infty$$
 is periodic modulo $2^{m-{{b}}_k + \nu_2(k!)}$, and so
 \begin{equation}\label{prelimperiodic}
 \{ {\rm St}_k(n+2^m) - {\rm St}_k(n) \}_{n=m-{{b}}_k + \nu_2(k!)}^\infty
 \end{equation}
 is periodic modulo $2^{m-{{b}}_k}$.
 However, by (\ref{generalcongruence}), for $n$ sufficiently large ($n\gg0$),
\begin{equation}\label{prelimdifference}
 {\rm St}_k(n+2^{m}) - {\rm St}_k(n) \equiv 0   \pmod{2^{m-{{b}}_k}}.
 \end{equation}
Combining this with (\ref{prelimperiodic}), we see that  (\ref{prelimdifference}) holds
whenever $n \ge m - {{b}}_k + \nu_2(k!)$, and so  ${\rm St}_k([n]_{2^{m}})$ is constant modulo $2^{m-{{b}}_k} .$
\end{proof}

Using Proposition \ref{kwongext}, we demonstrate that our search for classes $[n]_{2^m}$ on which $\nu_2 \circ {\rm St}_k$ is non-constant can be restricted to those such that ${\rm St}_k(n) \equiv 0 \pmod{2^{m-{{b}}_k}}$.


\begin{proposition}\label{translateSnu}
Let $k,m,n$ be non-negative integers such that
$n \ge k \ge 5$, $m \ge {{b}}_k$ and $2^m \ge m- {{b}}_k + \nu_2(k!)$.
If $\nu_2 \circ {\rm St}_k \mbox{ is non-constant on } [n]_{2^{m}}$, then
$${\rm St}_k([n]_{2^{m}}) \equiv 0 \pmod{2^{m-{{b}}_k}}.$$
\end{proposition}
\begin{proof}
We demonstrate the contrapositive.
By Proposition \ref{kwongext}, ${\rm St}_k([n]_{2^m})$ is constant modulo $2^{m-{{b}}_k}$, and so there exists  $s \in {\mathbb{N}}$ with $s < 2^{m-{{b}}_k}$ such that
\begin{equation}
{\rm St}_k([n]_{2^{m}}) \equiv s \pmod{2^{m-{{b}}_k}}.
\end{equation}
Since we are assuming that
${\rm St}_k([n]_{2^{m}}) \not\equiv 0 \pmod{2^{m-{{b}}_k}}$,
it follows that $s \neq 0$.
Consequently, the 2-adic valuation of every element of $S([n]_{2^{m+{{b}}_k}},k)$ is $\nu_2(s)$.
\end{proof}


The next two sections examine when the converse of Proposition \ref{translateSnu} holds.

\section{General framework}

Proposition \ref{translateSnu} gives us a sufficient condition for $\nu_2\circ {\rm St}_k$ to be constant on a congruence class.  In the cases that $k\in\{5,6\}$, as we shall see, it turns out that this condition is also necessary.  Numerically, we suspect that there are infinitely many values of $k$ for which the congruence condition is necessary; however, for $k$ chosen at random, the probability appears to be small.  Our goal in this section is to focus on the relationship between congruence classes and their children regarding whether or not $\nu_2\circ {\rm St}_k$ is constant.

We begin by stating the following simple lemma without proof.
\begin{lemma}\label{constantclasses}
Let $k,m,n$ be non-negative integers such that $n  \ge k$.
If $\nu_2 \circ {\rm St}_k$ is  constant on $[n]_{2^{m}}$,
then it is  constant on both of its children.
\end{lemma}

If $\nu_2 \circ {\rm St}_k$ is not constant on a given congruence class, then describing the behavior of $\nu_2 \circ {\rm St}_k$ on the children of the congruence class is more subtle.  Below we produce a sufficient result for $\nu_2 \circ {\rm St}_k$ to be non-constant on the children of a given congruence class.








\begin{lemma}\label{S2nu}
Let $k,\ell,M,n$ be non-negative integers such that
$n \ge k \ge 5$, $M \ge {{b}}_k$ and
$2^M \ge M- {{b}}_k + \nu_2(k!)$.
  Suppose the following four conditions hold
for all $m \ge M$.
\begin{enumerate}
\item[(i)] ${\rm St}_k([n]_{2^{m  }}) \mbox{ is not constant modulo  } 2^{m-{{b}}_k + \ell+1}$.

\item[(ii)] ${\rm St}_k([n]_{2^{m  }})$ is constant modulo  $2^{m-{{b}}_k+\ell}$.


\item[(iii)] ${\rm St}_k([n]_{2^{m+1  }})$ is constant modulo  $2^{m-{{b}}_k+\ell+1}$.



\item[(iv)] ${\rm St}_k([n+2^{m}]_{2^{m+1  }})$ is constant modulo  $2^{m-{{b}}_k+\ell+1}$.



\end{enumerate}
Then for all $m \ge M$, if $\nu_2 \circ {\rm St}_k$ is non-constant on $[n]_{2^{m}}$,
then it is non-constant on exactly one of its children.
\end{lemma}

Before proceeding with the proof, we provide an example.  For $k=6$, we have $b_k =5$, and we will see in Section
\ref{k5} that for $m \ge 3$ and any non-negative integer $n$,
\begin{equation*}
{\rm St}_{5}([n]_{2^m}) \mbox{ is constant modulo }  2^{m-1}
\end{equation*}
and
\begin{equation*}
{\rm St}_{5}([n]_{2^m}) \mbox{ is not constant modulo }  2^{m}.
\end{equation*}
By selecting $\ell=0$, conditions (i) through (iv) all immediately follow. Consequently,  the AMM conjecture immediately follows from the lemma.  For $k=7$, the scenario is much more complex.  In fact, the conditions above do not hold for all values of $n$.  Fortunately, however, these conditions do appear to hold at least for the values of $n$ when $\nu_2 \circ {\rm St}_k$ is non-constant on $[n]_{2^{m}}$.   Details are provided in Section \ref{k7}.


\begin{proof}  Let $m \ge M$.
First, we note that since each term of $[n]_{2^m}$ is at least $2^m$, we may assume without loss of generality that
$n \ge 2^m$,
and since $\nu_2(k!) \ge {{b}}_k$ for all $k$,
$$n \ge 2^{m-M} \cdot 2^M \ge 2^{m-M} (M - {{b}}_k + \nu_2(k!)) \ge 2^{m-M} \cdot M  -{{b}}_k + \nu_2(k!).$$
A simple exercise reveals that $2^{m-M} \cdot M \ge m$, which yields the inequality
$$ n \ge m -{{b}}_k + \nu_2(k!).$$
Note that   by condition (ii) ${\rm St}_k([n]_{2^{m}})$ is constant modulo $2^{m-{{b}}_k+\ell}$; it then necessarily follows that
\begin{equation}\label{constantj}
{\rm St}_k([n]_{2^{m}}) \mbox{ is constant modulo } 2^{m-{{b}}_k+j}
\end{equation} for all $0 \le j \le \ell$.  Using this, we will  inductively demonstrate that
\begin{equation}\label{Snmodj}
{\rm St}_k([n]_{2^{m}}) \equiv 0 \pmod{2^{m-{{b}}_k+j}}
\end{equation}
 for $0 \le j \le \ell$.


Assuming $\nu_2 \circ {\rm St}_k$ is non-constant on $[n]_{2^{m}}$, we know by Proposition \ref{translateSnu} that ${\rm St}_k([n]_{2^{m}})  \equiv 0  \pmod{2^{m-{{b}}_k}}$, thus justifying (\ref{Snmodj}) when $j=0$.
We proceed by induction, demonstrating that if (\ref{Snmodj}) holds for a particular value of $j$ such that $0 \le j \le \ell-1$, then it must also hold for $j+1$.


Since $1 \le j+1 \le \ell$, it follows from (\ref{constantj}) that ${\rm St}_k([n]_{2^{m}})$ is constant modulo  $2^{m-{{b}}_k+j+1}$.  Since we are assuming
${\rm St}_k([n]_{2^{m}}) \equiv 0 \pmod{2^{m-{{b}}_k+j}}$, it follows that every element of
${\rm St}_k([n]_{2^{m}})$ is congruent to either 0 or $2^{m-{{b}}_k+j}$ modulo $2^{m-{{b}}_k+j+1}$.  Since ${\rm St}_k([n]_{2^{m}})$ is constant modulo  $2^{m-{{b}}_k+j+1}$, it follows that either ${\rm St}_k([n]_{2^{m}}) \equiv 0 \pmod{2^{m-{{b}}_k+j+1}}$ or
${\rm St}_k([n]_{2^{m}}) \equiv 2^{m-{{b}}_k+j} \pmod{2^{m-{{b}}_k+j+1}}$.
If the latter holds, then
$\nu_2({\rm St}_k([n]_{2^{m}}) ) = \{ m-{{b}}_k+j\}$, contradicting the assumption that $\nu_2$ is non-constant on ${\rm St}_k([n]_{2^{m}})$.  Consequently, ${\rm St}_k([n]_{2^{m}}) \equiv 0 \pmod{2^{m-{{b}}_k+j+1}}$, and so (\ref{Snmodj}) holds for $j+1$, as desired.

We have just demonstrated that (\ref{Snmodj}) holds for $ 0 \le j \le \ell$, and so, in particular,
$${\rm St}_k([n]_{2^{m}}) \equiv 0 \pmod{2^{m-{{b}}_k+\ell}}.$$
Therefore, each element of ${\rm St}_k([n]_{2^m})$ is congruent to either $0$ or $2^{m-{{b}}_k + \ell}$ modulo $2^{m - {{b}}_k + \ell + 1}$.
Moreover, by conditions (iii) and (iv), we know that
${\rm St}_k([n]_{2^{m+1}})$
 and  ${\rm St}_k([n+2^m]_{2^{m+1}})$ are both constant modulo $2^{m-{{b}}_k+\ell+1}$.
Since by condition (i),  ${\rm St}_k([n]_{2^{m  }}) \mbox{ is not constant modulo  } 2^{m-{{b}}_k + \ell+1}$, it follows that either
\begin{equation}\label{step1}
{\rm St}_k([n]_{2^{m+1}}) \equiv 0 \pmod{2^{m-{{b}}_k+\ell+1}}
\end{equation}
 and
\begin{equation}\label{step2}
{\rm St}_k([n+2^m]_{2^{m+1}}) \equiv 2^{m-{{b}}_k+\ell} \pmod{2^{m-{{b}}_k+\ell+1}}
\end{equation}
both hold, or
\begin{equation}\label{step3}
{\rm St}_k([n]_{2^{m+1}}) \equiv 2^{m-{{b}}_k+\ell} \pmod{2^{m-{{b}}_k+\ell+1}}
\end{equation} and
\begin{equation}\label{step4}
{\rm St}_k([n+2^m]_{2^{m+1}}) \equiv 0 \pmod{2^{m-{{b}}_k+\ell+1}}
\end{equation}
both hold.  Suppose conditions (\ref{step1}) and (\ref{step2}) hold.
By (\ref{step2}), we see that
$\nu_2$ is constant on ${\rm St}_k([n+2^{m}]_{2^{m+1}})$.  Since
$\nu_2$ is not constant on ${\rm St}_k([n]_{2^{m}})$, it follows that
$\nu_2$ cannot be  constant on both  ${\rm St}_k([n]_{2^{m+1}})$
and ${\rm St}_k([n+2^{m}]_{2^{m+1}})$.
Therefore, $\nu_2$ is not constant on ${\rm St}_k([n]_{2^{m+1}})$.

Similarly, if conditions (\ref{step3}) and (\ref{step4}) hold, then  it can be shown that $\nu_2$ is constant on ${\rm St}_k([n]_{2^{m+1}})$ but is not constant on ${\rm St}_k([n+2^{m}]_{2^{m+1}})$.
\end{proof}


Using this lemma, we are now in a position to prove Theorem \ref{maintheorem}.

\begin{proof}  First, we note by Definition \ref{Nkm},  there are $\#{\mathcal N}_{k,m}$ congruence classes at level $m$ on which $\nu_2 \circ {\rm St}_k$ is non-constant.  Therefore, $\nu_2 \circ {\rm St}_k$ is constant on the remaining congruence classes at level $m$.  By Lemma \ref{constantclasses}, $\nu_2 \circ {\rm St}_k$ is constant on each of the children of those classes.

Therefore, if we can demonstrate that for each congruence class at level $m \ge M$ on which $\nu_2 \circ {\rm St}_k$ is non-constant, the function $\nu_2 \circ {\rm St}_k$ is non-constant on exactly one of its children, then we will have demonstrated both parts (a) and (b) of the AMM conjecture with $\mu_k = \#{\mathcal N}_{k,m}$ and $M_k \le M$.

Suppose  $m,n$ are integers such that $m \ge M$ and
$n \ge k$
where $\nu_2 \circ {\rm St}_k$ is non-constant on $[n]_{2^m}$.    Since $\nu_2 \circ {\rm St}_k$ is non-constant on $[n]_{2^m}$, it follows that $\nu_2 \circ {\rm St}_k$ is non-constant on $[n]_{2^M}$, and so  there exists an integer $j \in {\mathcal N}_{k,M}$ such that  $n \equiv j \pmod{2^M}$.  By assumption, we
have conditions (i) and (ii) above:
  \begin{equation}\label{condi}
{\rm St}_k([n]_{2^{m  }}) \mbox{ is not constant modulo } 2^{m-{{b}}_k + \ell_j+1}
\end{equation}
and
\begin{equation}\label{condii}
{\rm St}_k([n]_{2^{m  }}) \mbox{ is  constant modulo } 2^{m-{{b}}_k + \ell_j}.
\end{equation}
Moreover, since  (\ref{condii}) actually holds for any value of $m \ge M$, replacing $m$ by $m+1$ reveals  that \begin{equation}\label{condiii}
{\rm St}_k([n]_{2^{m+1  }}) \mbox{ is constant modulo } 2^{m-{{b}}_k+\ell_j+1}.
\end{equation}
Since  $m \ge M$, we have that $n + 2^m \equiv j \pmod{2^M}$, and so we can replace $n$ by $n+2^m$ to obtain
\begin{equation}\label{condiv}
{\rm St}_k([n+2^{m}]_{2^{m+1  }}) \mbox{ is constant modulo } 2^{m-{{b}}_k+\ell_j+1}.
\end{equation}
Since (\ref{condi}),
 (\ref{condii}),
  (\ref{condiii}),
  and  (\ref{condiv}) represent conditions (i), (ii), (iii), and (iv), respectively,  of Lemma \ref{S2nu}, it follows that $\nu_2 \circ {\rm St}_k$ is non-constant on exactly one of $[n]_{2^{m+1}}$ and $[n+2^m]_{2^{m+1}}$.
\end{proof}





\section{Computational framework}\label{framework}

In this section, we provide a method for determining when sets of the form ${\rm St}_k([n]_{2^m})$  are constant modulo specific powers of 2.  We then use this method in Section \ref{examples} to perform finite checks that  verify the AMM conjecture via Theorem \ref{maintheorem}.
We begin with the following lemma, which translates the condition that ${\rm St}_k([n]_{2^m})$ is constant modulo $2^{m-{{b}}_k+\ell}$ into a statement about an auxiliary function $f_k(n)$.


\begin{lemma}\label{fStcorrespondence}
Let $k, \ell, n$ be positive integers such that $k \ge 5$, and
define
$s=  \nu_2(k!) + \ell - {{b}}_k -3$.
Define $f_k: {\mathbb{N}} \to {\mathbb{N}}$ by
\begin{equation}\label{deff}
f_k(n) = \sum_{i=1}^{\lceil k/2 \rceil}
  {k\choose t_i}{t_i}^n ({t_i}^{2^{s+1}} - 1)
  \end{equation}
  where $t_i = 2i-1$.
 Suppose $m$ is an integer such that $m \ge s+1$ and $2^m - m \ge s+3$.  If $n \ge 2^m$, then
  $${\rm St}_k(n+2^m) \equiv {\rm St}_k(n)  \pmod{2^{m-{{b}}_k+\ell}}$$ if and only if
  $$f_k(n) \equiv 0 \pmod{2^{2s+4}}.$$
\end{lemma}

\begin{proof}
By (\ref{Stirlingsum2}), we
 can rewrite the condition
 $${\rm St}_k(n+2^m) \equiv {\rm St}_k(n)  \pmod{2^{m-{{b}}_k+\ell}}$$
as\begin{equation*}
\sum_{t=1}^{k}  (-1)^t {k\choose t}t^{n+2^m} \equiv
\sum_{t=1}^{k}  (-1)^t {k\choose t}t^{n} \pmod{2^{m+s+3}},
\end{equation*}
which, in turn, can be rewritten as
\begin{equation}\label{diffSt}
\sum_{{t=1}}^{k}  (-1)^t {k\choose t}t^{n}(t^{ 2^m}-1) \equiv
0 \pmod{2^{m+s+3}}.
\end{equation}
Since we are assuming that $n \ge 2^m$ and  $2^m -m \ge s+3$, it follows that $n \ge m +s+3$.
Thus, $t^n \equiv 0 \pmod{2^{m+s+3}}$ whenever $t$ is even,
and so (\ref{diffSt}) can be expressed as
\begin{equation}\label{abbrevsum}
\sum_{i=1}^{\lceil k/2 \rceil}
  {k\choose t_i}{t_i}^{n}(t_i^{2^m}-1) \equiv
0 \pmod{2^{m+s+3}},
\end{equation}
where $t_i =2i-1$.
Since $s=  \nu_2(k!) + \ell - {{b}}_k -3$, we know by Proposition \ref{binrep} that for all $m \ge s+1$,
\begin{equation}\label{binrepreplace}
{t_i}^{2^{m}} -1 \equiv  \sum_{j=0}^{s} c_{i,j}2^{m+2+j} \pmod{2^{m+s+3}},
\end{equation}
where $c_{i,0}, c_{i,1} \dots, c_{i,s}$ is comprised of the first $s+1$ digits of the binary representation of the integer $({t_i}^{2^{s+1}} - 1)/2^{s+3}$.
Substituting this into (\ref{abbrevsum}), we obtain the following equivalent statement:
\begin{equation*}
\sum_{i=1}^{\lceil k/2 \rceil}
  {k\choose t_i}{t_i}^{n}\left( \sum_{j=0}^{s} c_{i,j}2^{m+2+j}\right) \equiv
0 \pmod{2^{m+s+3}}.
\end{equation*}
Multiplying both sides by $2^{s-m+1}$, we
obtain
\begin{equation}\label{simplifiedcongruence}
\sum_{i=1}^{\lceil k/2 \rceil}
  {k\choose t_i}{t_i}^{n} \left( \sum_{j=0}^{s} c_{i,j}2^{s+3+j}\right) \equiv
0 \pmod{2^{2s+4}}.
\end{equation}
Since (\ref{binrepreplace}) holds whenever $m \ge s+1$, we can replace $m$ by $s+1$ to obtain
$${t_i}^{2^{s+1}} -1 \equiv  \sum_{j=0}^{s} c_{i,j}2^{s+3+j} \pmod{2^{2s+4 }},
$$
and so by substituting this expression into (\ref{simplifiedcongruence}) produces \begin{equation}\label{checkfunction}
\sum_{i=1}^{\lceil k/2 \rceil}
  {k\choose t_i}{t_i}^{n } \left({t_i}^{2^{s+1}} -1\right)\equiv
0 \pmod{2^{2s+4}},
\end{equation}
which is simply the statement that $f_k(n) \equiv 0 \pmod{2^{2s+4}}$.
\end{proof}



We are now in a position to determine when
${\rm St}_k([n]_{2^{m  }})$  is  constant modulo  $2^{m-{{b}}_k + \ell}$ given appropriate choices of $n$, $m$, and $\ell$.   Using Lemma \ref{fStcorrespondence}, we reduce this problem to a finite check.


\begin{proposition}\label{finitecheckconstant}
Let $k, \ell$ be positive integers such that $k \ge 5$, and
define
$s=  \nu_2(k!) + \ell - {{b}}_k -3$.
Let $f_k: {\mathbb{N}} \to {\mathbb{N}}$ be the function  described in (\ref{deff})
  where $t_i = 2i-1$.
Then for all $n \ge k$, the following three statements are equivalent.
\begin{enumerate}
\item[(i)] $f_k(n) \equiv 0 \pmod{2^{2s+4}}$.
\item[(ii)] ${\rm St}_k([n]_{2^{m}})$ is constant modulo $2^{m-{{b}}_k+\ell}$ for all
 integers $m \ge s+1$ such that $2^m - m \ge s+3$.
\item[(iii)] ${\rm St}_k([n]_{2^{m}})$ is constant modulo $2^{m-{{b}}_k+\ell}$ for some
 integer $m \ge s+1$ such that $2^m - m \ge s+3$.
\end{enumerate}
\end{proposition}

\begin{proof}
We will prove $\mbox{(i)} \Rightarrow \mbox{(ii)} \Rightarrow \mbox{(iii)} \Rightarrow \mbox{(i)}$.  Before proceeding, we argue that we can assume without loss of generality that $n \ge 2^m$.
Indeed, if $m$ is an integer such that
$m \ge s+1$ and $2^m - m \ge s+3$, we have that
$2^m \ge 2s+4$.    Consequently, by using Lemma \ref{odd-order}, it can be shown that $f_k(n) \equiv f_k(n+2^m) \pmod{2^{2s+4}}$, and so when considering part (i), it is sufficient to consider the case that $n \ge 2^m$.  Moreover, for parts (ii) and (iii), the congruence class $[n]_{2^m}$ solely consists of integers greater than $2^m$, in which case it is also sufficient to consider the case where $n \ge 2^m$.

Now, suppose (i) holds for a fixed integer $n\ge k$, and let $m$ be an integer such that  $m \ge s+1$ and $2^m - m \ge s+3$, in which case
$2^m \ge 2s+4$.  Consequently,  by Lemma \ref{odd-order}, we have $t_i^{2^m} \equiv 1 \pmod{2^{2s+4}}$, and so $f_k(n) \equiv f_k(n+2^m) \pmod{2^{2s+4}}$.    In fact, multiple applications of Lemma \ref{odd-order} reveal that
$f_k(n) \equiv f_k(n+j \cdot 2^m) \pmod{2^{2s+4}}$
for all $j\in {\mathbb{N}}$, and so
$f_k([n]_{2^m}) \equiv 0 \pmod{2^{2s+4}}.$
Therefore, by Lemma \ref{fStcorrespondence},
 ${\rm St}_k([n]_{2^{m}})$ is constant modulo $2^{m-{{b}}_k+\ell}$, and so (ii) holds.

The fact that (ii) $\Rightarrow$ (iii) follows trivially.   Now, assuming (iii), we have that  ${\rm St}_k([n]_{2^{m}})$ is constant modulo $2^{m-{{b}}_k+\ell}$
for some integer $m \ge s+1$ such that $2^m - m \ge s+3$.
Therefore, by Lemma \ref{fStcorrespondence},
 $f_k(n) \equiv 0 \pmod{2^{2s+4}}$, which is precisely statement (i).
\end{proof}



We also need a method for determining when $\nu_2 \circ {\rm St}_k$ is constant on individual congruence classes of the form $[n]_{2^m}$, which is easily described in the following proposition.





\begin{proposition}\label{algconstclass}
Let $k$ and $m$ be non-negative integers such that
$n \ge k \ge 5$, $m \ge {{b}}_k$ and $2^m \ge m- {{b}}_k + \nu_2(k!)$.
 Let $r \in [n]_{2^m},$
 and define $c = (\nu_2 \circ {\rm St}_k)(r)$.
 \begin{enumerate}
\item[(a)]   If $m > c + {{b}}_k$, then $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$.
\item[(b)] If $m \le c + {{b}}_k$, then $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$ if and only if for all $j\in {\mathbb{N}}$ such that $1 \le j \le 2^{c+ {{b}}_k - m}$,
$$ {\rm St}_k(n+  j \cdot 2^m) \equiv 0 \pmod{2^c}$$
and  $$ {\rm St}_k(n+ j \cdot 2^m) \not\equiv 0 \pmod{2^{c+1}}.$$
\end{enumerate}
\end{proposition}

\begin{proof}
For part (a), we  have $m > c+ {{b}}_k$.   Since $(\nu_2\circ {\rm St}_k)(r) = c$, it follows that
${\rm St}_k(r) \equiv 0 \pmod{2^c}$ but
${\rm St}_k(r) \not\equiv 0 \pmod{2^{c+1}}$.
By Proposition \ref{kwongext},
we have ${\rm St}_k([n]_{2^{c+{{b}}_k}})$ is constant modulo $2^c$.
Since $m > c+{{b}}_k$, it follows that  ${\rm St}_k([n]_{2^m})$ is constant modulo $2^c$.
Since $r \in [n]_{2^m}$ and ${\rm St}_k(r) \equiv 0  \pmod{2^c}$, we have that ${\rm St}_k([n]_{2^m}) \equiv 0 \pmod{2^c}$.  Thus, $\nu_2({\rm St}_k(i)) \ge c$ for all $i \in [n]_{2^m}$, and we have only left to demonstrate that $\nu_2({\rm St}_k(i)) < c+1$ for all $i \in [n]_{2^m}$.


By Proposition \ref{kwongext}, we have that ${\rm St}_k([n]_{2^{c+1 + {{b}}_k}})$ is constant modulo $2^{c+1}$.  Since $m > c + {{b}}_k$, we know $m \ge c+1+{{b}}_k$, and so ${\rm St}_k([n]_{2^m})$ is constant modulo $2^{c+1}$.
    Since $j \in [n]_{2^m}$ and ${\rm St}_k(j) \not\equiv 0 \pmod{2^{c+1}}$, it follows that for all $i \in[n]_{2^m}$ we have that  ${\rm St}_k(i) \not\equiv 0 \pmod{2^{c+1}}$, in which case
$\nu_2({\rm St}_k(i)) < c+1$ , as desired.


For part (b), we consider the case $m \le c + {{b}}_k$.    If $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$, then $\nu_2 \circ {\rm St}_k ([n]_{2^m}) = c$.
In this case, ${\rm St}_k([n]_{2^m}) \equiv 0 \pmod{2^c}$ but
${\rm St}_k(i) \not\equiv 0 \pmod{2^{c+1}}$ for all $i \in [n]_{2^m}$.
For each $j \in {\mathbb{N}}$ such that $1 \le j < 2^{c-{{b}}_k-m}$, we have $n + j \cdot 2^m \in [n]_{2^m}$, and so the conclusion follows.

Conversely, we assume that for all $j \in {\mathbb{N}}$ such that $1 \le j \le 2^{c-{{b}}_k -m}$,
\begin{equation}\label{cong0}
{\rm St}_k(n+j \cdot 2^m) \equiv 0 \pmod{2^c}
\end{equation}
and
\begin{equation}\label{notcong0}
{\rm St}_k(n+j \cdot 2^m) \not\equiv 0 \pmod{2^{c+1}}.
\end{equation}
We will show that for any $b\in[n]_{2^m}$, we have $\nu_2({\rm St}_k(b))=c$, thus demonstrating
that $\nu_2 \circ {\rm St}_k$ is constant on $[n]_{2^m}$.  Since $b \in [n]_{2^m}$, we have that $b= n + i \cdot 2^m$
for some $i\in {\mathbb{N}}$.  Select $j\in {\mathbb{N}}$ such that $1 \le j \le 2^{c-{{b}}_k-m}$ and $i \equiv j \pmod{2^{c-{{b}}_k -m}}$, in which case
$$b = n + i \cdot 2^m \equiv n+ j \cdot 2^m \pmod{2^{c-{{b}}_k}}.$$
Thus, by Proposition \ref{kwongext}, it follows that
$${\rm St}_k(b) \equiv {\rm St}_k(n+ j \cdot 2^m) \pmod{2^c},$$
and so by (\ref{cong0}), we have that ${\rm St}_k(b) \equiv 0 \pmod{2^c}$.  Similarly, by using Proposition \ref{kwongext} in conjunction with (\ref{notcong0}), we have that ${\rm St}_k(b) \not\equiv 0 \pmod{2^{c+1}}.$  Therefore, $\nu_2({\rm St}_k(b)) = c$.
\end{proof}










Using the results from this section in conjunction with Theorem \ref{maintheorem}, we have a method of verifying the AMM conjecture for different values of $k$.  In the next section, we put this method into practice.


\section{Examples}\label{examples}

In this section, we  begin with $k=5$ in order to demonstrate how to reproduce the result of Amdeberhan, Manna, and Moll  \cite{Am}  by using the techniques developed in this paper.  Next, we consider $k=6, 7, 13$ and $15$ in order to compare the behavior of $\nu_2 \circ {\rm St}_k$ for values of $k$ other than $5$.   The case $k=6$ is very similar to that of $k=5$, but  the scenario is  more complex when $k=7$, as the behavior depends on the parity of $n$.  We then close with the case $k=13$, which exhibits even more complex behaviors.

Before going into specific examples, we describe the general approach.  The goal is to apply Theorem \ref{maintheorem} for a given choice of $k$, which requires establishing conditions (i) and (ii) of that theorem.  That is, we need to investigate whether ${ St}_k([n]_{2^m})$ is constant modulo $2^{m-b_k+\ell_j}$ but not constant modulo $2^{m-b_k+\ell_j+1}$.  Proposition \ref{kwongext} and Proposition \ref{finitecheckconstant} give us methods for checking these congruences.  Unfortunately, however, each of these require certain minimal values of $m$.  The significant bound is
$$
m \ge s+1=\nu_2(k!)+\ell-{{b}}_k-3,
$$
where $\ell$ must be determined to ensure that $f_k(n)\equiv 0\pmod{2^{2s+4}}$.  (For small values of $m$, we will also need to check that $2^m-m\ge s+3$.)   Once $\ell$ is determined, we can prove Theorem \ref{maintheorem} for all but a small number of values of $m$ using {\sl Mathematica} to perform the necessary calculations.  The cases for small $m$ can then be handled by the use of Proposition \ref{algconstclass}.   At this point, we have then verified Conecture \ref{mollconjecture} for the given value of $k$.

The above is essentially how our computer proof works, except that in a few cases we need a little additional information (as will be discussed in the example of $k=13$, the only value for $k \le 20$ that requires this information).   It appears that the approach we use may require more computation than absolutely necessary, which we shall discuss further when we look at the case of $k=13$.



\subsection{$k=5$ and $k=6$}\label{k5}


We begin by considering the case $k=5$. We note that ${{b}}_5 = \lceil \log_2(5) \rceil -2 =1$ and $\nu_2(5!) = 3$, and so $s=3+\ell-1-3=\ell-1$.  Thus $m\ge \ell$.  However, if $\ell=1$ or $2$, the condition that $2^m - m \ge s+3$ is violated for small values of $m$, and so we know that we must use Proposition \ref{algconstclass} to check whether both $m=1$ and $m=2$ satisfy the conjecture.   Using the proposition, we can computationally determine whether $\nu_2 \circ {\rm St}_{5}$ is constant on $[n]_{2^m}$ for a given choice of $n$ and $m$.  Using the notation from Defintion \ref{Nkm}, with the aid of {\sl Mathematica}, we determine the following: ${\mathcal N}_{5,1} = \{5,6\}$, ${\mathcal N}_{5,2} = \{7,8\}$ and ${\mathcal N}_{5,3} = \{7,12\}$.  For $m\ge 3$, we  turn to our general argument.

By Proposition \ref{kwongext}, for $m \ge 3$,
\begin{equation}
{\rm St}_{5}([n]_{2^m}) \mbox{ is constant modulo }  2^{m-1}.
\end{equation}
If  $\ell =1$, then $s= \nu_2(5!) + \ell - {{b}}_5 - 3 = 0$ and so by
Proposition \ref{finitecheckconstant}, ${\rm St}_{5}([n]_{2^m})$ is constant modulo $2^m$ whenever  $m \ge 3$ if and only
$f_5(n) \not\equiv 0 \pmod{2^4}$.  We will check the case $n=7$ here.
\begin{eqnarray*}
f_5(7) & = & {5\choose 1}1^7(1^{2^1}-1) + {5\choose 3}3^7(3^{2^1}-1)  + {5\choose 5}5^7(5^{2^1}-1)  \pmod{2^4} \\
  & = & 0 + 10\cdot11\cdot 8 + 1\cdot13\cdot8 \pmod{2^4} \\
  & = & 8 \pmod{2^4} \\
  & \not\equiv & 0 \pmod{2^4}.
\end{eqnarray*}
{\sl Mathematica} needs only a finite check (since we are working modulo $2^4$) to show the non-congruence for all $n$.  Thus,  we conclude that for all $m \ge 3$,
\begin{equation}
{\rm St}_{5}([n]_{2^m}) \mbox{ is not constant modulo }  2^{m}.
\end{equation}

Now, if we select $M=3$, we see that ${\mathcal N}_{5,3} = \{7,12\}$, and if we define $\ell_7 = \ell_{12} = 3$, then parts (i) and (ii) of Theorem \ref{maintheorem} hold for all non-negative integers.  (In fact, in order to apply Theorem \ref{maintheorem}, we only need these two parts to hold when $n$ is congruent to either $7$ or $12$ modulo $8$.)
Thus, we have that the AMM conjecture holds with $\mu_5 = \#{\mathcal N}_{5,3} = 2$ and $M_5 \le 3$.  In fact, since we have verified the conjecture for levels $m=1$ and $m=2$, it follows that $M_5=1$.



When $k=6$, the result follows very similarly.  Using Proposition \ref{algconstclass} and  {\sl Mathematica}, we find that
${\mathcal N}_{6,1} = \{6,7  \}$, ${\mathcal N}_{6,2} = \{ 8,9   \}$ and ${\mathcal N}_{6,3} = \{ 12, 13  \}$.
When $k=6$, we note that  ${{b}}_6 = \lceil \log_2(6) \rceil -2 =1$ and
$\nu_2(6!) = 4$. By Proposition \ref{kwongext}, for $m \ge 3$,
\begin{equation}
{\rm St}_6([n]_{2^m}) \mbox{ is constant modulo }  2^{m-1}.
\end{equation}
 Using Proposition \ref{finitecheckconstant} in a manner similar to that for $k=5$, we  we conclude that for all $m \ge 3$,
\begin{equation}
{\rm St}_6([n]_{2^m}) \mbox{ is not constant modulo }  2^{m}.
\end{equation}
Again, as in the case when $k=5$, an application of Theorem \ref{maintheorem} justifies that the AMM conjecture holds for $k=6$
with  $\mu_6=2$ and $M_6\le 3$, and since we already determined that the conjecture holds for levels $m=1$ and $m=2$, it follows that $M_6=1$.

The calculations for $k=6$ are of roughly the same magnitude as those for $k=5$, and in both cases, they are not dissimilar from the proof for $k=5$ given by Amdeberhan, Manna, and Moll.  One aspect in both of these cases is that $n\in {\mathcal N}_{k,m}$ if and only if ${\rm St}_k[k]([n]_{2^{m+{{b}}{k}}})\equiv 0 \pmod{2^m}$.  That is, the converse of Proposition \ref{translateSnu} holds.

\subsection{$k=7$}\label{k7}

Although the behavior exhibited by $\nu_2 \circ {\rm St}_k$ is similar for the cases $k=5$ and $k=6$, the landscape changes when $k=7$.   By Proposition \ref{kwongext}, for $m \ge 3$,
\begin{equation}\label{k=7,m-1}
{\rm St}_7([n]_{2^m}) \mbox{ is constant modulo }  2^{m-1}.
\end{equation}
Using Proposition \ref{finitecheckconstant} with $\ell = 1$ in conjunction with {\sl Mathematica}, we find that for $m \ge 3$
\begin{equation}\label{k=7,m}
{\rm St}_7([n]_{2^m}) \mbox{ is not constant modulo $2^{m}$ if and only if $n$ is odd}.
\end{equation}
In fact, since (\ref{k=7,m-1}) follows directly from (\ref{k=7,m}), we did not actually need to apply Proposition \ref{kwongext} for the case $k=7$.
Using Proposition \ref{finitecheckconstant}  with $\ell = 2$, we find that for $m \ge 3$, \begin{equation}\label{k=7,m+1}
{\rm St}_7([n]_{2^m}) \mbox{ is not  constant modulo }  2^{m+1} \mbox{ if and only if $n$ is odd}.
\end{equation}
Applying Proposition \ref{finitecheckconstant} with $\ell = 3$ yields the following for all non-negative integers when $m \ge 4$:
\begin{equation}\label{k=7,m+2}
{\rm St}_7([n]_{2^m}) \mbox{ is not  constant modulo }  2^{m+2}.
\end{equation}
As with the cases $k=5$ and $k=6$,  it is possible to determine ${\mathcal N}_{7,4}$ explicitly.  However, we demonstrate that this is not necessary when justifying that the AMM conjecture holds.  Fix $M=4$, and consider $j \in {\mathcal N}_{7,4}$.   Whenever $j$ is odd, define $\ell_j =  1$, and whenever $j$ is even, define $\ell_j = 2$.  Thus, whenever $n$ is odd, we see that (\ref{k=7,m+1}) and (\ref{k=7,m}), constitute parts (i) and (ii) of Theorem \ref{maintheorem}, respectively.  In addition, whenever $n$ is even,
(\ref{k=7,m+2}) and (\ref{k=7,m+1}) constitute parts (i) and (ii) of Theorem \ref{maintheorem}, respectively.
Putting this together, we see that the AMM conjecture holds for $k=7$ with $M_7 \le 4$.

At this point, it makes sense to say a few words about the role that $\ell$ plays as well as the link between ${\rm St}_k([n]_{2^{m+{{b}}_k}})\equiv 0 \pmod{2^{m}}$ and $n\in {\mathcal N}_{k,m}$.  When $\ell=1$, we have for exactly one child (say $x$) of $[n]_{2^{m+{{b}}_k}}$ that ${\rm St}_k([x]_{2^{m+{{b}}_k+1}})\equiv 0 \pmod{2^{m+1}}$ and $x\in {\mathcal N}_{k,m+1}$. However, when $\ell>1$, both children have the property of ${\rm St}_k([x]_{2^{m+{{b}}_k+1}})\equiv 0 \pmod{2^{m+1}}$, but we know that only one lies in $ {\mathcal N}_{k,m}$.  The value of $\ell$ essentially tells you how many generations of children of $n$ have the property of being congruent to $0$ for the appropriate power of $2$.  More precisely, when we calculate the sets ${\mathcal N}_{7,1}$, ${\mathcal N}_{7,2}$, ${\mathcal N}_{7,3}$, and ${\mathcal N}_{7,4}$, we have the following:
\begin{eqnarray*}
{\mathcal N}_{7,1} & = & \{7, 8\} \\
{\mathcal N}_{7,2} & = & \{9, 10\} \\
{\mathcal N}_{7,3} & = & \{13, 14\} \\
{\mathcal N}_{7,4} & = & \{13,14\}.
\end{eqnarray*}
While this looks similar to the cases $k=5$ and $k=6$, there is a difference in the behavior of the children regarding congruences to $0$ modulo $2^{m}$.  While ${\rm St}_7(7)\equiv {\rm St}_7(8)\equiv 0 \pmod{2^0}$, we see that $7$ and $9$ behave differently from $8$ and $10$.  In particular, ${\rm St}_7(8)\equiv  {\rm St}_7(10)\equiv 0 \pmod{2^1}$, but ${\rm St}_7(7)=1\not\equiv 0 \pmod{2^1}$.   In fact, it is more complicated when you look at $10$.  In this case, both the children and the grandchildren are congruent to $0$ modulo the appropriate power of $2$.  Moreover, this pattern continues, which is why we had to choose different values of $\ell$ in the cases that $n$ was even and odd.  This more complex behavior is what appears to limit the proof method used  by Amdeberhan, Manna, and Moll.   Moreover, the case  $k=7$ is only the tip of the iceberg.  When $k=15$, each value of $\ell$ from $1$ to $4$ gives new congruence classes for $n$ with $f_{15}(n)\not\equiv 0 \pmod{2^{2s+4}}$.  On the bright side, however, similar to the case $k=7$ where $f_3(n)\not\equiv 0 \pmod{2^{2s+4}}$ for all $n$ whenever $\ell=3$, for $k=15$ we have a similar result for $\ell=4$.

\subsection{$k=13$}

The case $k=13$ is unique in that it is not sufficient to use Proposition \ref{kwongext} in conjunction with performing calculations according to Proposition \ref{finitecheckconstant}.
According to Proposition \ref{kwongext}, for $m \gg0$, we have
\begin{equation}\label{k=13,m-2}
{\rm St}_{13}([n]_{2^m}) \mbox{ is constant modulo }  2^{m-2}.
\end{equation}
For $m \gg 0$,  we can use Proposition \ref{finitecheckconstant} to determine that the following holds if and  only if $n \equiv 1, 2 \pmod{4}$:
\begin{equation}\label{k=13,m-1}
{\rm St}_{13}([n]_{2^m}) \mbox{ is not constant modulo }  2^{m-1}.
\end{equation}
In addition, for $m \gg 0$,  the following holds if and  only if $n \equiv 0, 1, 2 \pmod{4}$:
\begin{equation}\label{k=13,m}
{\rm St}_{13}([n]_{2^m}) \mbox{ is not constant modulo }  2^{m}.
\end{equation}
However, within our ability to calculate with {\sl Mathematica} there is no non-negative integer $\ell$ such that for sufficiently large $m$ such that for all $n\ge m$, $f_{13}(n)\not\equiv 0 \pmod{2^{s+4}}$.  In other words, there is no  non-negative integer $L$ such that the following holds for all non-negative integers $n$:
\begin{equation}\label{k=13,m+L}
{\rm St}_{13}([n]_{2^m}) \mbox{ is not constant modulo }  2^{m+L}.
\end{equation}
This peculiarity distinguishes the case $k=13$ from all other cases when $k\le 20$.  Fortunately, a finite check (using Proposition \ref{translateSnu}) verifies that
$\nu_2 \circ { St}_{13}$ is constant on the class $[n]_{2^m}$ whenever $n \equiv 3 \pmod{4}$, and so when employing Theorem \ref{maintheorem}, we only need to consider values of $n$ where $n \equiv 0,1,2 \pmod{4}$.  Consequently, statements (\ref{k=13,m-2}), (\ref{k=13,m-1}) and (\ref{k=13,m}) are sufficient for the purposes of validating the AMM conjecture.

This brings up a method to increase computational efficiency, but at some cost in terms of ease of programming.  Our algorithm  looks for a sufficient value of $\ell$ to guarantee that $f_k(n)\not\equiv 0\pmod{2^{2s+4}}$ for all $n$, but in cases like $k=13$, where finding such an $\ell$ is beyond our computing power, the program then performs a check to see whether the values of $n$ that we cannot guarantee the non-equivalence are constant.  However, we could use Proposition \ref{translateSnu} to check which $n$ we need to check for each $\ell$.  While this would lead to some improvement in the number of values of $k$ that we could check, the work in calculating $f_k(n) \pmod{2^{2s+4}}$ is a limiting factor since the magnitude of $s$ is largely dictated by $\nu_2(k!)$.

The case of $k=13$ also shows another complication in that $9\in {\mathcal N}_{13,3}$, but $[9]_{2^m}$ has no non-constant children.  Indeed, the number of congruence classes modulo $2^{m+{{b}}_k}$ for which Proposition \ref{translateSnu} does not rule out a non-constant class is $6$ for $m=1$, $8$ for $m=2$, $10$ for $m=3$ and $m=4$, $14$ for $m=5$, and then a constant $6$ for $m\ge 6$.  The case $k=13$ is the first such case where the congruence classes with this property are not (weakly) monotone with respect to $m$, and is the only case for $k<21$.



\subsection{General $k$}

The {\sl Mathematica} code that performs the calculations yielding the proof of the conjecture for $k\le 20$ is available at {\tt http://myweb.lmu.edu/emosteig}.  For these values of $k$, the largest choice of $\ell$ necessary is $4$ (in the case $k=15$).  In principle this code will work for any value of $k$ for which the conjecture holds true, and while we anticipate that we could further optimize the program to produce results for larger values of $k$, it also seems with the current ideas that the best we could hope for using these algorithms  would be $k\le 100$ (and in fact, $k=89$ appears to be require a very large value of $\ell$ based on the data we currently have).

\section{Further questions}

As we approached this problem, we collected a lot of data concerning which values of $n,m$ and $k$  the statement ${\rm St}_k([n]_{2^{m+{{b}}_k}}) \equiv 0 \pmod{2^m}$ holds true.  As might be expected by the requirement that $f_k(n)\not\equiv 0 \pmod{2^{2s+4}}$  together with $m\ge s+1$ in the computer-generated (as well as the hand-generated) proof, we often had more data than was fully needed for the proofs.  In addition, when $k$ is large, although our automated proof process is computationally infeasible due to the magnitude of $s$, we have a great deal of data that  suggests  many conjectures.  We close by describing  what appear to be the most tractable problems at this time.

The case where $k=2^t+1$ for some positive integer is extremely intriguing.  The data suggests several  results, which we are currently working on with a student.  In particular,
we have the following conjecture.
\begin{conjecture} \label{dinnerconjecture}
The AMM conjecture holds for $k=2^t+1$ for all integers $t\ge 2$.  Moreover, the following hold.
\begin{enumerate}
\item The parameter $\ell$ can be chosen equal to $1$.  That is, if $s=\nu_2(k!)+1-{{b}}_k-3= \nu_2(k!)+t-3$, $m\ge s+1$, and $2^m-m\ge s+3$, then $f_k(n)\not\equiv 0\pmod{2^{2s+4}}$ for all $n$.
\item  $M_k=1$.
\item $\mu_k=\#{\mathcal N}_{k,m}=2^{t-1}$ for all $m$.
\end{enumerate}
\end{conjecture}



A natural question arises about whether this work might apply to the work of Berrizbeitia {\em et. al.}
  \cite{BeMe}, where the authors look at the $p$-adic valuation of $S(n,k)$ where $p$ is an odd prime.  For small odd primes, similar arguments to the one in this paper should apply, given that the right analogue of Proposition~\ref{binrep} can be found.   While this seems relatively easy to do in the case of $p=3$, where there will need to be two possible starting states ($t \equiv \pm1 \mod 3$), stating a similar result in a usable way for odd primes greater than $3$ might be quite difficult as there will necessarily be $p-1$ starting states to use.   For example, looking at the case of $2^{5^n}$ modulo $5^{n+1}$ yields the result for $n<11$ that
$$
2^{5^n} \equiv \sum_{t=0}^n  a_t 5^t  \pmod {5^{n+1}},
$$
where
$$
a_0=2, a_1=1, a_2=2, a_3=1, a_4=3, a_5=4, a_6=2, a_7=3, a_8=0, a_9=3, a_{10}=2.
$$
Our choice of working modulo $5^{n+1}$ was purely arbitrary here.  In the $p=2$ case, we needed $2^{n+3}$, and if we must move to a higher power of $5$ in the modulus in the proofs, this would add even more complexity, as  $2^{5^n}\equiv 7^{5^n} \pmod{5^{n+1}}$, but not modulo $5^{n+2}$.

Another potential challenge in the odd prime case is that instead of looking at the difference ${\rm St}_k(n+2^m)-{\rm St}_k(n)$, we will need to show that each element of  $\{{\rm St}_k(n+ a\cdot p^m)\mid a\in\{0,1,\dots, p-1\}\}$ lies in its own equivalence class modulo the appropriate power of $p$.  Thus instead of looking at terms of the form $t^n(t^{2^m}-1)$, we will be looking at terms of the form $t^n(t^{p^m}-a)$, where $a=1, 2,\dots,p-1$, and we will need to show they are all non-zero.   While both of these hurdles seem possible to overcome, both may require modifying our techniques significantly.

Generalizing these results to other sequences modulo $2$ may prove more tractable.  The difficulty here seems to be identifying interesting such sequences.  For example, the sequences $b\cdot a^n+1$ for appropriate choices of integers $a$ and $b$ seem to have similar properties to the $S(n,k)$, but for many choices of $a$ and $b$ the result appears to be uninteresting as the $2$-adic valuation is bounded.  A few examples suggest that choosing $a$ and $b$ so that $b\cdot a^n+1$ is congruent to $0$ modulo $8$ may generally lead to interesting examples, but even here, we do not seem to get the full range of behaviors that make the Stirling numbers interesting.






Other interesting problems arise from the terms of $\ell$, $M_k$ and $\mu_k$.  In particular, from our early data, it appears that $\mu_k$ is a non-decreasing sequence.  Is this true in general?  A more ambitious problem appears to be determining the behavior of $M_k$.  Regarding $\ell$, we notice that the largest choices of $\ell$ needed for Lemma \ref{S2nu} occurs when $k=2^t-1$.  Is there a reason for this?  Is this true in general?  More precisely, determining bounds for $\ell$ depending on $k$ would be extremely interesting.




\begin{thebibliography}{9}


\bibitem{Am}  T. Amdeberhan, D.  Manna, and V.  Moll,
The 2-adic valuation of Stirling numbers,
{\em Exp. Math.} {\bf  17} (2008),  69--82.

\bibitem{BeMe} A.  Berrizbeitia, L. A. Medina, A. C. Moll, V. Moll, and L. Noble, The $p$-adic valuation of Stirling numbers,
{\em Journal for Algebra and Number Theory Academia}  {\bf 1} (2010), 1--30.

\bibitem{Wa}
S. De Wannemacker,  On 2-adic orders of Stirling numbers of the second
kind, {\em Integers} {\bf 5} (2005).

\bibitem{Du}
D.  Dummit and  R. Foote, {\em Abstract Algebra}, Prentice-Hall, 1991.

\bibitem{Gr}  R.  Graham,  D.  Knuth,  and O.  Patashnik, {\em Concrete Mathematics,}
Addison-Wesley, 1989.

\bibitem{Kw}Y. H. H.  Kwong, Minimum periods of $S(n,k)$ modulo $M$, {\em Fibonacci Quart.} {\bf 27} (1989), 217--221.

\bibitem{Le1.5} T.  Lengyel, On the divisibility by 2 of the Stirling numbers of the second kind, {\em Fibonacci Quart.}, {\bf 32} (1994) 194--201.


\bibitem{Le2} T.  Lengyel,  On the 2-adic order of Stirling numbers of the second kind and their differences, in {\em
21st International Conference on Formal Power Series and Algebraic
Combinatorics --- FPSAC 2009},
Discrete Math. Theor. Comput. Sci. Proc.,  2009, pp.\ 561--572.


\bibitem{Wo} Wolfram Research, Inc.,  {\sl Mathematica\/}, Version
8.0, Champaign, IL, 2010.



\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B73; Secondary 05A15.

\noindent \emph{Keywords: }
Stirling number, valuation, combinatorial enumeration problem.

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 27 2012;
revised version received February 17 2013.
Published in {\it Journal of Integer Sequences}, March 2 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}