\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{epsfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.0in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.5in}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/$\sim$njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\begin{center}
\vskip 1cm{\LARGE\bf The $p$-adic Valuations of Sequences \\
\vskip .1in Counting Alternating Sign Matrices}
\vskip 1cm
\large
Xinyu Sun and Victor H. Moll\\
Department of Mathematics \\
Tulane University \\
New Orleans, LA 70118\\
USA \\
\href{mailto:xsun1@math.tulane.edu}{\tt xsun1@math.tulane.edu} \\
\href{mailto:vhm@math.tulane.edu}{\tt vhm@math.tulane.edu}\\
\end{center}
\vskip .2 in
\begin{abstract}
The $p$-adic valuations of a sequence of integers counting alternating
sign symmetric matrices are examined for $p=2$ and $3$. Symmetry properties of
their graphs produce a new proof of the result that characterizes the indices
that yield an odd number of matrices.
\end{abstract}
\newcommand{\nn}{\nonumber}
\newcommand{\ba}{\begin{eqnarray}}
\newcommand{\ea}{\end{eqnarray}}
\newcommand{\ift}{\int_{0}^{\infty}}
\newcommand{\ifft}{\int_{- \infty}^{\infty}}
\newcommand{\no}{\noindent}
\newcommand{\realpart}{\mathop{\rm Re}\nolimits}
\newcommand{\imagpart}{\mathop{\rm Im}\nolimits}
\newcommand{\mup}[2]{\mu_{#1}({#2})}
\newcommand{\muc}[1]{\mup{3}{#1}}
\newcommand{\nuthree}[1]{\nu_{3}(T(#1))}
\newcommand{\Sc}[1]{S_{3}(#1)}
\newtheorem{Definition}{\bf Definition}[section]
\newtheorem{Thm}[Definition]{\bf Theorem}
\newtheorem{Example}[Definition]{\bf Example}
\newtheorem{Lem}[Definition]{\bf Lemma}
\newtheorem{Note}[Definition]{\bf Note}
\newtheorem{Cor}[Definition]{\bf Corollary}
\newtheorem{Conj}[Definition]{\bf Conjecture}
\newtheorem{Prop}[Definition]{\bf Proposition}
\newtheorem{Problem}[Definition]{\bf Problem}
\numberwithin{equation}{section}
\section{Introduction} \label{sec-intro}
\setcounter{equation}{0}
The magnificent book {\em Proofs and Confirmations} by David Bressoud
\cite{bressoud1} tells the story of the {\em Alternating Sign Matrix
Conjecture }(ASM)
and its proof. This remarkable result involves the counting function
\begin{equation}
T(n) = \prod_{j=0}^{n-1} \frac{(3j+1)!}{(n+j)!}.
\label{T-seq}
\end{equation}
\noindent
The survey by Bressoud and Propp \cite{bressoud99} describes the
mathematics underlying this problem.
The fact that these numbers are integers is a direct consequence of their
appearance as counting sequences. Mills, Robbins and Rumsey \cite{mrr-1}
conjectured that the number of $n \times n$ matrices whose entries are
$-1, \, 0,$ or $1$, whose row and column sums are all $1$, and such that
in every row, and in every column the non-zero entries alternate in sign is
given by $T(n)$. The first proof of this ASM
conjecture was provided by D. Zeilberger \cite{zeilberger96}. This
proof had the
added feature of being {\em pre-refereed}. Its $76$ pages were subdivided by
the author who provided a tree structure for the proof. An army of
volunteers provided checks for each node in the tree. The request for
checkers can be read in
\begin{center}
{\tt http://www.math.rutgers.edu/$\sim$zeilberg/asm/CHECKING}
\end{center}
The question of integrality of quotients
of factorials, such as $T(n)$, has been considered by
D. Cartwright and J. Kupka
\cite{cart-kupka}. \\
\begin{Thm}
\label{cart-kup}
Assume that for every integer $k \geq 2$ we have
\begin{equation}
\sum_{i=1}^{m} \left\lfloor{{a_{i}}\over{k}}\right\rfloor \leq
\sum_{j=1}^{n} \left\lfloor{{b_{j}}\over{k}}\right\rfloor.
\end{equation}
\noindent
Then the ratio of
$\begin{displaystyle}\prod_{j=1}^{n} b_{j}! \end{displaystyle}$ to
$\begin{displaystyle}\prod_{i=1}^{m} a_{j}! \end{displaystyle}$ is
an integer.
\end{Thm}
The authors \cite{cart-kupka} use this result to prove
that $T(n)$ is an integer. \\
Given an interesting sequence of integers, it is a natural question to
explore the structure of their factorization into primes. This is measured
by the $p$-adic valuation of the elements of the sequence.
\begin{Definition}
\label{def-valp}
Given a prime $p$ and a positive
integer $x \neq 0$, write $x = p^{m}y$, with $y$ not
divisible by $p$. The exponent $m$ is the $p$-adic valuation of $x$,
denoted by $m = \nu_{p}(x)$. This definition is extended to $x = a/b \in
\mathbb{Q}$ via $\nu_{p}(x) = \nu_{p}(a) - \nu_{p}(b)$. We leave the value
$\nu_{p}(0)$ as undefined.
\end{Definition}
The $p$-adic valuations of many sequences have surprising properties. The
reader will find in Amdeberhan, Manna, and Moll \cite{amm1} an analysis of the $2$-adic valuation of the
sequence
\begin{equation}
A_{l,m} = \frac{l! m!}{2^{m-l}} \sum_{k=l}^{m} 2^{k} \binom{2m-2k}{m-k} \binom{m+k}{m} \binom{k}{l}
\end{equation}
\noindent
for fixed $l \in \mathbb{N}$ and $m \geq l$. This example
appeared in the evaluation of a definite integral and
some of its properties
are given by Manna and Moll \cite{manna-moll-survey}.
The $2$-adic properties of
the Stirling numbers of the
second kind are described by Amdeberhan, Manna, and Moll \cite{amm2}.
In this paper we provide a complete description of the $p$-adic valuation of
the sequence $T(n)$ in (\ref{T-seq}) for the primes $p=2$ and $3$. Figure
\ref{figure-1} depicts the sequence $\nu_{2} \circ T(n)$
for $1 \leq n \leq 10^{5}$ and Figure \ref{figure-2} gives $\nu_{3} \circ T(n)$
for $1 \leq n \leq 3^{12} = 531441$.
{{
\begin{figure}[ht]
\begin{minipage}[t]{20em}
\centering
\epsfig{file=figure1.eps,width=17em,angle=0}
\caption{The $2$-adic valuation of $T(n)$}
\label{figure-1}
\end{minipage}%
\begin{minipage}[t]{20em}
\centering
\epsfig{file=figure2.eps,width=17em,angle=0}
\caption{The $3$-adic valuation of $T(n)$}
\label{figure-2}
\end{minipage}
\end{figure}
}}
The case $p \geq 5$ presents similar features and the techniques
presented here could be used to describe the function $\nu_{p} \circ T$
completely. This will be reported elsewhere.
As a corollary of the analysis presenetd here, we produce a new
proof of a result of D. Frey and
J. Sellers \cite{frey-sellers1}: the
number $T(n)$ is odd if and only if $n$ is a
{\em Jacobsthal number} $J_{m}$. These numbers, defined by the recurrence
$J_{n} = J_{n-1} + 2 J_{n-2}$ with initial conditions $J_{0} = 1$ and
$J_{1} = 1$, are reviewed in Section \ref{sec-odd}.
\smallskip
The main result of this paper is:
\begin{Thm}
\label{main-thm}
Let $J_{n}$ the Jacobsthal number and define
$I_{n} := [J_{n}, J_{n+1}]$. The function
$\nu_{2} \circ T$ restricted to $I_{n}$
is determined by its restriction to $I_{n-1} \cup I_{n-2}$.
\end{Thm}
\medskip
The details are provided in the algorithm presented next.
\medskip
\noindent
{\bf Algorithm for the function} $\nu_{2} \circ T$: \\
\noindent
{\bf Step 1}. Verify the special values $\nu_{2}(T(2^{n})) = J_{n-1}$ and
$\nu_{2}(T(J_{n})) = 0$. The midpoint of the interval $I_{n} = [ \, J_{n},
\, J_{n+1} \, ]$ is $2^{n}$.
\smallskip
\noindent
{\bf Step 2}. Given $N \in \mathbb{N}$, compute the unique index $n$ such that
$J_{n} \leq N < J_{n+1}$.
\smallskip
\noindent
{\bf Step 3}. For $1 \leq i \leq J_{n-1}$,
\begin{equation}
\nu_{2}(T(2^{n}+i)) = \nu_{2}(T(2^{n}-i)).
\end{equation}
\noindent
Thus, if $2^{n} < N < J_{n+1}$, replace $N$ by $N^{*}:= 2^{n+1}-N$ that
satisfies $J_{n} < N^{*} < 2^{n}$ and $\nu_{2}(T(N)) = \nu_{2}(T(N^{*}))$.
Therefore, the value of $\nu_{2} \circ T$ on the interval $[J_{n}, J_{n+1}]$
is determined by the values on its first half $[J_{n}, 2^{n}]$.
\smallskip
\noindent
{\bf Step 4}. For $0 < i < 2J_{n-3}$,
\begin{equation}
\nu_{2}(T(J_{n}+i)) = i + \nu_{2}(T(J_{n-2}+i)).
\end{equation}
\noindent
This yields the value of $\nu_{2} \circ T$ on the first part of the
interval $[ \, J_{n}, 2^{n} \, ]$, namely $[ \, J_{n}, \, J_{n} +
2J_{n-3} \, ]$, in terms of those from $I_{n-2} = [\, J_{n-2}, \,
J_{n-1} \, ]$.
\smallskip
\noindent
{\bf Step 5}. For $0 \leq i \leq J_{n-2}$,
\begin{equation}
\nu_{2}(T(2^{n}-J_{n-2}+i)) = \nu_{2}(T(J_{n-1}+i)) + 2J_{n-3}.
\end{equation}
\noindent
This determines the values of $\nu_{2} \circ T$ on the second part of the
interval $[ \, J_{n}, 2^{n} \, ]$, namely
$[ \, J_{n}+ 2J_{n-3}, \, 2^{n} \, ]$, in terms of $\nu_{2} \circ T$
restricted to the previous interval $I_{n-1} = [\, J_{n-1}, \,
J_{n-2} \, ]$.
\medskip
The proof of this result is given in Section \ref{sec-desc}. \\
\begin{Thm}
\label{thm-fixed}
For $n \in \mathbb{N}$, let $f_{n}$ be the restriction of
$\nu_{2} \circ T$ to the
interval $I_{n}$ scaled to the unit square $[0,1] \times [0,1]$. Then $f_{n}$
converges to the unique
function $f: [0,1] \to [0,1]$ that satisfies
\begin{equation}
f(x) = \begin{cases}
2x + \frac{1}{4} f(4x), & \text{ if } 0 \leq x < \frac{1}{4}; \nonumber \\
\frac{1}{2} + \frac{1}{2} f( 2x - \tfrac{1}{2}), & \text{ if }
\frac{1}{4} \leq x \leq \frac{3}{4}; \nonumber \\
2(1-x) + \frac{1}{4} f(4x-3), & \text{ if } \frac{3}{4} < x \leq 1.
\end{cases}
\label{fixedpoint0}
\end{equation}
\end{Thm}
\medskip
Similar results are valid for primes $p \geq 3$. Some details are given in
Section \ref{sec-three}.
The generalization of $T(n)$ defined by
\begin{equation}
T_{p}(n) := \prod_{j=0}^{n-1} \frac{(pj+1)!}{(n+j)!}
\end{equation}
\noindent
is also considered. The numbers $T_{p}(n)$ are integers and a recurrence for
its $p$-adic valuation is presented. A combinatorial
interpretation of them is left as an open question.
\section{A recurrence} \label{sec-rec}
\setcounter{equation}{0}
The integers $T(n)$ defined in (\ref{T-seq}) grow rapidly
and a direct calculation using (\ref{T-seq})
is impractical. The number of digits of $T(10^{k})$ is
$12, \, 1136, \, 113622$ and $11362189$ for
$1 \leq k \leq 4$. Naturally, the prime factorization of $T(n)$ can
be computed in reasonable time since
every prime $p$ dividing $T(n)$ satisfies $p \leq 3n-2$. \\
In this section we discuss a recurrence for the $p$-adic valuation of
$T(n)$, that permits its fast computation. Introduce the notation
\begin{equation}
f_{p}(j) := \nu_{p}(j!).
\end{equation}
\begin{Thm}
\label{thm-recurr1}
Let $p$ be a prime. Then the $p$-adic valuation of $T(n)$ satisfies
\begin{equation}
\nu_{p}(T(n+1)) = \nu_{p}(T(n)) + f_{p}(3n+1) + f_{p}(n) -f_{p}(2n)
-f_{p}(2n+1).
\label{rec-1}
\end{equation}
\end{Thm}
\begin{proof}
This follows directly by combining the initial value $T(1)=1$ with the
expression
\begin{equation}
\nu_{p}(T(n)) = \sum_{j=0}^{n-1} f_{p}(3j+1) - \sum_{j=0}^{n-1} f_{p}(n+j)
\end{equation}
\noindent
and the corresponding one for $\nu_{p}(T(n+1))$.
\end{proof}
Legendre \cite{legendre1} established the formula
\begin{equation}
f_{p}(j) = \nu_{p}(j!) = \frac{j - S_{p}(j)}{p-1},
\end{equation}
\noindent
where $S_{p}(j)$ denotes the sum of the base-$p$ digits of $j$. The result of
Theorem \ref{thm-recurr1} is now expressed in terms of the function $S_{p}$.
\begin{Cor}
\label{p-val}
The $p$-adic valuation of $T(n)$ is given by
\begin{equation}
\nu_{p}(T(n)) = \frac{1}{p-1} \left( \sum_{j=0}^{n-1} S_{p}(n+j) -
\sum_{j=0}^{n-1} S_{p}(3j+1) \right).
\end{equation}
\end{Cor}
Summing the recurrence (\ref{rec-1}) and using $T(1) = 1$ we obtain
an alternative expression for the $p$-adic valuation of $T(n)$.
\begin{Prop}
\label{prop-valuetn}
The $p$-adic valuation of $T(n)$ is given by
\begin{equation}
\nu_{p}(T(n)) = \frac{1}{p-1} \sum_{j=1}^{n-1}
\left( S_{p}(2j) + S_{p}(2j+1) - S_{p}(3j+1) - S_{p}(j) \right).
\label{valp-form1}
\end{equation}
\noindent
In particular, for $p=2$ we have
\begin{equation}
\nu_{2}(T(n)) = \sum_{j=0}^{n-1}
\left( S_{2}(2j+1) - S_{2}(3j+1) \right) \label{val-2}
\end{equation}
\end{Prop}
\begin{Cor}
For each $n \in \mathbb{N}$ we have
\begin{equation}
\sum_{j=1}^{n-1} S_{2}(2j+1) \geq \sum_{j=1}^{n-1} S_{2}(3j+1).
\end{equation}
\end{Cor}
\noindent
{\bf Note}. The formula (\ref{valp-form1}) can be used to compute $T(n)$ for
large values of $n$. Recall that only primes $p \leq 3n-2$
appear in the factorization of $T(n)$. For example, the number $T(100)$ has
$1136$ digits and its prime factorization is given by
\begin{multline}
T(100) = 2^{23} \cdot 3^{19} \cdot 13^{13} \cdot 17^{4} \cdot 29^{3} \cdot 41^{4} \cdot 61^{2} \cdot 67^{11} \cdot 71^{5}\cdot
73^{3} \cdot 151 \cdot 157^{5} \cdot 163^{9} \cdot 167^{11} \\
\times 173^{15}
\cdot 179^{19} \cdot 181^{21} \cdot 191^{27} \cdot 193^{29} \cdot 197^{31}
\cdot 199^{33} \cdot 211^{30} \cdot 223^{26} \cdot 227^{24} \cdot 229^{24}
\cdot 233^{22} \\
\times 239^{20} \cdot 241^{40} \cdot 251^{16} \cdot 257^{14}
\cdot 263^{12} \cdot 269^{10} \cdot 271^{10} \cdot 277^{8} \cdot 281^{6}
\cdot 283^{6} \cdot 293^{2}. \nonumber
\end{multline}
\section{The Jacobsthal numbers} \label{sec-odd}
\setcounter{equation}{0}
The {\em Jacobsthal sequence} (A001045) is defined by the recurrence
\begin{equation}
J_{n} = J_{n-1} + 2J_{n-2}, \text{ with } J_{0} = 1, J_{1} = 1.
\end{equation}
\noindent
The first few values are $1, \, 1, \, 3, \, 5, \, 11, \, 21, \, 43, \, 85$.
These numbers have many interpretations.
Here is a small sample: \\
\noindent
a) $J_{n}$ is the numerator of the reduced fraction in the alternating
sum $$\sum_{j=1}^{n+1} \frac{(-1)^{j+1}}{2^{j}}. $$
\noindent
b) Number of permutations with no fixed points avoiding $231$ and $132$. \\
\noindent
c) The number of odd coefficients in the expansion of
$(1+x+x^{2})^{2^{n-1}-1}$. \\
Many other examples can be found at
\begin{center}
\tt{http://www.research.att.com/$\sim$njas/sequences/A001045}
\end{center}
\medskip
The discussion of the function $\nu_{2} \circ T$ employs several elementary
properties of the Jacobsthal number $J_{n}$, summarized here for the
convenience of the reader.
\begin{Lem}
\label{jacob-prop}
For $n \geq 2$, the Jacobsthal numbers $J_{n}$ satisfy \\
\noindent
a) $ J_{n}= J_{n-1} + 2 J_{n-2}$ with $J_{0}=1$ and $J_{1}=1$. (This is
the definition of $J_{n}$). \\
\noindent
b) $J_{n} = \frac{1}{3} ( 2^{n+1} + (-1)^{n} )$. Therefore $J_{n}$ is the
nearest integer to $\frac{2^{n+1}}{3}$. \\
\noindent
c) $2^{n-1} + 1 \leq J_{n} < 2^{n}$. \\
\noindent
d) $J_{n}+J_{n-1} = 2^{n}$. \\
\noindent
e) $J_{n}-J_{n-2} = 2^{n-1}$.
\end{Lem}
\section{The $2$-adic valuation of $T(n)$} \label{sec-desc}
\setcounter{equation}{0}
The goal of this section is to prove Theorem \ref{main-thm}. The
algorithm presented in Section \ref{sec-intro} is justified. The
analysis begins with an auxiliary lemma.
\begin{Lem}
\label{lemma-aux1}
Let $n \in \mathbb{N}$. Introduce the notation
$S_{n,j}^{+} := S_{2}( 3 \cdot 2^{n} + 3j-2)$ and
$S_{n,j}^{-} := S_{2}( 3 \cdot 2^{n} - 3j+1 )$.
Then
\begin{equation}
S_{n,j}^{+} = \begin{cases}
S_{2}(3j-2) + 2, & \text{ if } \quad
1 \leq j \leq J_{n-1}; \\
S_{2}(3j-2), & \text{ if } \quad
1 + J_{n-1} \leq j \leq J_{n}; \\
S_{2}(3j-2) + 1, & \text{ if } \quad
1 + J_{n} \leq j \leq 2^{n};
\end{cases}
\end{equation}
\noindent
and
\begin{equation}
S_{n,j}^{-} = \begin{cases}
n+1-S_{2}(3j-2), & \text{ if } \quad
1 \leq j \leq J_{n-1}; \\
n+2-S_{2}(3j-2), & \text{ if } \quad
1 + J_{n-1} \leq j \leq J_{n}; \\
n+1-S_{2}(3j-2), & \text{ if } \quad
1 + J_{n} \leq j \leq 2^{n}.
\end{cases}
\end{equation}
\end{Lem}
\begin{proof}
Let $3j-2 = a_{0} + 2a_{1} + \cdots + a_{r}2^{r}$ be the binary expansion of
$3j-2$. The corresponding one for $3 \cdot 2^{n-1}$ is simply
$2^{n-1} + 2^{n}$. For $3j-2 < 2^{n-1}$ these two expansions have no terms in
common, therefore $S_{n,j}^{+} = S_{2}(3j-2) + 2$. On the other hand, if
$2^{n-1} \leq 3j-2 < 2^{n}$ then the index in the binary expansion of $3j-2$
is $r = n-1$ with $a_{n-1} = 1$. The expansion of $3j-2 + 3 \cdot 2^{n-1}$ is
now
\begin{equation}
a_{0} + 2a_{1} + \cdots + a_{n-2}2^{n-2} + 2^{n-1} + 2^{n-1} + 2^{n} =
a_{0} + 2a_{1} + \cdots + a_{n-2}2^{n-2} + 2^{n+1},
\nonumber
\end{equation}
\noindent
and this yields $S_{n,j}^{+} = a_{0} + a_{1} + \cdots + a_{n-2} + 1 =
S_{2}(3j-2)$. The remaining cases are treated in a similar form.
\end{proof}
We now establish the $2$-adic valuation at the center of the
interval $[J_{n-1}, J_{n}]$. This establishes one of the special values in
Step 1 of the algorithm.
\begin{Thm}
\label{thm-power}
Let $n \in \mathbb{N}$. Then
\begin{equation}
\nu_{2} \left( T \left( 2^{n} \right) \right) = J_{n-1}.
\end{equation}
\end{Thm}
\begin{proof}
We proceed by induction and split
\begin{equation}
\nu_{2} \left( T(2^{n}) \right) =
\sum_{j=1}^{2^{n}-1} \left[ S_{2}(2j+1) - S_{2}(3j+1) \right]
\end{equation}
\noindent
at $j=2^{n-1}-1$. The first part is identified as
$\nu_{2} \left( T( 2^{n-1} ) \right)$ to produce
\begin{equation}
\nu_{2} \left( T(2^{n}) \right) =
\nu_{2} \left( T(2^{n-1}) \right) +
\sum_{j=0}^{2^{n-1}-1} S_{2}(2j+1+ 2^{n})
- \sum_{j=1}^{2^{n-1}} S_{2}(3j-2 + 3
\cdot 2^{n-1}).
\nonumber
\end{equation}
\noindent
From $2j+1 \leq 2^{n}-1 < 2^{n}$
it follows $S_{2}(2j+1+2^{n}) = S_{2}(2j+1) + 1$.
Assume first that $n$ is even. Lemma \ref{lemma-aux1} gives
\begin{multline}
\sum_{j=1}^{2^{n-1}} S_{2}( 3j-2 + 3 \cdot 2^{n-1} )
=
\sum_{j=1}^{(2^{n-1}+1)/3} [S_{2}(3j-2) + 2 ] + \\
\sum_{j=(2^{n-1}+1)/3}^{(2^{n}-1)/3} S_{2}(3j-2) +
\sum_{j=(2^{n}+2)/3}^{2^{n-1}} [S_{2}(3j-2) + 1 ] \nonumber
\end{multline}
\noindent
and using (\ref{val-2}) yields
\begin{equation}
\nu_{2}(T(2^{n})) = 2 \nu_{2}(T(2^{n-1})) - 1 = 2J_{n-2}-1.
\end{equation}
\noindent
Elementary
properties of Jacobsthal numbers give $2J_{n-2} - 1 = J_{n-1}$, proving
the result. The argument for $n$ odd is similar.
\end{proof}
\medskip
The next theorem gives the second special value in Step 1. \\
\begin{Thm}
\label{thm-odd}
Let $n \in \mathbb{N}$. Then $\nu_{2}(T(J_{n})) = 0$.
\end{Thm}
\begin{proof}
Proposition \ref{prop-valuetn} gives
\begin{equation}
\nu_{2} \left( T(J_{n}) \right) =
\sum_{j=1}^{J_{n}-1} \left[ S_{2}(2j+1) - S_{2}(3j+1) \right].
\end{equation}
\noindent
Split the sum at $2^{n-1} \leq J_{n} -1$ to obtain
\begin{eqnarray}
\nu_{2} \left( T(J_{n}) \right) & = &
\sum_{j=1}^{2^{n-1}-1} \left[ S_{2}(2j+1) - S_{2}(3j+1) \right] \nonumber \\
& & +
\sum_{j=2^{n-1}}^{J_{n}-1}
\left[ S_{2}(2j+1) - S_{2}(3j+1) \right] \nonumber \\
& = & \nu_{2} \left( T ( 2^{n-1} ) \right) +
\sum_{j=2^{n-1}}^{J_{n}-1}
\left[ S_{2}(2j+1) - S_{2}(3j+1) \right]. \nonumber
\end{eqnarray}
Therefore
\begin{equation}
\nu_{2} \left( T(J_{n}) \right) = \nu_{2}(T(2^{n-1})) +
\sum_{j=0}^{J_{n} - 1 - 2^{n-1}}
\left[ S_{2} ( 2j+1 + 2^{n}) - S_{2}(3j+1 + 3 \cdot 2^{n-1}) \right].
\nonumber
\end{equation}
The Jacobsthal numbers satisfy
$J_{n}-1 - 2^{n-1} = J_{n-2} - 1$, so that
\begin{equation}
\nu_{2} \left( T(J_{n}) \right) = \nu_{2}(T(2^{n-1})) +
\sum_{j=0}^{J_{n-2} - 1}
\left[ S_{2} ( 2j+1 + 2^{n}) - S_{2}(3j+1 + 3 \cdot 2^{n-1}) \right].
\nonumber
\end{equation}
\noindent
The relation
\begin{equation}
2j+1 \leq 2(J_{n-2}-1)+1 = 2J_{n-2}-1 = J_{n}-J_{n-1}-1 < 2^{n},
\nonumber
\end{equation}
\noindent
implies
\begin{equation}
S_{2}(2j+1+2^{n}) = S_{2}(2j+1) + 1.
\nonumber
\end{equation}
\noindent
Similarly
$3j+1 \leq 3J_{n-2}-2 < 3 (2^{n-1}+(-1)^n) -2 \leq 2^{n-1} -1$ and
$3 \cdot 2^{n-1} = 2^{n} + 2^{n-1}$ give
\begin{equation}
S_{2}(3j+1 + 3 \cdot 2^{n-1} ) = S_{2}(3j+1) + 2,
\nonumber
\end{equation}
\noindent
for $0 \leq j \leq J_{n-2}-1$. Therefore
\begin{equation}
\nu_{2} \left( T(J_{n}) \right) = \nu_{2} \left( T(2^{n-1}) \right) +
\sum_{j=0}^{J_{n-2}-1} \left[ S_{2}(2j+1) - S_{2}(3j+1) \right] - J_{n-2}.
\nonumber
\end{equation}
\noindent
Theorem \ref{thm-power} shows that the first and third term on the line
above cancel, leading to
\begin{equation}
\nu_{2} \left( T(J_{n}) \right) =
\nu_{2} \left( T(J_{n-2}) \right).
\nonumber
\end{equation}
\noindent
The result now follows by induction on $n$.
\end{proof}
\medskip
We continue with the analysis of the function $\nu_{2} \circ T$. The next Lemma
corresponds to Step 3 in the outline that deals with
$\nu_{2}(T(j))$ for $J_{n} \leq j \leq J_{n} + 2J_{n-3} = 2^{n} - J_{n-2}$.
\begin{Lem}
\label{lemma-shift}
For $0 < i \leq 2J_{n-3}$ we have
\begin{equation}
\nu_{2}(T(J_{n}+i)) = i + \nu_{2}(T(J_{n-2}+i)).
\end{equation}
\end{Lem}
\begin{proof}
Assume $n$ is even. Then
\begin{eqnarray}
\nu_{2}(T(J_{n}+i)) & = &
\sum_{j=1}^{J_{n}+i-1}
\left[ S_{2}(2j+1) - S_{2}(3j+1) \right] \nonumber \\
& = &
\sum_{j=1}^{J_{n}-1}
\left[ S_{2}(2j+1) - S_{2}(3j+1) \right] +
\sum_{j=J_{n}}^{J_{n}+i-1}
\left[ S_{2}(2j+1) - S_{2}(3j+1) \right]. \nonumber
\end{eqnarray}
\noindent
The first sum is $\nu_{2}(T(J_{n})) = 0$, according to Theorem \ref{thm-odd}.
Lemma \ref{jacob-prop} now gives
\begin{eqnarray}
\nu_{2}(T(J_{n}+i)) & = &
\sum_{j=J_{n}}^{J_{n}+i-1}
\left[ S_{2}(2j+1) - S_{2}(3j+1) \right] \nonumber \\
& = & \sum_{j=J_{n}+1}^{J_{n}+i}
\left[ S_{2}(2j-1) - S_{2}(3j-2) \right] \nonumber \\
& = & \sum_{j=J_{n}+1-2^{n-1}}^{J_{n}+i-2^{n-1}}
\left[ S_{2}(2^{n}+2j-1) - S_{2}(3 \cdot 2^{n-1} + 3j-2) \right] \nonumber
\\
& = & \sum_{j=J_{n-2}+1}^{J_{n-2}+i}
\left[ S_{2}(2^{n}+2j-1) - S_{2}(3 \cdot 2^{n-1} + 3j-2) \right]. \nonumber
\end{eqnarray}
\noindent
The index $j$ satisfies
\begin{equation}
2j-1 \leq 2(J_{n-2}+i)-1 < 2(J_{n-2}+2J_{n-3}) = 2J_{n-1} < 2^{n},
\nonumber
\end{equation}
\noindent
therefore $S_{2}(2^{n}+2j-1) = 1 + S_{2}(2j-1)$.
The lower limit in the last sum is
$J_{n-2} + 1 = \frac{1}{3}(2^{n-1}+1) +1$, and the upper bound is
\begin{equation}
J_{n-2}+i \leq J_{n-2} + 2J_{n-3} = J_{n-1} =
\frac{1}{3}(2^{n}-1).
\end{equation}
\noindent
For these values of $j$, Lemma \ref{lemma-aux1} gives
$S_{2}(3 \cdot 2^{n-1} + 3j-2) =
S_{2}(3j-2)$. Therefore
\begin{eqnarray}
\nu_{2}(T(J_{n}+i))
& = & \sum_{j=J_{n-2}+1}^{J_{n-2}+i}
\left[ S_{2}(2j-1) + 1- S_{2}(3j-2) \right] \nonumber \\
& = & i + \sum_{j=J_{n-2}+1}^{J_{n-2}+i}
\left[ S_{2}(2j-1) - S_{2}(3j-2) \right] \nonumber \\
& = & i + \nu_{2}(T(J_{n-2}+i)). \nonumber
\end{eqnarray}
The result has been established for $n$ even. The proof for $n$ odd is
similar.
\end{proof}
\begin{Cor}
The $2$-adic valuation of $T(n)$ satisfies
$\nu_{2}(T(j)) > 0$ for $J_{n} < j < 2^{n} - J_{n-2}$.
\end{Cor}
\medskip
The next result shows the graph of $\nu_{2} \circ T$ on the
interval $[2^{n}-J_{n-2},2^{n}+J_{n-2}]$ is a vertical shift of the
graph on $[J_{n-1},J_{n}]$. This corresponds to Step 4 in the outline. \\
\begin{Prop}
\label{prop-shift}
For $0 \leq i \leq 2J_{n-2}$,
\begin{equation}
\nu_{2}(T(2^{n}-J_{n-2}+i)) =
\nu_{2}(T(J_{n-1}+i)) + 2J_{n-3}.
\end{equation}
\end{Prop}
\begin{proof}
The functions $\nu_{2}(T(J_{n-1} + i))$ and
$\nu_{2}(T(2^{n}-J_{n-2} + i))$ have the same discrete derivative. This amounts
to
\begin{multline}
\nu_{2}(T(J_{n-1}+i)) -
\nu_{2}(T(J_{n-1}+i-1)) = \\
\nu_{2}(T(2^{n}-J_{n-2}+i)) -
\nu_{2}(T(2^{n}-J_{n-2}+i-1))
\end{multline}
\noindent
for $1 \leq i \leq 2J_{n-2}$. Observe that
\begin{equation}
\nu_{2}(T(k)) - \nu_{2}(T(k-1)) = S_{2}(2k-1) - S_{2}(3k-2),
\end{equation}
\noindent
and using $2^{n}-J_{n-2} = 2^{n-1}+J_{n-1}$, conclude that the
result is equivalent to the identity
\begin{multline}
S_{2}(2^{n} + 2(J_{n-1}+i)-1) -
S_{2}(2(J_{n-1}+i)-1) = \\
S_{2}(3 \cdot 2^{n-1} + 3(J_{n-1}+i)-2)
- S_{2}(3(J_{n-1}+i)-2), \label{iden-1}
\end{multline}
\noindent
for $1 \leq i \leq 2J_{n-2}$. Define
\begin{equation}
h_{n}(i) = \begin{cases}
1, \quad & \text{ if } 1 \leq i \leq J_{n-2}; \\
0, \quad & \text{ if } J_{n-2} + 1 \leq i \leq 2J_{n-2}.
\end{cases}
\end{equation}
\noindent
The assertion is that both sides in (\ref{iden-1}) agree with $h_{n}(i)$.
The analysis of the left hand side is easy: the condition
$1 \leq i \leq J_{n-2}$ implies $2(J_{n-1}+i)-1 \leq 2^{n}-1$. Thus,
the term $2^{n}$ does not interact with the binary expansion
$2(J_{n-1}+i)-1$ and produces
the extra $1$. On the other hand, if $J_{n-2}+ 1 \leq i \leq 2 J_{n-2}$, then
\begin{multline}
2^{n}+1 = 2(J_{n-1}+J_{n-2}+1) -1 \leq 2(J_{n-1}+i)-1 \\
\leq 2(J_{n-1}+2J_{n-2})-1 = 2J_{n}-1 < 2^{n+1}-1.
\end{multline}
\noindent
Therefore the binary expansion of $x := 2(J_{n-1}+i)-1$ is of the
form $a_{0}+a_{1}\cdot 2 + \cdots + a_{n-1} \cdot 2^{n-1} + 1 \cdot 2^{n}$.
It follows that $2^{n} + x$ and $x$ have the same number of $1$'s in their
binary expansion. Thus
$S_{2}(x) = S_{2}(x+2^{n})$ as claimed. \\
The analysis of the right hand side of (\ref{iden-1}) is slightly more
difficult. Let $x := 3(J_{n-1}+i)-2$ and it is required to compare
$S_{2}(x)$ and $S_{2}(3 \cdot 2^{n-1} + x)$. Observe that
\begin{equation}
x \leq 3(J_{n-1} + 2J_{n-2} ) -2 = 3J_{n}-2 = 2^{n+1} + (-1)^{n} - 2 < 2^{n+1}
\end{equation}
\noindent
and
\begin{equation}
x \geq 3(J_{n-1}+1) -2 = 2^{n} + (-1)^{n-1} +1 \geq 2^{n}.
\end{equation}
\noindent
This shows that the binary expansion of $x$ is of the form
\begin{equation}
x = a_{0} + a_{1} \cdot 2 + \cdot + a_{n-1} \cdot 2^{n-1} + 1 \cdot 2^{n},
\end{equation}
\noindent
and the corresponding one for $3 \cdot 2^{n-1}$ is $2^{n} + 2^{n-1}$. An
elementary calculation shows that
$S_{2}(x + 3 \cdot 2^{n-1} ) - S_{2}(x)$ is $1$ if $a_{n-1}=0$ and $0$ if
$a_{n-1}=1$. In order to transform this inequality to a restriction on the
index $i$, observe that $a_{n-1}=1$ is equivalent to $x - 2^{n} \geq 2^{n-1}$.
Using the value of $x$ this becomes $3(J_{n-1}+i)-2) \geq 3 \cdot 2^{n-1}$,
that is directly transformed to $i \geq J_{n-2}+1$. This shows that the
right hand side of (\ref{iden-1}) also agrees with $h_{n}$ and (\ref{iden-1})
has been established.
\end{proof}
\medskip
The final step in the proof of Theorem \ref{main-thm}
deals with the symmetry of the graph
of $\nu_{2}(T(j))$ on $I_{n}$ about the point $j = 2^{n}$. The range covered in the
next proposition is $2^{n}-J_{n-1} \leq j \leq 2^{n}+J_{n-1}$. \\
\begin{Prop}
\label{prop-symmetry}
For $1 \leq i \leq J_{n-1}$,
\begin{equation}
\nu_{2}(T(2^{n}-i)) = \nu_{2}(T(2^{n}+i)).
\end{equation}
\end{Prop}
\begin{proof}
Start with
\begin{eqnarray}
\nu_{2}(T(2^{n})) - \nu_{2}(T(2^{n}-i)) & = &
\sum_{j=2^{n}-i+1}^{2^{n}} \left[ S_{2}(2j-1) - S_{2}(3j-2) \right]
\nonumber \\
& = & \sum_{k=1}^{i} \left[ S_{2}(2^{n+1}-(2k-1)) -
S_{2}( 3 \cdot 2^{n} -(3k-1)) \right].
\nonumber
\end{eqnarray}
\noindent
The first term in the sum satisfies
\begin{equation}
S_{2}(2^{n+1} -(2k-1) ) = n+2 - S_{2}(2k-1).
\end{equation}
\noindent
To check this, write $2k-1 = a_{0} + a_{1} \cdot 2 + \cdots + a_{r}
\cdot 2^{r}$ with $a_{0} = 1$ because $2k-1$ is odd. Now,
$2^{n+1} = (1 + 2 + 2^{2} + \cdots + 2^{n} ) + 1$ implies that
\begin{eqnarray}
2^{n+1} - (2k-1) & = & ( 2^{n} + 2^{n-1} + \cdots + 2^{r+1} ) \nonumber \\
& & + (1-a_{r}) \cdot 2^{r} + (1-a_{r+1}) \cdot 2^{r-1} + \cdots +
(1-a_{1}) \cdot 2 + 1 \nonumber
\end{eqnarray}
\noindent
resulting in
\begin{eqnarray}
S_{2}( 2^{n+1} - (2k-1))
& = & n+1 - \left( a_{r}+a_{r-1} + \cdots + a_{1} \right) \nonumber \\
& = & n+2 - S_{2}(2k-1). \nonumber
\end{eqnarray}
Therefore
\begin{multline}
\nu_{2}(T(2^{n})) - \nu_{2}(T(2^{n}-i)) =
(n+2)i - \sum_{k=1}^{i} S_{2}(2k-1) - \\
\sum_{k=1}^{i} S_{2}( 3 \cdot 2^{n} - (3k-1)).
\end{multline}
Similarly
\begin{eqnarray}
\nu_{2}(T(2^{n}+i)) - \nu_{2}(T(2^{n})) & = &
\sum_{j=2^{n}+1}^{2^{n}+i} \left( S_{2}(2j-1) - S_{2}(3j-2) \right)
\nonumber \\
& = & \sum_{k=1}^{i} \left( S_{2}(2^{n+1}+2k-1) - S_{2}(3 \cdot 2^{n} + 3k-2 )
\right). \nonumber
\end{eqnarray}
\noindent
The inequality
\begin{equation}
2k-1 \leq 2i-1 \leq 2J_{n-1}-1 \leq 2 \cdot 2^{n-1} -1
\leq 2^{n}-1 < 2^{n+1}
\end{equation}
\noindent
shows that $S_{2}(2^{n+1} + 2k-1 ) = 1 + S_{2}(2k-1)$. Also,
Lemma \ref{lemma-aux1}
yields the identity
\begin{equation}
S_{2}(3 \cdot 2^{n} + 3k-2 ) + S_{2}(3 \cdot 2^{n} -3k+1) = n+3.
\label{ident-symm}
\end{equation}
\noindent
Therefore
\begin{eqnarray}
\nu_{2}(T(2^{n}+i)) - \nu_{2}(T(2^{n})) & = &
\sum_{k=1}^{i} \left( S_{2}(2^{n+1}+2k-1) - S_{2}(3 \cdot 2^{n} + 3k-2 )
\right) + i \nonumber \\
& & + \sum_{k=1}^{i} S_{2}(2k-1) -
\left( n+3 - S_{2}(3 \cdot 2^{n} -3k+1) \right). \nonumber
\end{eqnarray}
\noindent
Thus
\begin{equation}
\nu_{2}(T(2^{n})) - \nu_{2}( T(2^{n}-i)) =
- \left[ \nu_{2}( T(2^{n}-i)) - \nu_{2}(T(2^{n})) \right],
\nonumber
\end{equation}
\noindent
and symmetry has been established.
\end{proof}
\noindent
{\bf Note}. The identity (\ref{ident-symm}) can be given a direct proof by
induction on $k$. It
is required to check that the left hand side is independent of $k$. This
follows from the identity
\begin{equation}
S_{2}(m+3) - S_{2}(m) =
\begin{cases}
2 - \omega_{2} \left( \frac{m}{2} \right), \quad \text{ if }
m \equiv 0 \bmod 2; \\
- \omega_{2} \left( \lfloor{ {{m} \over {4}} \rfloor}\right),
\quad \text{ if }
m \equiv 1 \bmod 2;
\end{cases}
\end{equation}
\noindent
where $\omega_{2}(m)$ is the number of trailing $1$'s in the binary expansion
of $m$. For $m= 829, \, S_{3}(829) = 7$ and $S_{3}(832) = 3$. The
binary expansion of $m=207 = \lfloor{829/4 \rfloor}$ is $11001111$ and the
number of trailing $1$'s is $4$. This
observation is due to A. Straub.
\medskip
\noindent
{\bf Note}. The proof of Theorem \ref{main-thm} is
now complete. \\
\noindent
{\bf Example}. The use of the algorithm is illustrated with the
computation of $\nu_{2}(T(5192))$. The number $T(5192)$ has $3,062,890$
digits and it is never computed. \\
\noindent
$1.$ Start with $J_{12} = 2731 < 5192 < J_{13} = 5461$. The midpoint
of $[2731,5461]$ is $4096$. \\
\noindent
$2.$ Apply Step 3, to obtain $\nu_{2}(T(5192)) = \nu_{2}(T(3000))$. \\
\noindent
$3.$ The number $3000 \in [J_{12}, J_{12}+2J_{9}]$. Step 4 gives
$\nu_{2}(T(3000)) = 269 + \nu_{2}(T(952))$. \\
\noindent
$4.$ The number $952 \in [ J_{10}+2J_{7}, 2^{10}]$. Step 5 gives
$\nu_{2}(T(952)) = 170 + \nu_{2}(T(440))$. \\
\noindent
$5.$ The number $440 \in [ J_{9} + 2J_{6}, 2^{9}]$. Step 5 gives
$\nu_{2}(T(440)) = 86 + \nu_{2}(T(184))$. \\
\noindent
$6.$ The number $184 \in [ J_{8}, J_{8} + 2J_{5}]$. Step 4 gives
$\nu_{2}(T(184)) = 13 + \nu_{2}(T(56))$. \\
\noindent
$7.$ The number $56 \in [ J_{6}+2J_{3}, 2^{6}]$. Step 5 gives
$\nu_{2}(T(56)) = 10 + \nu_{2}(T(24))$. \\
\noindent
$8.$ The number $24 \in [ J_{5}, J_{5}+2J_{2}]$. Step 4 gives
$\nu_{2}(T(24)) = 3 + \nu_{2}(T(8))$. \\
\noindent
$9.$ The number $8$ is a power of $2$, so $\nu_{2}(T(8)) = J_{2} =3$. \\
\smallskip
Backwards substitution gives $\nu_{2}(T(5192)) = 554$. This can be verified
using \ref{val-2}. \\
The construction of $\nu_{2} \circ T$
given in the algorithm following Theorem \ref{main-thm} gives the
result of Frey and Sellers \cite{frey-sellers1}.
\begin{Cor}
The number $T(n)$ is odd if and only if $n$ is a Jacobstahl number.
\end{Cor}
\medskip
The next statement deals with the range of $\nu \circ T$.
\begin{Thm}
The range of $\nu_2 \circ T$ is $\mathbb{N}$.
Furthermore, for each $m \in \mathbb{N}$, the equation
$\nu_{2}(T(n)) = m $ has finitely many solutions, the largest being
$n = J_{2m+1}-1$.
\end{Thm}
\begin{proof}
The inequality
\begin{equation}
\nu_2(T(J_n+i)) > \nu_2(T(J_n+1))
= \nu_2(T(J_{n+1}-1)), \nonumber
\end{equation}
\noindent
for $1 < i < J_{n+1}-J_n-2$ and
$\nu_2(T(J_{n+2}-1)) = \nu_2(T(J_n-1)) + 1$, comes from the previous
discussion. Therefore
the minimum value of $\nu_2(T(n))$ around $2^n$
is attained exactly at $J_n+1$ and $J_{n+1}-1$.
These values are also {\em strictly} increasing along the even and odd
indices. Thus, $m < \nu_{2}(T(i))$
for any given $m$, provided $i$ is large enough.
To determine the last appearance of $m$, it is only required to
determine the last occurance of $n$
such that $\nu_2(T(J_n-1)) = m$. Since
$\nu_2(T(J_2-1)) = \nu_2(T(J_3-1)) = 1,$ it follows
that $\nu_2(T(J_{2n}-1))=\nu_2(T(J_{2{n+1}}-1))=n$.
\end{proof}
\noindent
{\bf Note}. Define $\lambda(m)$ to be the number of solutions of
$\nu_{2}(T(n)) = m$. The
values for $1 \leq m \leq 8$ are
shown below.
\begin{table}[h]
\begin{center}
\begin{tabular}{||c||c|c|c|c|c|c|c|c||}
\hline
$m $& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline
$\lambda(m)$ & 2 & 8 & 5 & 12 & 5 & 14 & 8 & 14 \\
\hline
\end{tabular}
\end{center}
\vskip 0.2in
\caption{The first $8$ values in the range of $\nu_{2} \circ T$}
\end{table}
\noindent
For example, the five solutions to $\nu(T(n))=5$ are
$16, \, 342, \, 682, \, 684$ and
$J_{11} -1 = 1364$ and the eight solutions to $\nu(T(n))=7$ are
$26, \, 38, \, 46, \, 82, \, 5462,
\newline
\, 10922, \, 10924$ and $J_{15}-1 = 21844$. \\
\noindent
{\bf Note}. In sharp contrast to the $2$-adic valuation, D. Frey
and J. Sellers \cite{frey-sellers2,frey-sellers3}
show that if $p \geq 3$ is
a prime, the equation
$\nu_{p}(T(n))) = m$ has
infinitely many solutions,
for each $m \in \mathbb{N}$. \\
\noindent
{\bf Scaling}. The graph of $\nu_{2} \circ T$ on the interval
$I_{n}:= [ \, J_{n}, J_{n+1} \, ]$ vanishes at the endpoints and it
is symmetric about the midpoint $2^{n}$ where the maximum value $J_{n-1}$
occurs. Figure \ref{figure-3} shows $\nu_{2}(T(n))$ on the interval
$I_{10} = [ 341, 683]$ and Figure \ref{figure-3a} depicts
the first $15$ such graphs, scaled to the unit square.
\medskip
{{
\hyphenation{between}
\hyphenation{valuation}
\begin{figure}[ht]
\begin{minipage}[t]{20em}
\centering
\epsfig{file=figure3.eps,width=16em,angle=0}
\caption{The $2$-adic valuation of $T(n)$ \newline between minima}
\label{figure-3}
\end{minipage}%
\begin{minipage}[t]{20em}
\centering
\epsfig{file=all15.eps,width=16em,angle=0}
\caption{The scaled version of the $2$-adic \newline valuation of $T(n)$}
\label{figure-3a}
\end{minipage}
\end{figure}
}}
\medskip
The interval $[J_{n}, 2^{n} ] \subset I_{n}$ is divided into
$[J_{n}, J_{n}+2J_{n-3}]$ and $[J_{n}+2J_{n-3}, 2^{n}]$. Scaling
$I_{n}$ to $[0,1]$ the shifted endpoints of these
subintervals are
\begin{equation}
\left\{ 0, \, \frac{2J_{n-3}}{J_{n+1}-J_{n}}, \,
\frac{2^{n}-J_{n}}{J_{n+1}-J_{n}} \right\}
\to \left\{ 0, \frac{1}{4}, \frac{1}{2} \right\},
\end{equation}
\noindent
as $n \to \infty$. \\
The linear interpolation of the
function $\nu_{2} \circ T$ on the interval $I_{n} = [J_{n},J_{n+1}]$ is
now scaled to the unit square by
\begin{equation}
f_{n}(x) = \frac{1}{J_{n-1}} (\nu_{2} \circ T)
\left( J_{n} + (J_{n+1}-J_{n})x \right).
\end{equation}
\noindent
The algorithm in Section \ref{sec-intro} is now translated into a relation
for the functions $f_{n}$.
\smallskip
\begin{Prop}
The function $f_{n}$ satisfies
\begin{equation}
f_{n}(x) =
\frac{J_{n+1}-J_{n}}{J_{n-1}} x + \frac{J_{n-3}}{J_{n-1}}
f_{n-2} \left( \frac{J_{n+1}-J_{n}}{J_{n-1}-J_{n-2}}x \right), \nonumber
\end{equation}
\noindent
for $0 \leq x \leq \frac{2J_{n-3}}{J_{n+1}-J_{n}}$ and
\begin{equation}
f_{n}(x) =
\frac{J_{n-2}}{J_{n-1}} f_{n-1} \left( \frac{J_{n+1}-J_{n}}{J_{n}-J_{n-1}}
x - \frac{2J_{n-3}}{J_{n}-J_{n-1}} \right) +
\frac{2J_{n-3}}{J_{n-1}},
\nonumber
\end{equation}
\noindent
for $ \frac{2J_{n-3}}{J_{n+1}-J_{n}}
\leq x \leq \frac{J_{n-1}}{J_{n+1}-J_{n}}$.
\end{Prop}
A contraction mapping argument shows that $f_{n}$ converges to the unique
function $f: [0,1] \to [0,1]$ that satisfies
\begin{equation}
f(x) = \begin{cases}
2x + \frac{1}{4} f(4x), & \text{ if } 0 \leq x < \frac{1}{4}; \nonumber \\
\frac{1}{2} + \frac{1}{2} f( 2x - \tfrac{1}{2}), & \text{ if }
\frac{1}{4} \leq x \leq \frac{3}{4}; \nonumber \\
2(1-x) + \frac{1}{4} f(4x-3), & \text{ if } \frac{3}{4} < x \leq 1.
\end{cases}
\label{fixedpoint}
\end{equation}
\noindent
This is the function obtained from Figure \ref{figure-1} as the number of
points becomes infinite. The
details are ommited.
\section{The $3$-adic valuation of $T(n)$} \label{sec-three}
\setcounter{equation}{0}
The analysis of the $2$-adic valuation of $T(n)$ presented in Section
\ref{sec-desc} is now extended to the
prime $p=3$. A complete analytic description of Figure
\ref{figure-2} is possible. Only the results are given since the arguments are
similar to those for $p=2$.
The $3$-adic expansion of $n \in \mathbb{N}$ is
\begin{equation}
n = a_{j} \cdot 3^{j} + a_{j-1} \cdot 3^{j-1} + \cdots + a_{1} \cdot 3 +
a_{0}
\label{base3-exp}
\end{equation}
\noindent
is used to define
\begin{equation}
S_{3}(n) := a_{0} + a_{1} + \cdots + a_{k}.
\label{sum-base3}
\end{equation}
The analog of Theorem \ref{main-thm} is stated first.
\begin{Thm}
\label{main-thm-3}
The function
$\nu_{3} \circ T$ restricted to the interval $K_{n}:= [3^{n}, 3^{n+1}]$
is determined by its restriction to $K_{n-1}$.
\end{Thm}
A characterization of the values $n$ for which $\nu_{3}(T(n)) = 0$ is given
next.
\begin{Thm}
\label{val3-zero}
Let $n \in \mathbb{N}$ with (\ref{base3-exp}) as its expansion in base $3$. Then
$\nu_{3}(T(n)) = 0$ if and only if there is
an index $0 \leq i \leq k$ such that $a_{0}=a_{1}= \cdots = a_{i-1} = 0$
and $a_{i+1}=a_{i+2} = \cdots = a_{k} = 0 \text{ or } 2$, with
$a_{i}$ arbitrary.
\end{Thm}
Proposition \ref{prop-valuetn} is now written as
\begin{equation}
\nu_{3}(T(n)) = \tfrac{1}{2} \sum_{j=1}^{n-1} \muc{j},
\label{nu3-tn}
\end{equation}
\noindent
using the function
\begin{equation}
\muc{j} := S_3(2j)+S_3(2j+1)-S_3(3j+1)-S_3(j).
\end{equation}
\noindent
\begin{Thm}
\label{val3-symmetry}
The $3$-adic valuation of $T(n)$ satisfies
\smallskip
\noindent
a) $ \nu_{3}(T(3n)) = 3 \nu_{3}(T(n))$.
\smallskip
\noindent
b) $\nuthree{a}=\nuthree{2 \cdot 3^n+a}$ for
$0 \leq a \leq 3^{n}$ and
\begin{equation}
\muc{3^n+i}=\left\{
\begin{array}{lll}
\muc{i}+2, & \text{if } 1 \le i < \tfrac{1}{2}3^n; \nonumber \\
\muc{i}, & \text{if } i = \tfrac{1}{2}(3^n+1); \nonumber \\
\muc{i}-2, & \text{if } \tfrac{1}{2}3^n+1 < i \le 3^n; \nonumber
\end{array}
\right.
\end{equation}
\noindent
for $1 \leq i < 3^{n}$.
\smallskip
\noindent
c) $\muc{3^n+i}= - \muc{2 \cdot 3^n-i+1}$ for
$1 \le i < \frac{3^n}{2}$.
\end{Thm}
The rest of this section contains a procedure to
compute $\nu_{3}(T(n))$. Consider the ternary expansion (\ref{base3-exp})
and define a sequence of integers $\{ x_{j}, x_{j-1}, \cdots, x_{1},x_{0} \}$
according to the following rules: \\
\noindent
a) the initial term is $x_{j} = n$.
\smallskip
\noindent
b) for $1 \leq i \leq j$, write $x_{i}$ in base $3$ with $i+1$ digits (a
certain number of zeros might have to be placed at the beginning) and let
$d_{i}$ be the first digit in this expansion;
\smallskip
\noindent
c) let $t_{i}$ be the integer obtained by dropping the first digit of
the expansion of $x_{i}$ in part b). Then, for $1 \leq i \leq j$,
\begin{equation}
x_{i-1} = \begin{cases}
t_{i}, \quad & \text{ if } d_{i} = 0 \text{ or } 2; \\
\text{Min}\left( t_{i}, 3^{i}- t_{i} \right), \quad &
\text{ if } d_{i} = 1.
\end{cases}
\end{equation}
\begin{Thm}
\label{thm-3adic}
The sequence defined above satisfies
\begin{equation}
\nu_{3} \left( T(x_{i}) \right) =
\begin{cases}
\nu_{3} \left( T(x_{i+1}) \right), \quad & \text{ if }
d_{i} = 0 \text{ or } 2; \nonumber \\
\nu_{3} \left( T(x_{i+1}) \right) -x_{i}, \quad & \text{ if } d_{i} = 1.
\end{cases}
\end{equation}
\noindent
Moreover
\begin{equation}
\nu_{3} \left( T(n) \right) = \sum_{d_{i+1}=1 } x_{i}.
\end{equation}
\end{Thm}
Observe that the number of $3$-adic digits is decreased by $1$ in the
passage from $x_{i}$
to $x_{i-1}$. Therefore $0 \leq x_{1} \leq 2$ and the procedure terminates
in a finite number of steps. \\
\noindent
{\bf Example} A symbolic
computation shows that $\nu_{3}(T(1280)) = 180$. This is now
confirmed using Theorem \ref{thm-3adic}. The $3$-adic expansion of
$n=1280$ is $[1 \, 2, \, 0, \, 2, \, 1, \, 0, \, 2]_{3}$.
Therefore $j=6$ and $x_{6}=1280$.
The first digit is $d_{6}=1$. Dropping it yields
$t_{6} = [2, \, 0, \, 2, \, 1, \, 0, \, 2]_{3}$ = 551 and
$x_{5} = \text{Min}(551, 3^{6}-551) = 178$. The $3$-adic expansion of
$x_{5}$ is written as
$x_{5} = [0 \, 2, \, 0, \, 1, \, 2, \, 1]_{3}$. The extra zero in front
is added to have $6$ digits in this expansion. This is the first step of
the algorithm. The complete sequence is gioven in table \ref{table-2}. \\
\begin{table}[h]
\begin{center}
\begin{tabular}{|c||r|r|r|r|r|r|r|}
\hline
$i$ & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ \hline
$d_{i}$ & 1 & 0 & 2 & 0 & 1 & 0 & 0 \\ \hline
$x_{i}$ & 1280 & 178 & 178 & 16 & 16 & 2 & 2 \\
\hline
\end{tabular}
\end{center}
\vskip 0.2in
\caption{The algorithm for $\nu_{3} \circ T$ for $n=1280$}
\label{table-2}
\end{table}
The terms contributing to $\nu_{3}(T(n))$ are those with $d_{i+1}=1$, namely
$i=5$ and $i=1$. This gives
$x_{5} + x_{1} = 178 +2 = 180$.
\medskip
\noindent
{\bf Example}. The value
$\nu_{3}(T(1000))$ is computed from the table below. It yields
$\nu_{3}(T(1000)) = x_{5} + x_{4} + x_{2} = 271 + 28 + 1 = 300$.
\begin{table}[h]
\begin{center}
\begin{tabular}{|c||r|r|r|r|r|r|r|}
\hline
$i$ & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\ \hline
$d_{i}$ & 1 & 1 & 0 & 1 & 0 & 0 & 0 \\ \hline
$x_{i}$ & 1000 & 271 & 28 & 28 & 1 & 1 & 1 \\
\hline
\end{tabular}
\end{center}
\vskip 0.2in
\caption{The algorithm for $\nu_{3} \circ T$ for $n=1000$}
\end{table}
\medskip
%and define two sequence of integers $\{ n_{1}, \ldots, n_{k} \}$ and
%$\{ n_{1}', \ldots, n_{k}' \}$. Begin with
%$n_{k} = n_{k}' = n$, and, for $0 \leq j < k$ and assume having
%\begin{equation}
%n'_{j+1}=\sum^{j+1}_{i=0}b_{j+1,i} 3^i,
%\end{equation}
%\noindent
%then define recursively
%\begin{eqnarray*}
%n_j &=& \sum^{j}_{i=0}b_{j+1,i} 3^i, \\
%n'_j &=& \left\{
%\begin{array}{lll}
%n_{j} & \text{if } b_{j+1,j+1} = 0,2; \\
%\min(n_j, 3^{j+1} - n_{j}) & \text{if } b_{j+1,j+1} = 1.
%\end{array}
%\right.
%\end{eqnarray*}
%
%\smallskip
%
%The sequence $n_{j}'$ is decreasing and {\bf Explain better} \\
%
%\begin{Thm}
%\label{thm-3adic}
%The $3$-adic valuation of $T(n)$ satisfies
%\begin{equation}
%\nuthree{n_j} = \left\{
%\begin{array}{lll}
%\nuthree{n'_{j-1}} & \text{if } a_j = 0,2; \\
%\nuthree{n'_{j-1}} + 2 n'_{j-1} & \text{if } a_j = 1.
%\end{array}
%\right.
%\end{equation}
%\end{Thm}
%
%\noindent
%{\bf Example}. Let $n=1280$, whose representation with base 3 is $1202102$.
%Then $k=6$ and we have
%
%\begin{table}[h]
%\begin{center}
%\begin{tabular}{||c||r|r|r|r||}
%\hline
%$j$&$n_j$&$n_j$ (base 3)&$n'_j$ &$n'_j$ (base 3)\\\hline
%6&1280&1202102&1280&1202102\\
%5&551&202102&178&020121 \\
%4&178&20121&178&20121\\
%3&16&0102&16&0102\\
%2&16&102&16&102\\
%1&7&21&2&02\\
%0&2&2&1&1\\\hline
%\end{tabular}
%\end{center}
%\vskip 0.2in
%\caption{The algorithm for $\nu_{3} \circ T$}
%\end{table}
%
%It follows that
%\begin{eqnarray}
%\nuthree{1280} & = & 2 n'_5 + \nuthree{n'_5} \nonumber \\
%& = & 2 n'_5+\nuthree{n_2} \nonumber \\
%& = & 2 n'_5+2\nuthree{n'_1}+\nuthree{n_1} \nonumber \\
%& = & 360. \nonumber
%\end{eqnarray}
%
\medskip
\noindent
Theorem \ref{thm-3adic} yields a scaling procedure similar
to the one given for $p=2$ in Section \ref{sec-desc}. The resulting
limiting function satisfies
\begin{equation}
f(x) =
\begin{cases}
\frac{1}{3}f(3x), & \text{ if } 0 \leq x \leq \frac{1}{3};
\nonumber \\
4(x - \frac{1}{3}) + \frac{1}{3}f(3x-1), & \text{ if }
\frac{1}{3} \leq x \leq \frac{1}{2};
\nonumber \\
-4(x - \frac{2}{3}) + \frac{1}{3}f(3x-1), & \text{ if }
\frac{1}{2} \leq x \leq \frac{2}{3};
\nonumber \\
\frac{1}{3}f(3x-2), & \text{ if } \frac{2}{3} \leq x \leq 1.
\nonumber
\end{cases}
\label{fig-3adic}
\end{equation}
The graph of $f$ corresponds to the limiting behavior of
Figure \ref{figure-2}. \\
\noindent
{\bf Note}. A similar phenomena is observed for larger primes. The figures
show the valuations of $T(n)$ for $p=5$ and $p=7$ in the range $1 \leq n
\leq 2000$.
{{
\begin{figure}[ht]
\begin{minipage}[t]{20em}
\centering
\epsfig{file=prime5a.eps,width=17em,angle=0}
\caption{The $5$-adic valuation of $T(n)$}
\label{figure-5}
\end{minipage}%
\begin{minipage}[t]{20em}
\centering
\epsfig{file=prime7a.eps,width=17em,angle=0}
\caption{The $7$-adic valuation of $T(n)$}
\label{figure-7}
\end{minipage}
\end{figure}
}}
\section{A generalization} \label{sec-gen}
\setcounter{equation}{0}
The sequence
\begin{equation}
T_{p}(n) := \prod_{j=0}^{n-1} \frac{(pj+1)!}{(n+j)!},
\end{equation}
\noindent
contains $T(n)$ of (\ref{T-seq}) as the special
case for $p=3$. In
this section we present some elementary properties of this generalization.
\begin{Thm}
For a fixed prime $p \geq 3$, the numbers $T_{p}(n)$ are integers.
\end{Thm}
\begin{proof}
Start with
\begin{equation}
T_{p}(n+1) = T_{p}(n) \times y_{p}(n),
\label{recur-11}
\end{equation}
\noindent
where
\begin{equation}
y_{p}(n) = \frac{(pn+1)! \, n!}{(2n+1)! \, (2n)!}.
\label{recur-11a}
\end{equation}
Define
\begin{equation}
x_{p}(n) := \frac{(pn+1)!}{((p-1)n+1)! \, n!} = \binom{pn+1}{n},
\end{equation}
\noindent
and observe that
\begin{equation}
y_{p}(n) = x_{p}(n) \times y_{p-1}(n) n!.
\end{equation}
\noindent
Iterating this argument yields
\begin{equation}
y_{p}(n) =
\prod_{r=0}^{k-1}x_{p-r}(n) y_{p-k}(n).
\end{equation}
\noindent
The choice $k = p-4$ yields
\begin{equation}
y_{p}(n) =
\binom{4n+1}{2n} \, n!^{p-3}
\prod_{r=0}^{p-5} \binom{(p-r)n+1}{n}.
\nonumber
\end{equation}
\noindent
The upshot is that $y_{p}(n)$ is an integer. The
recurrence (\ref{recur-11}) and the initial condition
$T_{p}(1) = 1$ now show that $T_{p}(n)$ is also an integer. The explicit
formula
\begin{equation}
T_{p}(n) = \prod_{j=1}^{n-1} \binom{4j+1}{2j} j!^{p-3}
\prod_{r=0}^{p-5} \binom{(p-r)j+1}{j}
\end{equation}
\noindent
follows from the recurrence. \\
\end{proof}
\begin{proof}
An alternative proof of the fact that $y_{p}(n)$
is an integer was shown to us by Valerio de Angelis. Observe that, for
$p \geq 4$, we have $(pn+1)! = N \times (4n+1)!$ for
the integer $N = (4n+2)_{(p-4)n}$. Therefore
\begin{equation}
y_{p})(n) = (4n+2)_{(p-4)n} \times
\binom{4n+2}{2n} n!,
\end{equation}
\noindent
shows that $y_{p}(n) \in \mathbb{N}$ and yields the explicit formula
\begin{equation}
T_{p}(n) = \prod_{j=1}^{n-1} (4j+2)_{(p-4)n} \binom{4j+1}{2j} j!.
\end{equation}
\end{proof}
\begin{proof}
A third proof using Theorem \ref{cart-kup} was shown to us by
T. Amdeberhan.
The required inequality states:
if $n,k,p \in \mathbb{N}$ and $p\geq 3$, then
$$\psi_k(n;p):=\sum_{j=0}^{n-1}\left\lfloor{{pj+1} \over {k} } \right\rfloor-
\sum_{j=0}^{n-1} \left\lfloor{{n+j} \over {k}} \right\rfloor\geq 0.$$
It suffices to prove the special
case $p=3$, i.e. $\psi_k(n;3)\geq 0$ which we denote by $\psi_k(n)$
for $k\geq 3, n\geq 1$.
\smallskip
\noindent
Write $n=ck+r$ where $0\leq r\leq k-1$. We approach a reduction
process by breaking down the respective sums as follows.
\begin{eqnarray}
\sum_{j=0}^{n-1} \left\lfloor{{3j+1} \over{k} } \right\rfloor
& = & \sum_{j=0}^{ck-1} \left\lfloor{{3j+1} \over {k} } \right \rfloor+
\sum_{j=0}^{r-1} \left\lfloor{{3(ck+j)+1} \over {k} } \right\rfloor \nonumber \\
&= & \sum_{j=0}^{ck-1} \left\lfloor{{3j+1} \over {k} } \right\rfloor+ 3cr
+\sum_{j=0}^{r-1} \left\lfloor{{3j+1} \over {k} } \right\rfloor, \nonumber
\end{eqnarray}
\noindent
and
\begin{eqnarray}
\sum_{j=0}^{n-1} \left\lfloor{{n+j} \over {k}} \right\rfloor & = &
\sum_{j=0}^{ck-1} \left\lfloor{{ck + r +j} \over {k}} \right\rfloor
+2cr+\sum_{j=0}^{r-1} \left\lfloor{{r+j} \over {k}} \right \rfloor \nonumber \\
&=& \sum_{j=0}^{ck-1}\left\lfloor{{ck+j} \over{k}} \right\rfloor-
\sum_{j=0}^{r-1} \left\lfloor{{ck+j} \over {k} } \right \rfloor+
\sum_{j=0}^{r-1} \left\lfloor{{2ck+j} \over {k} } \right\rfloor
+2cr+\sum_{j=0}^{r-1} \left\lfloor{{r+j} \over {k} } \right\rfloor \nonumber \\
&=& \sum_{j=0}^{ck-1} \left\lfloor{{ck+j} \over {k} } \right \rfloor+
\sum_{j=0}^{r-1} \left\lfloor{{ck+j} \over {k}} \right\rfloor
+2cr+\sum_{j=0}^{r-1} \left\lfloor{{r+j} \over {k} } \right\rfloor \nonumber \\
&=& \sum_{j=0}^{ck-1} \left\lfloor{{ck+j} \over {k} } \right\rfloor+
cr+\sum_{j=0}^{r-1} \left\lfloor{{j} \over {k} } \right\rfloor
+2cr+\sum_{j=0}^{r-1} \left\lfloor{{r+j} \over {k} } \right\rfloor \nonumber \\
&=&\sum_{j=0}^{ck-1} \left\lfloor{{ck+j} \over {k} } \right\rfloor+
3cr+\sum_{j=0}^{r-1} \left\lfloor{{r+j} \over {k} } \right\rfloor. \nonumber
\end{eqnarray}
Combining these expressions, we find that $\psi_k(ck+r)=\psi_k(ck)+\psi_k(r)$.
A similar argument with $r$ replaced by $k$ produces
$\psi_k(ck+k)=\psi_k(ck)+\psi_k(k)$. We conclude $\psi_k$ is
\it $k$-Euclidean, \rm i.e.
$$\psi_k(ck+r)=c\psi_k(k)+\psi_k(r).$$
Therefore, we just need to verify the assertion $\psi_k(r)\geq 0$. In
fact, we will strengthen it by giving an explicit formula in vectorial form
$$[\psi_k(0),\dots,
\psi_k(k-1)]=[0,0^{k^{\prime}},1,2,\dots,\lfloor{k^{\prime\prime}/2}\rfloor,
\lceil{k^{\prime\prime}/2}\rceil,\dots,2,1,0^{k^{\prime}}];$$
where $k^{\prime}=\lfloor{\frac{k+1}3}\rfloor,
k^{\prime\prime}=k-1-2k^{\prime}$ and $0^{k^{\prime}}$ means $k^{\prime}$
consecutive zeros. This admits an elementary proof. Note that $\psi_k(ck)=0$,
hence $\psi_k$ is \it $k$-periodic \rm and it
satisfies $\psi_k(ck+r)=\psi_k(r)$.
\end{proof}
\medskip
We now present a recurrence for the $p$-adic
valuation of the sequence $T_{p}(n)$. The
special role of the prime $p=3$ becomes apparent.
\begin{Thm}
Let $p$ be prime. Then the sequence $T_{p}(n)$ satisfies
\begin{equation}
\nu_{p}(T_{p}(pn)) = p \nu_{p}(T_{p}(n)) + \frac{1}{2}p(p-3)n^{2}.
\end{equation}
\end{Thm}
\begin{proof}
Start with
\begin{equation}
T_{p}(pn) = \prod_{j=0}^{pn-1} (pj+1)!/\prod_{j=pn}^{2pn-1} j!
\end{equation}
\noindent
and using Legendre's formula to obtain
\begin{equation}
(p-1) \nu_{p}(T_{p}(pn)) = \sum_{j=0}^{pn-1} pj+1 - S_{p}(pj+1) -
\sum_{j=pn}^{2pn-1} j-S_{p}(j).
\end{equation}
\noindent
The terms independent of the function $S_{p}$ add up to $n^{2}p(p-3)/2$ so
that
\begin{equation}
\nu_{p}(T_{p}(pn)) - p \nu_{p}(T_{p}(n)) =
\frac{1}{2}n^{2}p(p-3) + \frac{1}{p-1}W_{p,n},
\end{equation}
\noindent
where
\begin{equation}
W_{p,n} = - \sum_{j=0}^{pn-1}S_{p}(pj+1) +
\sum_{j=pn}^{2pn-1} S_{p}(j) +
p \sum_{j=0}^{n-1}S_{p}(pj+1) - p \sum_{j=0}^{n-1} S_{p}(n+j).
\end{equation}
\noindent
Theresult follows from $W_{p,n} = 0$. To establish this use
$S_{p}(pj+1) = 1 + S_{p}(j)$ to write
\begin{equation}
W_{p,n} = - \sum_{j=0}^{pn-1}S_{p}(j) +
\sum_{j=pn}^{2pn-1} S_{p}(j) +
p \sum_{j=0}^{n-1}S_{p}(j) - p \sum_{j=n}^{2n-1} S_{p}(j).
\label{W-term}
\end{equation}
\noindent
In the second sum, write $j = pr+k$ with $0 \leq k \leq p-1$ and
$n \leq r \leq 2n-1$, to obtain
\begin{eqnarray}
\sum_{j=pn}^{2pn-1} S_{p}(j) & = & \sum_{k=0}^{p-1}
\sum_{r=n}^{2n-1} S_{p}(pr+k) \nonumber \\
& = & \sum_{r=n}^{2n-1} \sum_{k=0}^{p-1} \left( k + S_{p}(r) \right)
\nonumber \\
& = & \frac{n}{2}p(p-1) + p \sum_{r=n}^{2n-1} S_{p}(r).
\nonumber
\end{eqnarray}
\noindent
This form of the second term is now combined with the fourth one
in (\ref{W-term}). A similar
calculation on the first term gives the result. Indeed,
\begin{eqnarray}
\sum_{j=0}^{pn-1} S_{p}(j) & = &
\sum_{k=0}^{p-1} \sum_{r=0}^{n-1} S_{p}(pr+k) \nonumber \\
& = & \sum_{k=0}^{p-1} \sum_{r=0}^{n-1} \left( k + S_{p}(r) \right)
\nonumber \\
& = & \frac{n}{2}p(p-1) + p \sum_{r=0}^{n-1} S_{p}(r). \nonumber
\end{eqnarray}
\end{proof}
\begin{Cor}
For $p$ a prime, we have
\begin{equation}
\nu_{p}(T_{p}(p^{n})) = \frac{p^{n}(p-3)(p^{n}-1)}{2(p-1)}.
\end{equation}
\end{Cor}
\begin{proof}
Replace $n$ by $p^{n}$ in the Theorem to obtain
\begin{equation}
\nu_{p}(T_{p}(p^{n+1})) = p \nu_{p}(T_{p}(p^{n})) + \frac{1}{2}(p-3)p^{2n+1}.
\end{equation}
\noindent
Iterating this identity yields the result.
\end{proof}
\medskip
\noindent
{\bf Problem}. The sequence $T_{p}(n)$ comes as a formal generalization of
the original sequence $T_{3}(n)$ that appeared in counting alternating
symmetric matrices. This raises the question: {\em what does}
$T_{p}(n)$ {\em count?}
\bigskip
\section{Acknowledgments}
The authors wish to thank Tewodros Amdeberhan, Valerio de Angelis and
A. Straub for many conversations
about this paper. Marc Chamberland helped in the experimental
discovery of the generalization presented in Section \ref{sec-gen}.
The authors also wish to thank a referee for a very complete and illuminating
report on a preliminary version of the paper. This included the ideas
behind Theorem \ref{thm-fixed}.
The work of the second author was partially funded by
$\text{NSF-DMS } 0713836$. \\
\bigskip
\begin{thebibliography}{10}
\bibitem{amm1}
T.~Amdeberhan, D.~Manna, and V.~Moll.
\newblock The $2$-adic valuation of a sequence arising from a rational
integral.
\newblock {\em J. Combin. Theory Ser. A}, {\bf 115} (2008),
1474--1486.
\bibitem{amm2}
T.~Amdeberhan, D.~Manna, and V.~Moll.
\newblock The $2$-adic valuation of {S}tirling numbers.
\newblock {\em Experiment. {M}ath.}, {\bf 17} (2008), 69--82.
\bibitem{bressoud1}
D.~Bressoud.
\newblock {\em Proofs and {C}onfirmations: the story of the {A}lternating
{S}ign {M}atrix {C}onjecture}.
\newblock Cambridge University Press, 1999.
\bibitem{bressoud99}
D.~Bressoud and J.~Propp.
\newblock How the {a}lternating {s}ign {m}atrix {c}onjecture was solved.
\newblock {\em Notices Amer. Math. Soc.}, {\bf 46} (1999), 637--646.
\bibitem{cart-kupka}
D.~Cartwright and J.~Kupka.
\newblock When factorial quotients are integers.
\newblock {\em Austral. Math. Soc. Gaz.}, {\bf 29} (2002), 19--26.
\bibitem{frey-sellers1}
D.~Frey and J.~Sellers.
\newblock \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL3/SELLERS/sellers.html}{Jacobsthal numbers and {a}lternating {s}ign {m}atrices}.
\newblock {\em J. Integer Sequences}, {\bf 3} (2000), Article 00.2.3.
\bibitem{frey-sellers2}
D.~Frey and J.~Sellers.
\newblock \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL4/SELLERS/powers.html}{On powers of $2$ dividing the values of certain plane partitions}.
\newblock {\em J. Integer Sequences}, {\bf 4} (2001), Article 01.1.8.
\bibitem{frey-sellers3}
D.~Frey and J.~Sellers.
\newblock Prime power divisors of the number of $n \times n$ {A}lternating
{S}ign {M}atrices.
\newblock {\em Ars Combin.}, {\bf 71} (2004), 139--147.
\bibitem{legendre1}
A.~M. Legendre.
\newblock {\em Theorie des {N}ombres}.
\newblock Firmin {D}idot {F}reres, {P}aris, 1830.
\bibitem{manna-moll-survey}
D.~Manna and V.~Moll.
\newblock A remarkable sequence of integers.
\newblock To appear, {\em Expo. Math.}, 2009.
\bibitem{mrr-1}
W.~H. Mills, D.~P. Robbins, and H.~Rumsey.
\newblock Proof of the {M}ac{D}onald conjecture.
\newblock {\em Inv. Math.}, {\bf 66} (1982), 73--87.
\bibitem{zeilberger96}
D.~Zeilberger.
\newblock Proof of the {A}lternating {S}ign {M}atrix conjecture.
\newblock {\em Electronic {J}. {C}ombin.}, {\bf 3} (2) (1996), Paper \#R13.
\newblock Electronic version at \href{http://www.combinatorics.org/Volume_3/Abstracts/v3i2r13.html}{\tt http://www.combinatorics.org/Volume\_3/Abstracts/v3i2r13.html}.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A10; Secondary 11B75, 11Y55.
\noindent \emph{Keywords: }
Alternating sign matrices, Jacobsthal numbers, valuations.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences \seqnum{A005130} and \seqnum{A001045}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received January 28 2009;
revised version received April 27 2009.
Published in {\it Journal of Integer Sequences}, April 30 2009.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}