<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[10pt]{article}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{amsthm,amssymb}
\usepackage{psfig,epsf}

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

\newcommand{\D}{\displaystyle}
\newcommand{\lrfloor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\lrpar}[1]{\left( #1 \right)}
\newcommand{\pwp}[1]{ \frac{2^{#1}+1}{3}}
\newcommand{\pwm}[1]{ \frac{2^{#1}-1}{3}}
\newcommand{\jac}[1]{ \frac{2^{#1 +1}+(-1)^{#1}}{3}}
\renewcommand{\lrpar}[1]{\left( #1 \right)}
\renewcommand{\j}[1]{J_{#1}}
\newcommand{\Nk}{N_k^{\#}(n)}
\newcommand{\Dk}{D_k^{\#}(n)}
\newcommand{\Nkjm}{N_k^{\#}(\j{m})}
\newcommand{\Dkjm}{D_k^{\#}(\j{m})}
\newcommand{\DD}[2]{D^{\#}_{#1}(#2)}
\newcommand{\Nkl}{N_k^{\#}(2^{\ell})}
\newcommand{\Dkl}{D_k^{\#}(2^{\ell})}
\newcommand{\N}[2]{N^{\#}_{#1}(#2)}
\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}



\newtheorem{Lemma}{Lemma}[section]
\newtheorem{Theorem}[Lemma]{Theorem}
\newtheorem{Prop}[Lemma]{Proposition}
\newtheorem{Corollary}[Lemma]{Corollary}
\newtheorem{Notation}[Lemma]{Notation}
\newtheorem{Remark}[Lemma]{Remark}
\newtheorem{Table}[Lemma]{Table}
\renewcommand{\baselinestretch}{1.2} 
\renewcommand{\arraystretch}{.7} 

\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
 -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother


\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo23.eps}
\vskip 1cm
{\LARGE\bf Jacobsthal Numbers and Alternating Sign Matrices}
\vskip 1.5cm
%\author{\href{http://www.cedarville.edu/dept/sm/ddf_www.htm}
\large Darrin D. Frey and James A. Sellers \\ \medskip

%\href{http://www.cedarville.edu/dept/sm/jas_www.htm}
Department of Science and Mathematics \\
Cedarville College \\
Cedarville, OH 45314 \\
\medskip
Email addresses:
\href{mailto:freyd@cedarville.edu}{freyd@cedarville.edu}
and \href{mailto:sellersj@cedarville.edu}{sellersj@cedarville.edu} 
\vskip2.5cm
\bf {Abstract}
\end{center}
{\em Let $A(n)$ denote the number of $n\times n$ alternating sign
matrices
and
$J_m$ the $m^{th}$ Jacobsthal number.
It is known that
$$A(n) = \prod_{\ell =0}^{n-1}\frac{(3\ell +1)!}{(n+\ell )!}.$$
The values of $A(n)$
are in general highly composite.  
The goal of this paper is to prove that $A(n)$ is odd if and
only if $n$ is a Jacobsthal number,
thus showing that $A(n)$ is odd infinitely often.  
}

\vspace*{+.1in}
\noindent 2000 {\it Mathematics Subject Classification}: \ \ 05A10,
15A15

\noindent \emph{Keywords: alternating sign matrices, Jacobsthal
numbers}


\begin{section}{Introduction}
In this paper we relate two seemingly unrelated
areas of mathematics:  alternating sign matrices and Jacobsthal
numbers. 
We begin with a brief discussion of alternating sign matrices.

An $n\times n$ alternating sign matrix is an $n\times n$ matrix of
$1$s,
$0$s
and $-1$s such that
\begin{itemize}
\item the sum of the entries in each row and column is 1, and 
\item the signs of the nonzero entries
in every row and column alternate.
\end{itemize}

Alternating sign matrices include 
permutation matrices, in which each row and column contains only one
nonzero entry, a 1.

For example, the seven $3\times 3$
alternating sign matrices are
                          
\[
\left(
      \begin{array}{ccc}
         1 &amp; 0 &amp; 0\\
         0 &amp; 1 &amp; 0\\
         0 &amp; 0 &amp; 1
      \end{array}
\right),
\left(
      \begin{array}{ccc}
         1 &amp; 0 &amp; 0\\
         0 &amp; 0 &amp; 1\\
         0 &amp; 1 &amp; 0
      \end{array}
\right),
\left(
      \begin{array}{ccc}
         0 &amp; 0 &amp; 1\\
         1 &amp; 0 &amp; 0\\
         0 &amp; 1 &amp; 0
      \end{array}
\right),
\left(
      \begin{array}{ccc}
         0 &amp; 0 &amp; 1\\
         0 &amp; 1 &amp; 0\\
         1 &amp; 0 &amp; 0
      \end{array}
\right),
\]

\[
\left(
      \begin{array}{ccc}
         0 &amp; 1 &amp; 0\\
         1 &amp; 0 &amp; 0\\
         0 &amp; 0 &amp; 1
      \end{array}
\right),
\left(
      \begin{array}{ccc}
         0 &amp; 1 &amp; 0\\
         0 &amp; 0 &amp; 1\\
         1 &amp; 0 &amp; 0
      \end{array}
\right),
\left(
      \begin{array}{ccc}
         0 &amp; 1 &amp; 0\\
         1 &amp; -1&amp; 1\\
         0 &amp; 1 &amp; 0
      \end{array}
\right)\,.
\]

The determination of a closed
formula
for $A(n)$ was undertaken by a variety of mathematicians
over the last 25 years or so.  David Bressoud's text
\cite{Bressoud}
chronicles these endeavors and discusses
the underlying mathematics
in a very readable way.
See also the survey article
\cite{notices} by Bressoud and Propp.

As noted in \cite{Bressoud}, a formula for $A(n)$ is given by
\begin{equation}
\label{asmformula}
A(n) = \prod_{\ell =0}^{n-1}\frac{(3\ell +1)!}{(n+\ell )!}.
\end{equation}

It is clear from this that, for most values of $n$, $A(n)$ will be
highly composite.
The following table shows the first few values of $A(n)$ (sequence
\seqnum{A005130} in \cite{Sloane}).
Other sequences related to alternating sign matrices can also be 
found in \cite{Sloane}.

{\small
\begin{center}
\begin{tabular}{r|r|r}
$n$ &amp; \multicolumn{1}{c|}{$A(n)$} &amp; \multicolumn{1}{c}{Prime
Factorization of $A(n)$}  \\ 
\hline
1 &amp; 1 &amp; 1\\
2 &amp; 2 &amp; 2\\
3 &amp; 7 &amp; 7\\
4 &amp; 42 &amp; $2\cdot 3\cdot 7$\\
5 &amp; 429 &amp; $ 3\cdot 11\cdot 13$\\
6 &amp; 7436 &amp; $ 2^{2}\cdot 11\cdot 13^{2}$\\
7 &amp; 218348 &amp; $ 2^{2}\cdot 13^{2}\cdot 17 \cdot 19$\\
8 &amp; 10850216 &amp; $ 2^{3}\cdot 13\cdot 17^{2} \cdot 19^{2}$\\
9 &amp; 911835460 &amp; $ 2^{2}\cdot 5\cdot 17^{2}  \cdot 19^{3}\cdot 23$\\
10&amp; 129534272700  &amp; $ 2^{2}\cdot 3\cdot 5^{2}  \cdot 7\cdot 17\cdot
19^{3}\cdot 23^{2}$\\
11   &amp;   31095744852375   &amp; $ 3^{2}\cdot 5^{3}\cdot 7  \cdot
19^{2}\cdot 23^{3}\cdot 29\cdot 31$\\
12   &amp;   12611311859677500 &amp; $ 2^{2}\cdot 3^{3}\cdot 5^{4} \cdot
19\cdot 23^{3}\cdot 29^{2} \cdot 31^{2}$  \\
13   &amp;   8639383518297652500  &amp; $ 2^{2}\cdot 3^{5}\cdot 5^{4} \cdot
23^{2}\cdot 29^{3}\cdot 31^{3} \cdot 37$ \\
14   &amp;   9995541355448167482000  &amp; $ 2^{4}\cdot 3^{5}\cdot 5^{3}
\cdot 23\cdot 29^{4}\cdot 31^{4} \cdot 37^{2}$ \\
15   &amp;   19529076234661277104897200  &amp; $ 2^{4}\cdot 3^{3}\cdot 5^{2}
\cdot 29^{4}\cdot 31^{5}\cdot 37^{3} \cdot 41\cdot 43$ \\
16   &amp;   64427185703425689356896743840 &amp; $ 2^{5}\cdot 3^{2}\cdot 5 
\cdot 11\cdot 29^{3}\cdot 31^{5}\cdot 37^{4}\cdot 41^{2}\cdot 43^{2}$ 
\\
17   &amp;   358869201916137601447486156417296 &amp; $ 2^{4}\cdot 3\cdot
7^{2}  \cdot 11\cdot 29^{2}\cdot 31^{4}\cdot 37^{5}\cdot 41^{3}\cdot
43^{3}\cdot 47$  \\
18   &amp;   3374860639258750562269514491522925456 &amp; $ 2^{4}\cdot
7^{3}\cdot 13  \cdot 29\cdot 31^{3}\cdot 37^{6}\cdot 41^{4}\cdot
43^{4}\cdot 47^{2}$  \\
19   &amp;   53580350833984348888878646149709092313244 &amp; $ 2^{2}\cdot
7^{3}\cdot 13^{2} \cdot 31^{2}\cdot 37^{6}\cdot 41^{5} \cdot
43^{5}\cdot 47^{3}\cdot 53$  \\
20   &amp;   1436038934715538200913155682637051204376827212 &amp; $
2^{2}\cdot 7^{4}\cdot 13^{2} \cdot 31\cdot 37^{5}\cdot 41^{6} \cdot
43^{6}\cdot 47^{4}\cdot 53^{2}$  \\
21   &amp;   64971294999808427895847904380524143538858551437757 &amp; $
7^{5}\cdot 13\cdot 37^{4}\cdot 41^{6}\cdot 43^{7}\cdot 47^{5} \cdot
53^{3}\cdot 59\cdot 61$  \\
22   &amp;   4962007838317808727469503296608693231827094217799731304 &amp; $
2^{3}\cdot 3\cdot 7^{6} \cdot 37^{3}\cdot 41^{5}\cdot 43^{7}\cdot
47^{6}\cdot 53^{4}\cdot 59^{2}\cdot 61^{2}$ \\  \hline
\end{tabular}
\end{center}
\smallskip
\centerline{Table 1:  Values of $A(n)$}
}
\bigskip

Examination of this table and further computer calculations reveals
that the first few 
values of $n$ for which $A(n)$ is odd are
$$1, 3, 5, 11, 21, 43, 85, 171.$$

These appear to be the well--known
{\it Jacobsthal numbers} $\{J_n\}$ (sequence \seqnum{A001045} in
\cite{Sloane}).
They are defined by the 
recurrence 
\begin{equation}
\label{jacrecur}
\j{n+2} = \j{n+1}+2\j{n} ~,
\end{equation}
with initial values 
$\j{0} = 1$ and $\j{1}=1.$

This sequence has a rich history, especially in view of its
relationship to the Fibonacci numbers.  For examples of recent work 
involving the Jacobsthal numbers, see \cite{Horadam1}, 
\cite{Horadam2}, \cite{Horadam3} and \cite{Horadam4}.

The goal of this paper is to prove that this is no coincidence:
for a positive integer $n$,
$A(n)$ is odd if and only if $n$ is a Jacobsthal number.  

\end{section}

\begin{section}{The Necessary Machinery}
To show that $A(\j{m})$ is odd for each positive integer $m$, 
we will show that the number of factors of 2 in the prime 
decomposition of $A(\j{m})$ is zero.  
To accomplish this, we develop formulas for the number of factors of
2 in
$$N(n) = \prod_{\ell =0}^{n-1}{(3\ell +1)!} \qquad\mbox{and}\qquad
D(n) = \prod_{\ell =0}^{n-1}{(n+\ell)!}~.$$ 
Once we prove that the number of factors of 2 is the same for
$N(\j{m})$ and
$D(\j{m})$, but not the same for $N(n)$ and $D(n)$ if $n$ is not a
Jacobsthal number,
we will have our result.  

We will make frequent use of the following lemma.
For a proof, see for example \cite[Theorem 2.29]{Long}.
\begin{Lemma}
\label{pinnfact}
The number of factors of a prime $p$ in $N!$ is equal to 
$$\sum\limits_{k\geq 1} \lrfloor{\frac{N}{p^k}}.$$
\end{Lemma}

It follows that the number of factors
of 2
in $N(n)$ is 
$$
N^{\#}(n) = \sum_{\ell =0}^{n-1}\sum_{k\geq 1} \lrfloor{\frac{3\ell
+1}{2^k}}
= \sum_{k\geq 1} N_k^{\#}(n)
$$
where 
\begin{equation}
\label{Nkformula}
N_k^{\#}(n) = \sum_{\ell =0}^{n-1}\lrfloor{\frac{3\ell +1}{2^k}}.
\end{equation}

Similarly, the number of factors of 2 in $D(n)$ is given by 
$$
D^{\#}(n) = \sum_{\ell =0}^{n-1}\sum_{k\geq 1}
\lrfloor{\frac{n+\ell}{2^k}}
= \sum_{k\geq 1} D_k^{\#}(n)
$$
where 
\begin{equation}
\label{Dkformula}
D_k^{\#}(n) = \sum_{\ell =0}^{n-1}\lrfloor{\frac{n+\ell}{2^k}}.
\end{equation}

For use below we note that the recurrence for the Jacobsthal numbers
implies the following explicit formula (cf. \cite{Tucker}).

\begin{Theorem}
The $m^{th}$ Jacobsthal number $\j{m}$ is given by 
\begin{equation}\label{Eq4a}
\j{m} = \frac{2^{m+1} + (-1)^m}{3}.
\end{equation}
\end{Theorem}


\end{section}

\begin{section}{Formulas for $N_k^{\#}(n)$ and $D_k^{\#}(n)$}


\begin{Lemma}
The smallest value of $\ell$ for which $$\D \lrfloor{\frac{3\ell +
1}{2^k}} =m,$$
where $m$ and $k$ are positive integers and $k \geq 2$, is

$$
\left\{ \begin{array}{lcr}
\frac{m}{3}2^k &amp; &amp; \quad\mbox{if}\quad m \equiv 0 \pmod 3\\
\frac{m-1}{3}2^k+\j{k-1} &amp; &amp; \quad\mbox{if}\quad m \equiv 1 \pmod
3\\
\frac{m-2}{3}2^k+\j{k} &amp; &amp; \quad\mbox{if}\quad m \equiv 2 \pmod 3.
\end{array} \right.
$$
\label{smallest}
\end{Lemma}

\begin{proof}
Suppose $m\equiv 0 \pmod 3$ and $\D \ell = \frac{m}{3}2^k$.  Then
$$\lrfloor{\frac{3\ell + 1}{2^k}} =
\lrfloor{\frac{3\lrpar{\frac{m}{3}2^k} + 1}{2^k}}
 = \lrfloor{\frac{m2^k}{2^k}+\frac{1}{2^k}} = m,$$
and no smaller
value of $\ell$ yields
$m$ since the numerators differ by multiples of three.

If $m \equiv 1 \pmod 3$ and $\D \ell = \frac{m-1}{3}2^k+\j{k-1}$,
then
\begin{eqnarray*}
\lrfloor{\frac{3\ell + 1}{2^k}} 
&amp;=&amp; \lrfloor{\frac{3\lrpar{\frac{m-1}{3}2^k+\j{k-1}} + 1}{2^k}}\\
&amp;=&amp;
\lrfloor{\frac{(m-1)2^k+3\lrpar{\frac{2^k+(-1)^{k-1}}{3}}+1}{2^k}}\\
&amp;=&amp; \lrfloor{\frac{(m-1)2^k+2^k+(-1)^{k-1}+1}{2^k}}\\
&amp;=&amp; m, \ \ \mbox{if $k \geq 2$,}
\end{eqnarray*}
 and no
smaller value of
$\ell$ yields $m$.

If $m \equiv 2 \pmod 3$ and $\D \ell = \frac{m-2}{3}2^k+\j{k}$, then
\begin{eqnarray*}
\lrfloor{\frac{3\ell + 1}{2^k}}
&amp;=&amp; \lrfloor{\frac{3\lrpar{\frac{m-2}{3}2^k+\j{k}} + 1}{2^k}}\\
&amp;=&amp;
\lrfloor{\frac{(m-2)2^k+3\lrpar{\frac{2^{k+1}+(-1)^k}{3}}+1}{2^k}}\\
&amp;=&amp; \lrfloor{\frac{(m-2)2^k+2^{k+1}+(-1)^k+1}{2^k}}\\
&amp;=&amp; m,
\end{eqnarray*}
 and no smaller value of $\ell$ yields $m$.

\end{proof}

\begin{Lemma}
\label{2klemma}
For any positive integer $k$, $\D \j{k-1} + \j{k} = 2^k.$
\end{Lemma}

\begin{proof}
Immediate from (\ref{Eq4a}).
\end{proof}


\begin{Lemma}
\label{sum}
For any positive integer $k$, $$\D
\sum_{v=0}^{2^k-1}\lrfloor{\frac{3v+1}{2^k}} = 2^k.$$
\end{Lemma}

\begin{proof}
The result is immediate if $k=1$.
If $k \geq 2$, then by Lemma~\ref{smallest}, $\j{k-1}$ is the
smallest value of $v$ for which $\D
\lrfloor{\frac{3v+1}{2^k}} = 1$ and $\j{k}$ is the smallest value of
$v$ for
which
$\D \lrfloor{\frac{3v+1}{2^k}} = 2$.  Thus

\begin{eqnarray*}
\sum_{v=0}^{2^k-1}\lrfloor{\frac{3v+1}{2^k}}
&amp;=&amp;  0\times \j{k-1} +
1\times[(\j{k}-1)-(\j{k-1}-1)]+
2\times[{(2^k-1)-(\j{k}-1)}]\\ 
&amp;=&amp; \j{k} - \j{k-1} + 2(2^k-\j{k})\\
&amp;=&amp; 2^{k+1}-2^k \ \ \mbox{by Lemma~\ref{2klemma}}\\
&amp;=&amp; 2^k~.
\end{eqnarray*}
\end{proof}

\begin{Theorem}
\label{Nkform}
Let $n = 2^kq+r$, where $q$ is a nonnegative integer and $0\leq
r&lt;2^k.$  
Then
\begin{equation}
\label{Nkformula2}
N_k^{\#}(n) = \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) -
2^k)+tail(n)
\end{equation}
where 
\begin{equation}
\label{Nktail}
tail(n) = \left\{ 
\begin{array}
{l@{\ \ \mbox{if}\quad}l}
3qr &amp; 0\leq r\leq \j{k-1} \\
3qr+(r-\j{k-1}) &amp; \j{k-1}&lt; r\leq\j{k} \\
(3q+2)r-2^k &amp; \j{k} &lt; r&lt;2^k.
\end{array}
\right.
\end{equation}

\end{Theorem}
\begin{proof}
To analyze the sum $$\D \Nk = \sum_{\ell =
0}^{n-1}\lrfloor{\frac{3\ell+1}{2^k}}$$ we let
$\ell = 2^ku+v$, where $0 \leq v &lt; 2^k$.  Then
$$\lrfloor{\frac{3\ell +1}{2^k}} =
\lrfloor{\frac{3(2^ku+v)+1}{2^k}} =
\lrfloor{\frac{2^k(3u)}{2^k}+\frac{3v+1}{2^k}}
= 3u + \lrfloor{\frac{3v+1}{2^k}}.$$
\nopagebreak
Thus 
\begin{eqnarray*}
\sum_{\ell = 0}^{2^kq-1}\lrfloor{\frac{3\ell +1}{2^k}}
&amp;=&amp;
\sum_{u=0}^{q-1}\sum_{v=0}^{2^k-1}\lrpar{3u+\lrfloor{\frac{3v+1}{2^k}}}\\
&amp;=&amp;
\sum_{u=0}^{q-1}\lrpar{(3u)2^k+\sum_{v=0}^{2^k-1}\lrfloor{\frac{3v+1}{2^k}}}\\
&amp;=&amp; \sum_{u=0}^{q-1}((3u)2^k+2^k)  \ \ \  \ \mbox{by
Lemma~\ref{sum}}\\  
&amp;=&amp; 2^k\sum_{u=0}^{q-1}(3u+1)\\
&amp;=&amp; 2^k\lrpar{3\lrpar{\frac{(q-1)q}{2}}+q}\\
&amp;=&amp; 2^kq\lrpar{3\lrpar{\frac{n-r-2^k}{2^{k+1}}}+1}\\
&amp;=&amp; \lrpar{\frac{q}{2}}(3(n-r-2^k)+2^{k+1})\\
&amp;=&amp; \lrpar{\frac{n-r}{2^{k+1}}}(3(n-r)-2^k).
\end{eqnarray*}

If $r=0$, we have our result.  If $r&gt;0$ and $k=1$, then $r=1$ and we
have
one extra term in our sum, namely, $$\D
\lrfloor{\frac{3(2q)+1}{2}}=3q$$ and again
we have our result since $r=1$.  If $r&gt;0$ and $k \geq 2$, then 
by Lemma~\ref{smallest}, $2^kq$ is the smallest value of $\ell$ for
which $\D
\lrfloor{\frac{3\ell +1}{2^k}} = 3q$,
$2^kq+\j{k-1}$ is the smallest value of $\ell$ for which
$$\D \lrfloor{\frac{3\ell +1}{2^k}}=3q+1,$$ and
$2^kq+\j{k}$ is the smallest value of $\ell$ for which
$$\D \lrfloor{\frac{3\ell +1}{2^k}}=3q+2.$$
Hence
$$\sum_{\ell = 2^kq}^{2^kq+r-1}\lrfloor{\frac{3\ell +1}{2^k}} =
\left\{ \begin{array}{lcl}
\D 3qr &amp; &amp; \quad\mbox{if  }\quad r \leq \j{k-1}\\
\D 3q\j{k-1}+(3q+1)(r-\j{k-1}) &amp; &amp; \quad\mbox{if  } \j{k-1} &lt; r \leq
\j{k}\\
\D 3q\j{k-1}+(3q+1)(\j{k}-\j{k-1})+(3q+2)(r-\j{k}) &amp; &amp; \quad\mbox{if 
}
\j{k} &lt; r &lt; 2^k.
\end{array} \right.$$

So, if $n = 2^kq+r$ where $0 \leq r &lt; 2^k$,
\begin{eqnarray*}
\Nk
&amp;=&amp; \sum_{\ell = 0}^{n-1}\lrfloor{\frac{3\ell +1}{2^k}}\\
&amp;=&amp; \sum_{\ell = 0}^{2^kq-1}\lrfloor{\frac{3\ell +1}{2^k}}
+ \sum_{\ell = 2^kq}^{2^kq+r-1}\lrfloor{\frac{3\ell +1}{2^k}}\\
&amp;=&amp; \lrpar{\frac{n-r}{2^{k+1}}}(3(n-r)-2^k) + tail(n),
\end{eqnarray*}

where
$$tail(n) = \left\{ \begin{array}{lcl}
\D 3qr &amp; &amp; \quad\mbox{if  }\quad r \leq \j{k-1}\\
\D 3q\j{k-1}+(3q+1)(r-\j{k-1}) &amp; &amp; \quad\mbox{if  } \j{k-1} &lt; r \leq
\j{k}\\
\D 3q\j{k-1}+(3q+1)(\j{k}-\j{k-1})+(3q+2)(r-\j{k}) &amp; &amp; \quad\mbox{if 
}
\j{k} &lt; r &lt; 2^k.\\
\end{array} \right.$$

The second expression in $tail(n)$ is clearly equal to
$3qr+r-\j{k-1}$.  For the
third expression, we have
\begin{eqnarray*}
3q\j{k-1}+(3q+1)(\j{k}-\j{k-1})+(3q+2)(r-\j{k})
&amp;=&amp; 3qr+\j{k}-\j{k-1}+2r-2\j{k}\\
&amp;=&amp; (3q+2)r-2^k \ \ \mbox{by Lemma~\ref{2klemma}.}
\end{eqnarray*}
\end{proof}

\begin{Theorem}
\label{Dkform}
Let $n = 2^kq+r$ where $q$ is a nonnegative integer and $0\leq
r&lt;2^k.$  
Then we have 
\begin{equation}
\label{Dkformula2}
D_k^{\#}(n) = \left\{ 
\begin{array}
{l@{\ \ \mbox{if}\quad}l}
\D\left(\frac{n-r}{2^{k+1}}\right)(3(n+r)-2^k) &amp; 0\leq r \leq 2^{k-1}
\\
\D\left(\frac{n-(2^k-r)}{2^{k+1}}\right)(3(n-r)+2^{k+1}) &amp; 2^{k-1} &lt;
r &lt; 2^{k}.\\ 
\end{array}
\right.
\end{equation}
\end{Theorem}

\begin{proof}
We may write
$$D_k^{\#}(n) = \sum_{\ell =
0}^{2n-1}\lrfloor{\frac{\ell}{2^k}} -
\sum_{\ell = 0}^{n-1}\lrfloor{\frac{\ell}{2^k}}.$$  In both sums,
$$\D \lrfloor{\frac{\ell}{2^k}} = s\,,$$
if $2^{k}s \leq \ell &lt; 2^{k}(s+1)$,
so
if $n = 2^kq+r$, where $0 &lt; r \leq 2^k$, we have

\begin{eqnarray*}
\sum_{\ell = 0}^{n-1}\lrfloor{\frac{\ell}{2^k}}
&amp;=&amp; 2^k [1+2+ \cdots + q-1] + qr \\
&amp;=&amp; q\lrpar{\frac{n+r-2^k}{2}}.
\end{eqnarray*}

If $0&lt;r \leq 2^{k-1}$, then $2n-1 = 2^k(2q)+(2r-1)$, which means

\begin{eqnarray*}
\sum_{\ell = 0}^{2n-1}\lrfloor{\frac{\ell}{2^k}}
&amp;=&amp; 2^k[1+2+\cdots + (2q-1)]+(2r-1+1)(2q)\\
&amp;=&amp; q(2n+2r-2^k).
\end{eqnarray*}

Hence in this case

\begin{eqnarray*}
D_k^{\#}(n)
&amp;=&amp; \sum_{\ell = 0}^{n-1}\lrfloor{\frac{n+\ell}{2^k}}\\
&amp;=&amp; \sum_{\ell =0}^{2n-1}\lrfloor{\frac{\ell}{2^k}}-\sum_{\ell =
0}^{n-1}\lrfloor{\frac{\ell}{2^k}}\\
&amp;=&amp; q(2n+2r-2^k) - q\lrpar{\frac{n+r-2^k}{2}}\\
&amp;=&amp; \lrpar{\frac{n-r}{2^{k+1}}}(3(n+r)-2^k).
\end{eqnarray*}

If $2^{k-1} &lt; r \leq 2^k$, say, $r = 2^{k-1}+s$ where $0 &lt; s \leq
2^{k-1}$, then

\begin{eqnarray*}
2n-1
&amp;=&amp; 2(2^kq+r)-1\\
&amp;=&amp; 2^k(2q)+2(2^{k-1}+s)-1\\
&amp;=&amp; 2^k(2q+1)+2s-1.
\end{eqnarray*}

Thus

\begin{eqnarray*}
\sum_{\ell = 0}^{2n-1}\lrfloor{\frac{\ell}{2^k}}
&amp;=&amp; 2^k[1+2+\cdots + 2q]+(2s-1+1)(2q+1)\\
&amp;=&amp; (2q+1)(n+r-2^k).
\end{eqnarray*}

So in this case

\begin{eqnarray*}
D_k^{\#}(n)
&amp;=&amp; \sum_{\ell = 0}^{n-1}\lrfloor{\frac{n+\ell}{2^k}}\\
&amp;=&amp; \sum_{\ell = 0}^{2n-1}\lrfloor{\frac{\ell}{2^k}}-\sum_{\ell
=0}^{n-1}\lrfloor{\frac{\ell}{2^k}}\\
&amp;=&amp; (2q+1)(n+r-2^k) - q\lrpar{\frac{n+r-2^k}{2}}\\
&amp;=&amp; \lrpar{\frac{n+r-2^k}{2^{k+1}}}(3(n-r)+2^{k+1}).
\end{eqnarray*}

The reader will note that in the statement of the theorem we have
separated the cases
according as $0 \leq r \leq 2^{k-1}$ and $2^{k-1} &lt; r &lt; 2^k$, whereas
in the proof the cases
are $0 &lt; r \leq 2^{k-1}$ and $2^{k-1} &lt; r \leq 2^k$.  However, these
are equivalent since
$\D \frac{n-0}{2^{k+1}}(3(n+0)-2^k) =
\frac{n-(2^k-2^k)}{2^{k+1}}(3(n-2^k)+2^{k+1})$.
\end{proof}


\end{section}

\begin{section}{$A(\j{m})$ is odd}
Now that we have closed formulas for $\Nk$ and $\Dk$ we can proceed
to prove that
$A(\j{m})$ is odd for all Jacobsthal numbers $\j{m}$.


\begin{Theorem}
\label{thebigthm}
For all positive integers $m$, $A(\j{m})$ is odd.
\end{Theorem}

\begin{proof}
The proof simply involves substituting $\j{m}$ into 
(\ref{Nkformula2}) and (\ref{Dkformula2}) and showing that 
$N_k^{\#}(\j{m}) = D_k^{\#}(\j{m})$
for all $k$.  This implies that $N^{\#}(\j{m}) = D^{\#}(\j{m})$, 
and so the number of factors of 2 in $A(\j{m})$ is zero.  
Our theorem is then proved.

We break the proof into two cases, based on whether the parity of $k$
is equal
to the parity of $m$.

\begin{itemize}
\item{{\bf Case 1:}  The parity of $m$ equals the parity of $k$.}
Then
\begin{eqnarray*}
2^k(\j{m-k}-1)+\j{k}
&amp;=&amp;
2^k\lrpar{\frac{2^{m-k+1}+(-1)^{m-k}}{3}-1}+\frac{2^{k+1}+(-1)^k}{3}\\
&amp;=&amp; \frac{2^{m+1}+2^k-3\cdot 2^k+2^{k+1}+(-1)^k}{3} \ \ \ \
\mbox{since $(-1)^{m-k}=1$}\\
&amp;=&amp; \frac{2^{m+1}+(-1)^m}{3} \ \ \mbox{since $(-1)^k = (-1)^m$}\\
&amp;=&amp; \j{m}
\end{eqnarray*}

Thus, in the notation of Theorems~\ref{Nkform} and \ref{Dkform},
$q=\j{m-k}-1$ and $r=\j{k}$.  We now calculate
$\Nkjm$ and $\Dkjm$ using Theorems~\ref{Nkform} and \ref{Dkform}.

\begin{eqnarray*}
N_k^{\#}(\j{m})
&amp;=&amp;\lrpar{ \frac{\j{m}-\j{k}}{2^{k+1}}} \lrpar{ 3(\j{m} - \j{k})-2^k 
} \\
&amp; &amp;\ \ \ {} + 3(\j{m-k}-1)\j{k} + (\j{k} - \j{k-1}) \\
&amp;=&amp;\frac{1}{2^{k+1}}\lrpar{
\jac{m}-\jac{k}}\lrpar{3\lrpar{\jac{m}-\jac{k}}-2^k}  \\
&amp; &amp;\ \ \ {} + (3\j{m-k} -1)\j{k} - 2^k \ \ \mbox{by
Lemma~\ref{2klemma}}\\
&amp;=&amp;\frac{1}{3\cdot 2^{k+1}}\lrpar{ 2^{m+1}-2^{k+1} }\lrpar{
2^{m+1}-2^{k+1}-2^k  }  \\
&amp; &amp;\ \ \ {} + \lrpar{3\lrpar{ \jac{m-k}} -1 }\lrpar{\jac{k}}-2^k \ \
\mbox{since $(-1)^m = (-1)^k$}\\
&amp;=&amp;\frac{1}{3}\lrpar{2^{2m-k+1}-2^{m+2}+2^{k+1}-2^{m}+2^k}\\
&amp; &amp;\ \ \ {} +\frac{1}{3}(2^{m-k+1}(2^{k+1}+(-1)^k)-3\cdot 2^k)  \ \
\mbox{since $(-1)^{m-k}=1$}\\
&amp;=&amp;\frac{1}{3}\lrpar{2^{2m-k+1}-2^{m}+(-1)^k2^{m-k+1}} 
\end{eqnarray*}
after much simplification.  Next,
we calculate $D_k^{\#}(\j{m})$, recalling that
$2^{k-1} &lt; r = \j{k} &lt; 2^k.$

\begin{eqnarray*}
D_k^{\#}(\j{m})
&amp;=&amp; \frac{ \lrpar{\j{m}-2^k+\j{k}  } 
}{2^{k+1}}\lrpar{3(\j{m}-\j{k})+2^{k+1}  } \\
&amp;=&amp; \frac{1}{2^{k+1}}\lrpar{ \jac{m} + \jac{k} - 2^k}
                     \lrpar{ 3 \lrpar{ \jac{m} - \jac{k} } + 2^{k+1}}
\\
&amp;=&amp; \frac{1}{3\cdot2^{k+1}}\lrpar{ 2^{m+1} +2^{k+1} +2(-1)^k -3\cdot
2^k  }
                           \lrpar{ 2^{m+1} - 2^{k+1} + 2^{k+1}  } \ \
\mbox{since $(-1)^m = (-1)^k$}\\
&amp;=&amp; \frac{1}{3}\lrpar{ 2^{2m-k+1} + 2^{m+1} + 2^{m-k+1}(-1)^k -3\cdot
2^{m} }\\
&amp;=&amp; \frac{1}{3}\lrpar{ 2^{2m-k+1} - 2^{m} + (-1)^k2^{m-k+1}}
\end{eqnarray*}
after simplification.
We see that
$N_k^{\#}(\j{m})=D_k^{\#}(\j{m})$.

\bigskip
\item{{\bf Case 2:}  The parity of $m$ is not equal to the parity of
$k$.}
Then
\begin{eqnarray*}
2^k(\j{m-k})+\j{k-1}
&amp;=&amp; 2^k\lrpar{\jac{m-k}}+\frac{2^k+(-1)^{k-1}}{3}\\
&amp;=&amp; \frac{2^{m+1}-2^k+2^k+(-1)^{k-1}}{3}\\
&amp;=&amp; \j{m}.
\end{eqnarray*}

Thus, in the notation of Theorems~\ref{Nkform} and \ref{Dkform},
$q=\j{m-k}$ and $r=\j{k-1}$.  We now calculate
$\Nkjm$ and $\Dkjm$ using Theorems~\ref{Nkform} and \ref{Dkform}.



\begin{eqnarray*}
N_k^{\#}(\j{m})
&amp;=&amp;\lrpar{ \frac{\j{m}-\j{k-1}}{2^{k+1}}} \lrpar{ 3(\j{m} -
\j{k-1})-2^k  } \\
&amp; &amp;\ \ \ {} + 3\j{m-k}\j{k-1} \\
&amp;=&amp;\frac{1}{2^{k+1}}\lrpar{ \jac{m}-\frac{2^k+(-1)^{k-1}}{3} }\lrpar{
3\lrpar{\jac{m}-\frac{2^k+(-1)^{k-1}}{3}}-2^k  }  \\
&amp; &amp;\ \ \ {} + 3\lrpar{ \jac{m-k}}\lrpar{\frac{2^k+(-1)^{k-1}}{3}}\\
&amp;=&amp;\frac{1}{3\cdot 2^{k+1}}\lrpar{ 2^{m+1}-2^{k} }\lrpar{
2^{m+1}-2\cdot 2^{k}  }  \\
&amp; &amp;\ \ \ {} + \frac{1}{3}((2^{m-k+1} -1)(2^{k}+(-1)^{k-1})) \ \
\mbox{since $(-1)^m = (-1)^{k-1}$ and $(-1)^{m-k}=-1$}\\
&amp;=&amp;\frac{1}{3}(2^{2m-k+1}-2^{m+1}-2^{m}+2^k+2^{m+1}-2^k+2^{m-k+1}(-1)^{k-1}+(-1)^k)
\\
&amp;=&amp;\frac{1}{3}(2^{2m-k+1}-2^{m}+2^{m-k+1}(-1)^{k-1}+(-1)^k) 
\end{eqnarray*}
after much simplification.
Again we find that $N_k^{\#}(\j{m})=D_k^{\#}(\j{m})$.

Now we calculate $D_k^{\#}(\j{m})$, recalling that
$0 &lt; r &lt; 2^{k-1}.$

\begin{eqnarray*}
D_k^{\#}(\j{m})
&amp;=&amp; \frac{ (\j{m}-\j{k-1}  )  }{2^{k+1}}(3(\j{m}+\j{k-1})-2^{k}  )
\\
&amp;=&amp; \frac{1}{2^{k+1}}\lrpar{ \jac{m} - \frac{2^k+(-1)^{k-1}}{3}}
                     \lrpar{ 3 \lrpar{ \jac{m} +
\frac{2^k+(-1)^{k-1}}{3} } - 2^{k}} \\
&amp;=&amp; \frac{1}{3\cdot 2^{k+1}} (2^{m+1} -2^{k} )
                           ( 2^{m+1} + 2(-1)^{k-1} ) \ \ \mbox{since
$(-1)^m = (-1)^{k-1}$}\\
&amp;=&amp; \frac{1}{3}(2^{2m-k+1}-2^{m}+2^{m-k+1}(-1)^{k-1}+(-1)^k) 
\end{eqnarray*}
after simplification.  Again we find that
$N_k^{\#}(\j{m})=D_k^{\#}(\j{m})$.

\end{itemize}

This completes the proof that $A(\j{m})$ is odd for all Jacobsthal
numbers
$\j{m}.$

\end{proof} 

\end{section}

\begin{section}{The Converse}

We now prove the converse to Theorem~\ref{thebigthm}.  That is, we
will prove
that $A(n)$ is even if $n$ is not a Jacobsthal number.  As a guide in
how to proceed, 
we include a table of values for $N_k^{\#}(n)$ and $D_k^{\#}(n)$ for
small
values of $n$ and $k$.  This table suggests that $N_k^{\#}(n) \geq
D_k^{\#}(n)$ for all
positive integers $n$ and $k$.
It also suggests that for each value of $n$, there is at least one
value of $k$
for which $N_k^{\#}(n)$ is strictly greater than $D_k^{\#}(n)$ except
when $n$ is
a Jacobsthal number. 
(The rows that begin with a Jacobsthal number are indicated in
bold-face.)

\bigskip
 
\footnotesize

\noindent \begin{tabular}{r|rr|rr|rr|rr|rr|rrr}
$n$
&amp;$N_1^{\#}(n)$&amp;$D_1^{\#}(n)$&amp;$N_2^{\#}(n)$&amp;$D_2^{\#}(n)$&amp;$N_3^{\#}(n)$&amp;$D_3^{\#}(n)$&amp;$N_4^{\#}(n)$&amp;$D_4^{\#}(n)$&amp;$N_5^{\#}(n)$&amp;$D_5^{\#}(n)$&amp;$N_6^{\#}(n)$&amp;$D_6^{\#}(n)$&amp;\\

\hline
\bf{1}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;  
\bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;  
\bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   \\
2   &amp;   2   &amp;   2   &amp;   1   &amp;   0   &amp;   0   &amp;   0   &amp;   0   &amp;   0   &amp;
  0   &amp;   0   &amp;   0   &amp;   0   \\
\bf{3}   &amp;   \bf{5}   &amp;   \bf{5}   &amp;   \bf{2}   &amp;   \bf{2}   &amp;  
\bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;  
\bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   \\
4   &amp;   10   &amp;   10   &amp;   4   &amp;   4   &amp;   1   &amp;   0   &amp;   0   &amp;   0  
&amp;   0   &amp;   0   &amp;   0   &amp;   0   \\
\bf{5}   &amp;   \bf{16}   &amp;   \bf{16}   &amp;   \bf{7}   &amp;   \bf{7}   &amp;  
\bf{2}   &amp;   \bf{2}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   &amp;  
\bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   \\
6   &amp;   24   &amp;   24   &amp;   11   &amp;   10   &amp;   4   &amp;   4   &amp;   1   &amp;   0
  &amp;   0   &amp;   0   &amp;   0   &amp;   0   \\
7   &amp;   33   &amp;   33   &amp;   15   &amp;   15   &amp;   6   &amp;   6   &amp;   2   &amp;   0
  &amp;   0   &amp;   0   &amp;   0   &amp;   0   \\
8   &amp;   44   &amp;   44   &amp;   20   &amp;   20   &amp;   8   &amp;   8   &amp;   3   &amp;   0
  &amp;   0   &amp;   0   &amp;   0   &amp;   0   \\
9   &amp;   56   &amp;   56   &amp;   26   &amp;   26   &amp;   11   &amp;   11   &amp;   4   &amp;  
2   &amp;   0   &amp;   0   &amp;   0   &amp;   0   \\
10   &amp;   70   &amp;   70   &amp;   33   &amp;   32   &amp;   14   &amp;   14   &amp;   5   &amp; 
 4   &amp;   0   &amp;   0   &amp;   0   &amp;   0   \\
\bf{11}   &amp;   \bf{85}   &amp;   \bf{85}   &amp;   \bf{40}   &amp;   \bf{40}   &amp;  
\bf{17}   &amp;   \bf{17}   &amp;   \bf{6}   &amp;   \bf{6}   &amp;   \bf{0}   &amp;  
\bf{0}   &amp;   \bf{0}   &amp;   \bf{0}   \\
12   &amp;   102   &amp;   102   &amp;   48   &amp;   48   &amp;   21   &amp;   20   &amp;   8  
&amp;   8   &amp;   1   &amp;   0   &amp;   0   &amp;   0   \\
13   &amp;   120   &amp;   120   &amp;   57   &amp;   57   &amp;   25   &amp;   25   &amp;   10  
&amp;   10   &amp;   2   &amp;   0   &amp;   0   &amp;   0   \\
14   &amp;   140   &amp;   140   &amp;   67   &amp;   66   &amp;   30   &amp;   30   &amp;   12  
&amp;   12   &amp;   3   &amp;   0   &amp;   0   &amp;   0   \\
15   &amp;   161   &amp;   161   &amp;   77   &amp;   77   &amp;   35   &amp;   35   &amp;   14  
&amp;   14   &amp;   4   &amp;   0   &amp;   0   &amp;   0   \\
16   &amp;   184   &amp;   184   &amp;   88   &amp;   88   &amp;   40   &amp;   40   &amp;   16  
&amp;   16   &amp;   5   &amp;   0   &amp;   0   &amp;   0   \\
17   &amp;   208   &amp;   208   &amp;   100   &amp;   100   &amp;   46   &amp;   46   &amp;   19
  &amp;   19   &amp;   6   &amp;   2   &amp;   0   &amp;   0   \\
18   &amp;   234   &amp;   234   &amp;   113   &amp;   112   &amp;   52   &amp;   52   &amp;   22
  &amp;   22   &amp;   7   &amp;   4   &amp;   0   &amp;   0   \\
19   &amp;   261   &amp;   261   &amp;   126   &amp;   126   &amp;   58   &amp;   58   &amp;   25
  &amp;   25   &amp;   8   &amp;   6   &amp;   0   &amp;   0   \\
20   &amp;   290   &amp;   290   &amp;   140   &amp;   140   &amp;   65   &amp;   64   &amp;   28
  &amp;   28   &amp;   9   &amp;   8   &amp;   0   &amp;   0   \\
\bf{21}   &amp;   \bf{320}   &amp;   \bf{320}   &amp;   \bf{155}   &amp;   \bf{155}  
&amp;   \bf{72}  &amp;   \bf{72}   &amp;   \bf{31}   &amp;   \bf{31}   &amp;   \bf{10}   &amp;
  \bf{10}   &amp;   \bf{0}   &amp;   \bf{0}   \\
22   &amp;   352   &amp;   352   &amp;   171   &amp;   170   &amp;   80   &amp;   80   &amp;   35
  &amp;   34   &amp;   12   &amp;   12   &amp;   1   &amp;   0   \\
23   &amp;   385   &amp;   385   &amp;   187   &amp;   187   &amp;   88   &amp;   88   &amp;   39
  &amp;   37   &amp;   14   &amp;   14   &amp;   2   &amp;   0   \\
24   &amp;   420   &amp;   420   &amp;   204   &amp;   204   &amp;   96   &amp;   96   &amp;   43
  &amp;   40   &amp;   16   &amp;   16   &amp;   3   &amp;   0   \\
25   &amp;   456   &amp;   456   &amp;   222   &amp;   222   &amp;   105   &amp;   105   &amp;  
47   &amp;   45   &amp;   18   &amp;   18   &amp;   4   &amp;   0   
\end{tabular}

\smallskip
\centerline{Table 2:  Values for $N_k^{\#}(n)$ and $D_k^{\#}(n)$}
\bigskip

\normalsize

\noindent 
(We note in passing that the values of $N_1^{\#}(n)$ form sequence
\seqnum{A001859} in \cite{Sloane}.)

In order to prove the first assertion (that $\Nk \geq \Dk$), we
separate the functions
defined by the cases in equations~(\ref{Nkformula2}) and
(\ref{Dkformula2}) into individual
functions denoted by $N_k^{\# (1)}(n), N_k^{\# (2)}(n), \ldots ,
D_k^{\# (2)}(n)$.  That is, 

\begin{eqnarray*}      
N_k^{\# (1)}(n) &amp;:=&amp; \left( \frac{n-r}{2^{k+1}}\right) (3(n-r) -
2^k)+3qr\\
N_k^{\# (2)}(n) &amp;:=&amp; \left( \frac{n-r}{2^{k+1}}\right) (3(n-r) -
2^k)+3qr+(r-J_{k-1})\\
N_k^{\# (3)}(n) &amp;:=&amp; \left( \frac{n-r}{2^{k+1}}\right) (3(n-r) -
2^k)+(3q+2)r-2^k\\
D_k^{\# (1)}(n) &amp;:=&amp; \left( \frac{n-r}{2^{k+1}}\right) (3(n+r) -
2^k)\\
D_k^{\# (2)}(n) &amp;:=&amp; \left( \frac{n-(2^k-r)}{2^{k+1}}\right) (3(n-r)
+
2^{k+1})
\end{eqnarray*}

For a given value of $n$, $\Nk$ will equal $N_k^{\# (i)}(n)$ for some
$i \in \{ 1, 2, 3\}$
and $\Dk$ will be $D_k^{\# (j)}(n)$ for some $j \in \{ 1, 2\}$
depending on the value
of $r$.  Note that not all combinations of $i$ and $j$ are possible
(for example, there is no value of $n$ such that $i = 1$ and $j=2$). 
In
Lemmas~\ref{nk1=dk1} through \ref{nk3=dk2} we show that
$N_k^{\# (i)}(n) \geq D_k^{\# (j)}(n)$ for all possible combinations
of $i$ and $j$
(that correspond to some integer $n$)
which implies that $\Nk \geq \Dk$ for all positive integers $n$.



\bigskip
\begin{Lemma}
\label{nk1=dk1}
For all integers $n$ and $k$, $N_k^{\# (1)}(n) = D_k^{\# (1)}(n).$
\end{Lemma}

\begin{proof}
We first note that, in the notation of Theorem~\ref{Nkform},
$\displaystyle \frac{n-r}{2^{k+1}} =
\frac{2^kq}{2^{k+1}}
= \frac{q}{2}$.
Then
\begin{eqnarray*}
N_k^{\# (1)}(n)
&amp;=&amp; \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+3qr\\
&amp;=&amp; \left(\frac{n-r}{2^{k+1}}\right) \left (3(n-r) - 2^k+3qr\left(
\frac{2}{q}\right) \right) \ \ \mbox{since $\D
\frac{n-r}{2^{k+1}}=\frac{q}{2}$}\\
&amp;=&amp; \left(\frac{n-r}{2^{k+1}}\right) (3n+3r - 2^k)\\
&amp;=&amp; D_k^{\# (1)}(n).
\end{eqnarray*}
\end{proof}

\begin{Lemma}
For all integers $k$ and all integers $n$ such that $r &gt; \j{k-1}$ (in
the notation of
Theorem~\ref{Nkform}), $$N_k^{\# (2)}(n) &gt; D_k^{\# (1)}(n) .$$
\end{Lemma}

\begin{proof}
\begin{eqnarray*}
N_k^{\# (2)}(n)
&amp;=&amp; \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) -
2^k)+3qr+(r-J_{k-1})\\
&amp;&gt;&amp; \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+3qr \ \
\mbox{since $r &gt; \j{k-1}$}\\
&amp;=&amp; N_k^{\# (1)}(n)\\
&amp;=&amp; D_k^{\# (1)}(n) \ \ \mbox{ by Lemma~\ref{nk1=dk1}}.
\end{eqnarray*}
This proves our result.
\end{proof}


\begin{Lemma}
For all integers $k$ and all integers $n$ such that $r \leq \j{k}$
(in the notation of
Theorem~\ref{Nkform}), $$N_k^{\# (2)}(n) \geq D_k^{\# (2)}(n).$$
\end{Lemma}

\begin{proof}
We see that $r \leq \j{k} = 2^k - \j{k-1}$ by Lemma~\ref{2klemma}. 
Thus, 
$2^kq+r \leq 2^k(q+1)-\j{k-1}$.  This implies
$n \leq 2^k(q+1)-J_{k-1}$, so $2n-2^k(q+1) \leq n-J_{k-1}$.  Hence,

\begin{eqnarray*}
\displaystyle N_k^{\# (2)}(n)
&amp;=&amp; \left(\frac{n-r}{2^{k+1}}\right) (3(n-r) - 2^k)+3qr+(r-J_{k-1}) 
\\
&amp;=&amp; \frac{q}{2}(3(2^kq)-2^k)+3q(n-2^kq)+n-2^kq-J_{k-1}  \\
&amp;=&amp; q^2(-3(2^{k-1}))+q(-3(2^{k-1})+3n)+n-J_{k-1}   \\
&amp;\geq&amp; q^2(-3(2^{k-1}))+q(-3(2^{k-1})+3n)+2n-2^k(q+1)  \ \ \mbox{by
the above argument}\\
&amp;=&amp; \frac{2n-2^k-2^kq}{2^{k+1}}(3(2^kq)+2^{k+1})\\
&amp;=&amp; D_k^{\# (2)}(n).
\end{eqnarray*}
\end{proof}

\begin{Lemma}
\label{nk3=dk2}
For all positive integers $n$ and $k$, $N_k^{\# (3)}(n) = D_k^{\#
(2)}(n)$.
\end{Lemma}

\begin{proof}

\begin{eqnarray*}
N_k^{\# (3)}(n) &amp;=&amp;
\lrpar{\frac{n-r}{2^{k+1}}}(3(n-r)-2^k)+(3q+2)r-2^k\\
&amp;=&amp; \lrpar{\frac{q}{2}}(3(2^kq)-2^k)+3q(n-2^kq)+2(n-2^kq)-2^k\\
&amp;=&amp; \frac{n-2^k+n-2^kq}{2^k+1}(3(2^kq)+2^{k+1})\\
&amp;=&amp; D_k^{\# (2)}(n).
\end{eqnarray*}
\end{proof}

\begin{Remark}
\label{remark}
To summarize, Lemmas~\ref{nk1=dk1} through \ref{nk3=dk2} tell us that
for any positive
integer $n$, $$\Nk \geq \Dk.$$
\end{Remark}

For Propositions~\ref{firstprop} through \ref{lastprop} we make the
assumption that
$\j{\ell} &lt; n &lt; \j{\ell +1}$ for some positive integer $\ell$.


\begin{Prop}
\label{firstprop}
For $\ell$ and $n$, as given above, $\N{\ell +1}{n} = n - J_{\ell}$.
\end{Prop}

\begin{proof}
By Lemma~\ref{smallest},
\begin{eqnarray*}
\sum_{i=0}^{n-1}\lrfloor{\frac{3i+1}{2^{\ell+1}}}
&amp;=&amp; 0\times(\j{\ell}) + 1\times((n-1)-(\j{\ell}-1))\\
&amp;=&amp; n-\j{\ell}.
\end{eqnarray*}
\end{proof}

\begin{Prop}
\label{secondprop}
$D_k^{\#}(n) = 0$ if $n &lt; 2^{k-1}$.  In particular, $D_{\ell +
1}^{\#}(n)
= 0$ if $n &lt; 2^{\ell}$.
\end{Prop}

\begin{proof}
If $n &lt; 2^k$ then, in the notation of Theorem~\ref{Dkform}, $n=r$
and $q=0$, so by Theorem~\ref{Dkform}, $D_k^{\#}(n) = 0$.
\end{proof}

\begin{Prop}
\label{thirdprop}
$\D D^{\#}_{\ell +1}(n) = 2(n-2^{\ell})$ if $2^{\ell} \leq n &lt;
J_{\ell +1}$.
\end{Prop}

\begin{proof}
If $2^{\ell} \leq n &lt; J_{\ell +1}$ then, in the notation of
Theorem~\ref{Dkform},
$q=0$ and $r = n$.  Since $n \geq 2^{\ell}$,
we are in the second case of Theorem~\ref{Dkform} so
$$
D^{\#}_{\ell +1}(n)
= \frac{n-2^{\ell +1}+n}{2^{\ell +2}}(0+2^{\ell +2})\\
= 2(n-2^{\ell}).
$$
\end{proof} 

\begin{Prop}
\label{lastprop}
For $n$ and $\ell$ as given above, $2(n-2^{\ell}) &lt; n-\j{\ell}$.
\end{Prop}

\begin{proof}
We begin by showing that $\j{\ell +1}-2^{\ell} = 2^{\ell} -
\j{\ell}$.
We have
\begin{eqnarray*}
\j{\ell +1}-2^{\ell}
&amp;=&amp; \frac{2^{\ell+2}+(-1)^{\ell +1}}{3}-2^{\ell}\\
&amp;=&amp; 2^{\ell}-\jac{\ell}\\
&amp;=&amp; 2^{\ell}-\j{\ell},
\end{eqnarray*}
and hence
\begin{eqnarray*}
2(n-2^{\ell})
&amp;=&amp; n-2^{\ell}+n-2^{\ell}\\
&amp;&lt;&amp; n-2^{\ell}+\j{\ell +1}-2^{\ell}\\
&amp;=&amp; n-2^{\ell}+2^{\ell}-\j{\ell} \ \ \mbox{from the above
argument}\\
&amp;=&amp; n-\j{\ell}
\end{eqnarray*}
so we have our result.
\end{proof}

We are now ready to prove our theorem.

\begin{Theorem}
$A(n)$ is even if $n$ is not a Jacobsthal number.
\label{conversethm}
\end{Theorem}

\begin{proof}
Our goal is to show that there is some $k$ such that $\Nk$ is
strictly greater than
$\Dk$ since, by Remark~\ref{remark}, we have shown that $\Nk \geq
\Dk$ for all
positive integers $k$ and $n$.

Given $n$, not a Jacobsthal number, there exists a positive integer
$\ell$ such that
$\j{\ell} &lt; n &lt; \j{\ell + 1}$.  Then $N_{\ell +1}^{\#}(n) = n -
\j{\ell}$ by Proposition~\ref{firstprop},
and since $n &gt; \j{\ell}$, $N_{\ell +1}^{\#}(n) &gt; 0$.  On the other
hand, by
Proposition~\ref{secondprop}, if $n&lt; 2^{\ell}$, then $D_{\ell
+1}^{\#}(n)=0$.
If $2^{\ell} \leq n &lt; \j{\ell +1}$, then by
Proposition~\ref{thirdprop},
$D_{\ell +1}^{\#}(n) = 2(n-2^{\ell})$ which is strictly less than
$n - \j{\ell} = N_{\ell +1}^{\#}(n)$ by Proposition~\ref{lastprop}. 
Hence, in every case,
$N_{\ell +1}^{\#}(n)$ is strictly greater than $D_{\ell +1}^{\#}(n)$
so there is at least
one factor of two in $A(n)$ and we have our result.
\end{proof}

\end{section}


\begin{section}{A Closing Remark}
We close by noting that we can prove a stronger result than
Theorem~\ref{conversethm}.
If $J_{\ell} &lt; n &lt; J_{\ell +1}$, then
$$\N{\ell +1}{n} - \DD {\ell +1}{n} = \left\{ \begin{array}{lcl}
n-J_{\ell} &amp; \mbox{if} &amp;
J_{\ell} &lt; n \leq 2^{\ell}\\
J_{\ell +1} -n &amp; \mbox{if} &amp; 2^{\ell} \leq n &lt; J_{\ell +1}\\
\end{array}
\right.$$
by Propositions~\ref{firstprop}, \ref{secondprop}, \ref{thirdprop}
and Lemma~\ref{2klemma}.

Let $ord_2(n)$
be the
highest power of 2 that divides $n$.
By Remark~\ref{remark}, $\Nk - \Dk \geq 0$ for all $n$ and for all
$k$, so that
$$ord_2(A(n)) \geq \left\{ \begin{array}{lcl} n-J_{\ell} &amp; \mbox{if}
&amp;
J_{\ell} &lt; n \leq 2^{\ell}\\
J_{\ell +1} -n &amp; \mbox{if} &amp; 2^{\ell} \leq n &lt; J_{\ell +1}\\
\end{array},
\right.$$
which strengthens Theorem~\ref{conversethm}.  

Finally, we see that $ord_2(A(2^{\ell})) = J_{\ell -1}$ since, 
for all $k &lt; \ell + 1, \Nkl = N_k^{\# (1)}(2^{\ell}) = D_k^{\#
(1)}(2^{\ell}) = \Dkl$, and
$2^{\ell}-J_{\ell} = J_{\ell +1}-2^{\ell} = J_{\ell - 1}$.
So, for example, we know that $A(2^{10})$ is divisible by $2^{J_9}$,
which equals $2^{341}$, 
and that $A(2^{10})$ is not divisible by $2^{342}.$




\end{section}

\begin{section}{Acknowledgements}
The authors gratefully acknowledge
the excellent technical help
of Robert Schumacher 
in the preparation of this document.

\end{section}

\begin{thebibliography}{99}

\bibitem{Bressoud}  D. M. Bressoud,
``Proofs and Confirmations:  The story of the alternating sign
matrix
conjecture'',
Cambridge University Press,
1999.

\bibitem{notices}   D. M. Bressoud and J. Propp,
How the Alternating Sign Matrix Conjecture Was Solved,
\emph{Notices of the American Mathematical Society},
\textbf{46} (6) (1999), 637-646.


\bibitem{Horadam1}
A. F. Horadam,
Jacobsthal Representation Numbers,
\emph{Fibonacci Quarterly}, \textbf{34} (1) (1996), 40-53.

\bibitem{Horadam2}
A. F. Horadam,
Jacobsthal Representation Polynomials,
\emph{Fibonacci Quarterly}, \textbf{35} (2) (1997), 137-148.

\bibitem{Horadam3}
A. F. Horadam,
Rodriques' Formulas for Jacobsthal-Type Polynomials,
\emph{Fibonacci Quarterly}, \textbf{35} (4) (1997), 361-370.

\bibitem{Horadam4}
A. F. Horadam and P. Filipponi,
Derivative Sequences of Jacobsthal and Jacobsthal-Lucas Polynomials,
\emph{Fibonacci Quarterly}, \textbf{35} (4) (1997), 352-357.


\bibitem{Long}  C. T. Long,
``Elementary Introduction to Number Theory'', 3rd edition,
Waveland Press, Inc., Prospect Heights, IL,
1995.

\bibitem{Sloane} N. J. A. Sloane,
The On-Line Encyclopedia of Integer Sequences.
Published electronically at
\htmladdnormallink{http://www.research.att.com/$\sim
$njas/sequences/}{http://www.research.att.com/~njas/sequences/}.
    
\bibitem{Tucker}  A. Tucker,
``Applied Combinatorics'',  3rd edition,
John Wiley \&amp; Sons, 
1995.


\end{thebibliography}

\vspace*{+.5in}
\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
{\small
(Concerned with sequences
\htmladdnormallink{A001045}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001045},
\htmladdnormallink{A001859}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=001859}
and
\htmladdnormallink{A005130}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=005130}.)
}

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Received Jan. 13, 2000;
published in Journal of Integer Sequences June 1, 2000.

\centerline{\rule{6.5in}{.01in}}

\vspace*{+.1in}
\noindent
Return to \htmladdnormallink{Journal of Integer Sequences home
page}{http://www.
research.att.com/~njas/sequences/JIS/}.

\centerline{\rule{6.5in}{.01in}}



\end{document}

</pre></body></html>