\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}