\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Some $2$-adic Integers Related \\ \vskip .1in to the Odd Part of $2^e!$ } \vskip 1cm \large Donald M.\ Davis\\ Department of Mathematics\\ Lehigh University\\ Bethlehem, PA 18015 USA\\ \href{mailto:dmd1@lehigh.edu}{\tt dmd1@lehigh.edu} \\ \end{center} \vskip .2 in \begin{abstract} The odd part of $2^e!$ as $e\to\infty$ leads to a $2$-adic integer $z$. The bits of $z$ were publicized in OEIS sequence \seqnum{A359349}, where two conjectures were made, relevant to computing $z$. We prove both of those conjectures. A second $2$-adic integer, the limit of $((2^e-1)!!-1)/2^e$, plays a key role in one proof. \end{abstract} \def\on{\operatorname} \def\a{\alpha} \def\Si{\Sigma} \def\b{\beta} \def\ni{\noindent} \def\od{\operatorname{od}} \def\odprod{\on{odpr}} \def\uns{\on{uns}} \def\stab{\on{stab}} \def\Z{\mathbb{Z}} \def\sihat{\widehat{\sigma}} \section{Introduction}\label{intro} In \cite{MAA}, the author noted that the odd part of $2^e!$ and of $2^{e-1}!$ agree mod $2^e$, and so the 2-adic limit as $e$ approaches $\infty$ is a 2-adic integer, which we call $z$. In sequence \seqnum{A359349} of the {\it On-Line Encyclopedia of Integer Sequences} (OEIS), the author and Schoenfield publicized the sequence of bits of $z$ and made two conjectures. One involved a relationship between the bits of $z$ and some of the unstable bits in the odd part of $2^e!$, while the other leads to a more efficient way of computing $z$. In this paper we prove both conjectures and some generalizations. In this introductory section, we review the two conjectures, stating them as theorems. In Sections \ref{sec2} and \ref{sec3}, we prove generalizations of both. Let $\nu(n)$ denote the exponent of 2 in the prime factorization of $n$, and $\od(n)=2/2^{\nu(n)}$, the odd part of $n$. Then $\od(2^e!)=2^e!/2^{2^e-1}$. In Table 1 we tabulate the first 40 bits in the backward binary expansion (BBE) of $\od(2^e!)$ for $2\le e\le30$. The first 31 bits of row 30 of Table 1 are the first 31 bits of the BBE of the 2-adic integer $z$ defined above. For example, the binary expansion of $z$ ends \begin{equation} \cdots011010001011.\label{z12}\end{equation} In \seqnum{A359349}, a larger table (64 bits for $e\le40$) is presented. \begin{table}[H] \centering \begin{tabular}{r|l} $e$&\\ \hline 2&110$\ $0000000000000000000000000000000000000\\ 3&1101$\ $110010000000000000000000000000000000\\ 4&11010$\ $11101110111011100000110010000000000\\ 5&110100$\ $1011001110100011000001101010001001\\ 6&1101000$\ $000000001101000110100010110011110\\ 7&11010001$\ $10010101001010001010001101011100\\ 8&110100010$\ $0111100111001000110000010011101\\ 9&1101000101$\ $000110101110110000001011000011\\ 10&11010001011$\ $10101101100010111001010101001\\ 11&110100010110$\ $0010011111110101111010110111\\ 12&1101000101101$\ $110111110000001100111011011\\ 13&11010001011010$\ $11100001101100011101011000\\ 14&110100010110100$\ $1011001111011110110100001\\ 15&1101000101101000$\ $000011110100000100110000\\ 16&11010001011010001$\ $10000001011001001111011\\ 17&110100010110100010$\ $0101001000011101001001\\ 18&1101000101101000101$\ $011101001000000000010\\ 19&11010001011010001011$\ $00000101101001010101\\ 20&110100010110100010111$\ $1001101111101111101\\ 21&1101000101101000101110$\ $011011110000010111\\ 22&11010001011010001011101$\ $00100001101011100\\ 23&110100010110100010111011$\ $1101001111111011\\ 24&1101000101101000101110110$\ $111101110010100\\ 25&11010001011010001011101100$\ $10000001111101\\ 26&110100010110100010111011000$\ $0101001100111\\ 27&1101000101101000101110110001$\ $011101101100\\ 28&11010001011010001011101100011$\ $00000011011\\ 29&110100010110100010111011000111$\ $1001011000\\ 30&1101000101101000101110110001110$\ $011111001 \end{tabular} \caption{first 40 bits in BBE of $\od(2^e!)$.} \label{table} \end{table} Bits $0$ through $e$ of $\od(2^e!)$ are {\it stable}; they agree with those of $z$. The {\it unstable} bits of $\od(2^e!)$ are those in position $\ge e+1$; they appear to the right of the space in Table \ref{table}. Note that, for $e>d$, the first $d$ unstable bits of $\od(2^e!)$ occur in the same positions as the last $d$ stable bits of $\od(2^{e+d}!)$. The latter are the stable bits of $z$ in position $e+1$ through $e+d$. Let $\uns(e,d)$ and $\stab(e+1,d)$ denote the numbers whose BBE's are these sequences of $d$ bits. The following theorem is the first conjecture of \seqnum{A359349}. \begin{theorem}\label{thm1} There is a 2-adic integer $K$ such that, for all $d$ and $e>d$, we have $$\uns(e,d)+K\equiv \stab(e+1,d)\pmod{2^d}.$$ \end{theorem} \begin{example} The BBE of $K$ begins $1011011$. This will be seen in Example \ref{expl3}. The BBE's of $\uns(17,7)$ and $\stab(18,7)$ are $0101001$ and $1110110$, respectively. Note that the BBE of stab(18,7) is the 7 bits to the left of the space in line 24 of Table \ref{table}. We verify Theorem \ref{thm1} with $d=7$ and $e=17$ by reversing the order of the bits and checking the binary addition in Table \ref{addn}. \end{example} \begin{table}[h] \centering \begin{tabular}{c|r} $\uns(17,7)$&$\cdots1001010$\\ $K$&$\cdots1101101$\\ \hline $\stab(18,7)$&$\cdots0110111$ \end{tabular} \caption{Binary addition check.} \label{addn} \end{table} \bigskip This relationship between the stable and unstable parts is, at least, a curiosity. It could be useful in calculations. We will see in Section \ref{sec2} that the first $d$ bits of $K$ can be determined from $\od(2^d!)$ mod $2^d$ and $(2^d-1)!!$ mod $2^{2d}$. Computing $\uns(e,d)$ requires $\od(2^e!)$ mod $2^{e+d}$. The desired $\stab(e+1,d)$, which can be obtained as the sum of these, would, if computed directly, require $\od(2^{e+d}!)$ mod $2^{e+d}$, which is a much larger calculation, requiring the multiplication of much larger numbers. Let $\odprod(\ell,m)$ denote the product of all odd integers $j$ satisfying $\ell\le j\le m$, and let \begin{equation}\label{hdef}h(m)=\odprod(2^{m-1}+1,2^m-1).\end{equation} We begin with the following elementary proposition. \begin{proposition} For any $e\ge1$, we have $$\od(2^e!)=\prod_{m=2}^eh(m)^{e+1-m}.$$\label{hprop} \end{proposition} \begin{proof} Each factor $j$ of $h(m)$ occurs with coefficient $2^i$ for $0\le i\le e-m$ in $2^e!$. \end{proof} This yields a method of computing $\od(2^e!)$ mod $2^B$, reducing mod $2^B$ at each step. The following theorem, which is the second conjecture of \seqnum{A359349}, makes it more efficient. \begin{theorem}\label{thm2} If $2\le m-1\le B\le 3m-7$, and $d=2+\lfloor \frac{B-m}2\rfloor$, then $$h(m)\equiv \odprod(2^{m-1}+1,2^{m-1}+2^d-1)^{2^{m-1-d}}\pmod{2^B}.$$ \end{theorem} The advantage is that now $h(m)$ requires $2^{d-1}+m-2-d$ multiplications (always reducing mod $2^B$) compared with $2^{m-2}-1$ multiplications if using (\ref{hdef}). We compare computing $\od(2^{49}!)$ mod $2^{50}$ via Proposition \ref{hprop} and computing it using Theorem \ref{thm2}. In either case, we compute $h(m)$ for $m<19$ using (\ref{hdef}). In Table \ref{50} we list, for even values of $m$ between 20 and 44, the approximate number of multiplications required to compute $h(m)$ using (\ref{hdef}) (the {\bf Old} way) and using Theorem \ref{thm2} (the {\bf New} way). Note that $h(m)$ must then be raised to the $50-m$ power mod $2^{50}$. \renewcommand{\arraystretch}{1.2} \begin{table}[h] \centering \begin{tabular}{c|ccccccccccccc} $m$&$20$&$22$&$24$&$26$&$28$&$30$&$32$&$34$&$36$&$38$&$40$&$42$&$44$\\ $d$&$17$&$16$&$15$&$14$&$13$&$12$&$11$&$10$&$9$&$8$&$7$&$6$&$5$\\ \hline Old&$2^{18}$&$2^{20}$&$2^{22}$&$2^{24}$&$2^{26}$&$2^{28}$&$2^{30}$&$2^{32}$&$2^{34}$&$2^{36}$&$2^{38}$&$2^{40}$&$2^{42}$\\ New&$2^{16}$&$2^{15}$&$2^{14}$&$2^{13}$&$2^{12}$&$2^{11}$&$2^{10}$&$2^9$&$2^8$&$2^7$&$2^6$&$2^5$&$2^4$ \end{tabular} \caption{Two ways of computing $\od(2^{49}!)$ mod $2^{50}$.} \label{50} \end{table} \bigskip In preliminary discussion, Schoenfield \seqnum{A359349} wrote ``If the conjecture can be proved, then I think I could compute the first 105 terms (of $z$) with a program that would take maybe a few days to run.'' \section{A formula for the 2-adic integer $K$ in Theorem \ref{thm1}}\label{sec2} In this section, we prove Theorem \ref{thm1} and give a formula for the 2-adic integer $K$ that occurs in it. We begin by reviewing the proof \cite{MAA} of existence of the 2-adic integer $z$, as some of the ingredients will be useful later. \begin{lemma} \label{bij} Let $I_e=\{i:2^{e-1}0}2^{je}\sihat_j(S_e)\equiv 2^{e}\sihat_1(S_e)\equiv0\pmod{2^{2e}}.$$ \end{proof} Let $(2^e-1)!!=\odprod(1,2^e-1)$. \begin{corollary}\label{wcor} If $e\ge2$, then $\dfrac{(2^e-1)!!-1}{2^e}\equiv\dfrac{(2^{e+1}-1)!!-1}{2^{e+1}} \pmod{2^{e-1}}$.\end{corollary} \begin{proof} By Lemma \ref{Gauss}, the two expressions are odd integers. We show that their ratio is $\equiv1$ (mod $2^{e-1}$). Let $A=(2^e-1)!!-1$. By Lemma \ref{Gauss}, $A=2^eu$ with $u$ odd. By Proposition \ref{weak1}, $\odprod(2^e+1,2^{e+1}-1)=A+1+k2^{2e}$ for some integer $k$. The desired ratio is \begin{align*} \frac{(A+1)(A+1+k2^{2e})-1}{2A} & = \frac{A^2+2A+(A+1)k2^{2e}}{2A} \\ & =2^{e-1}u+1+\frac{(A+1)k2^{2e}}{2^{e+1}u}\equiv1\pmod{2^{e-1}}. \end{align*} \end{proof} \begin{definition} We define $w$ to be the 2-adic integer which is congruent to $\dfrac{(2^e-1)!!-1}{2^e} \pmod {2^{e-1}}$ for all $e$.\label{wdef}\end{definition} This is well-defined by Corollary \ref{wcor}. One can compute that the binary expansion of $w$ ends $\cdots 1001110011001$. We have introduced two 2-adic integers, $z$ and $w$. The next result shows that their product equals the difference between the unstable parts of consecutive rows of Table \ref{table} in a metastable range. \begin{theorem}\label{prod}If $e\ge3$, then $$\frac{\od(2^e!)-\od(2^{e-1}!)}{2^e}\equiv zw\pmod{2^{e-1}}.$$\end{theorem} \begin{proof} By Lemma \ref{bij}, we have $(2^e-1)!!=\dfrac{\od(2^e!)}{\od(2^{e-1}!)}$. Thus $$\frac{(2^e-1)!!-1}{2^e}=\frac{\od(2^e!)-\od(2^{e-1}!)}{2^e\od(2^{e-1}!)},$$ so $$\frac{(2^e-1)!!-1}{2^e}\cdot\od(2^{e-1}!)=\frac{\od(2^e!)-\od(2^{e-1}!)}{2^e}.$$ The result follows now from Corollary \ref{zdef} and Definition \ref{wdef}. \end{proof} \begin{example} \label{expl2} The binary expansion of $zw$ ends $\cdots011000010011$, obtained by multiplying the binary numbers in (\ref{z12}) and just after Definition \ref{wdef}. The numbers $\od(2^7!)$ and $\od(2^6!)$ agree mod $2^7$. From Table \ref{table}, beginning in the $2^7$ position, the binary expansion of $\od(2^7!)$ ends $\cdots 1010011$, while that of $\od(2^6!)$ ends with eight 0's. The difference agrees with $zw$ mod $2^6$.\end{example} We now state the main theorem of this section. \begin{theorem} \label{Kthm} The $2$-adic integer $K$ of Theorem \ref{thm1} equals $\ {-zw}$. \end{theorem} \begin{proof}[Proof of Theorems \ref{thm1} and \ref{Kthm}.] The difference $\stab(e+1,d)-\uns(e,d)$, as described in the paragraph preceding Theorem \ref{thm1}, equals $\dfrac{\od(2^{e+d}!)-\od(2^e!)}{2^{e+1}}$ (mod $2^d$). We have \begin{align*} \frac{\od(2^{e+d}!)-\od(2^e!)}{2^{e+1}} & = \sum_{i=1}^d\frac{\od(2^{e+i}!)-\od(2^{e+i-1}!)}{2^{e+1}} \\ & = \sum_{i=1}^d2^{i-1}\frac{\od(2^{e+i}!)-\od(2^{e+i-1}!)}{2^{e+i}}\\ \end{align*} \begin{align*} & \equiv\sum_{i=1}^d2^{i-1}zw\pmod{2^e}\\ & \equiv\sum_{i=1}^\infty2^{i-1}zw\pmod{2^d}\\ & = -zw.\qedhere\end{align*} \end{proof} \begin{example} \label{expl3} The binary expansion of $-zw$ ends $\cdots010111101101$, since adding this to the $zw$ in Example \ref{expl2} equals 0. Add that to the binary number obtained by reversing the order of the first $12$ bits after the space on line $14$ of Table \ref{table}, and you obtain the binary number obtained by reversing the order of the last $12$ bits before the space on line $26$. This illustrates Theorem \ref{thm1} with $d=12$ and $e=14$.\end{example} \section{Proof of Theorem \ref{thm2}}\label{sec3} In this section, we prove Theorem \ref{thm2} and some mild generalizations. The bulk of our work is the following strengthening of Proposition \ref{weak1}, the proof of which appears later. \begin{theorem} \label{hard} With $S_e$ as defined in Lemma \ref{bij}, and $A$ any integer, if $e\ge2$, then $$\prod_{i\in S_e}(A2^e+i)\equiv\prod_{i\in S_e}i\pmod{2^{3e-1}}.$$ \end{theorem} \begin{corollary} \label{ABcor} For any integers $A$, $B$, $j$, and $e\ge2$, we have $$\prod_{i\in S_e}(A2^e+i)^{2^j}\equiv\prod_{i\in S_e}(B2^e+i)^{2^j}\pmod{2^{3e-1+j}}.$$ \end{corollary} \begin{proof} It is elementary that if $\a\equiv\b$ (mod $2t$), then $\a^2\equiv\b^2$ (mod $4t$). We apply this iteratively to Theorem \ref{hard}, and then both expressions in the corollary are congruent to $\prod i^{2^j}$.\end{proof} \begin{proof}[Proof of Theorem \ref{thm2}.] We write the conjectured congruences in succession, beginning \begin{align*} \odprod(2^{m-1}+1,2^m-1) & \equiv \odprod(2^{m-1}+1,2^{m-1}+2^{m-2}-1)^2\pmod {2^{3m-7}},\end{align*} then \begin{align*} \odprod(2^{m-1}+1,2^{m-1}+2^{m-2}-1)^2 &\equiv \odprod(2^{m-1}+1,2^{m-1}+2^{m-3}-1)^{2^2}\pmod{2^{3m-9}},\end{align*} with arbitrary entry \begin{align*} \odprod(2^{m-1}+1,2^{m-1}+2^{d+1}-1)^{2^{m-2-d}} \equiv&\odprod(2^{m-1}+1,2^{m-1}+2^d-1)^{2^{m-1-d}}\pmod{2^{2d+m-3}}. \end{align*} After canceling $\odprod(2^{m-1}+1,2^{m-1}+2^d-1)^{2^{m-2-d}}$, this becomes \begin{align*} & \odprod(2^{m-1}+2^d+1,2^{m-1}+2^{d+1}-1)^{2^{m-2-d}} \\ & \quad\quad \equiv \odprod(2^{m-1}+1,2^{m-1}+2^d-1)^{2^{m-2-d}}\pmod{2^{2d+m-3}}. \end{align*} We can restate this as $$\prod_{i\in S_d}(2^{m-1}+2^d+i)^{2^{m-2-d}}\equiv\prod_{i\in S_d}(2^{m-1}+i)^{2^{m-2-d}}\pmod{2^{2d+m-3}},$$ and this is a consequence of Corollary \ref{ABcor}. \end{proof} We prove the following two lemmas, from which Theorem \ref{hard} follows easily. \begin{lemma}\label{lem1} If $e\ge2$, then $\sihat_1(S_e)\equiv 2^{2e-2}\pmod{2^{2e-1}}$.\end{lemma} \begin{lemma}\label{lem2} If $e\ge2$, then $\sihat_2(S_e)\equiv2^{e-2}\pmod{2^{e-1}}$.\end{lemma} \begin{proof}[Proof of Theorem \ref{hard}.] We have $$\prod_{i\in S_e}(A2^e+i)-\prod_{i\in S_e}i=\sum_{j>0}(A2^e)^j\sihat_j(S_e)\equiv0\pmod{2^{3e-1}}$$ by Lemmas \ref{lem1} and \ref{lem2}, with the argument slightly different for the two parities of $A$. \end{proof} \begin{proof}[Proof of Lemma \ref{lem1}.] If $e\ge2$, then $$\sihat_1(S_e)=\sum_{i=0}^{2^{e-2}-1}\biggl(\frac{(2^e-1)!!}{2i+1}+\frac{(2^e-1)!!}{2^e-1-2i}\biggr)=2^e\sum_{i=0}^{2^{e-2}-1}\frac{(2^e-1)!!}{(2i+1)(2^e-1-2i)}.$$ Let $H_e=\displaystyle \sum_{i=0}^{2^{e-2}-1}\frac{(2^e-1)!!}{(2i+1)(2^e-1-2i)}$. We prove by induction that $H_e\equiv2^{e-2}$ mod $2^{e-1}$, which implies the lemma. The claim is true for $e=2$. Assume it true for $e-1$. We have $$H_e\equiv\sum_{i=0}^{2^{e-2}-1}\frac{((2^{e-1}-1)!!)^2}{(2i+1)(2^{e-1}-2i-1)}\pmod{2^{e-1}}.$$ The summands for $i$ and $2^{e-2}-1-i$ are equal. Thus $H_e\equiv 2(2^{e-1}-1)!!H_{e-1}$ (mod $2^{e-1}$). By the induction hypothesis, we obtain $H_e\equiv2^{e-2}$ (mod $2^{e-1}$), as desired. \end{proof} The following results will be used in the proof of Lemma \ref{lem2}. \begin{lemma}\label{8} If $e\ge3$, then, of the $2^{e-1}$ numbers $i^2$ $\bmod$ $2^e$, $i\in S_e$, there are exactly four having each of the $2^{e-3}$ values less than $2^e$ and $\equiv1\pmod 8$.\end{lemma} \begin{proof} Each of the $2^{e-3}$ numbers, being $\equiv1$ (mod 8), is a quadratic residue, and so must occur as $i^2$ for some $i\in S_e$. Each occurs in at least four ways since for odd $i<2^{e-1}$, the numbers $i$, $2^{e-1}-i$, $i+2^{e-1}$, and $2^e-i$ are distinct numbers with the same square mod $2^e$. By the Pigeonhole Principle, the claimed partitioning must hold. \end{proof} \begin{lemma}\label{9} For $e\ge3$, we have $$\sihat_1(1,9,\ldots,2^e-7,1,9,\ldots,2^e-7,1,9,\ldots,2^e-7,1,9,\ldots,2^e-7)\equiv 2^{e-1}\pmod{2^e}.$$ \end{lemma} \begin{proof}The proof is by induction. The claim is true for $e=3$ and $4$; we have $\sihat_1(1,1,1,1)=4$ and $\sihat_1(1,9,1,9,1,9,1,9)=4\cdot9^4+4\cdot9^3=4\cdot9^3\cdot10$. For arbitrary $e$, our expression equals $4\cdot9^3\cdots(2^e-7)^3\cdot\sihat_1(1,9,\ldots2^e-7)$. Because of the 4, we can consider $\sihat_1(1,9,\ldots,2^e-7)$ mod $2^{e-2}$, so we obtain an odd multiple of $4\cdot\Si$ with $$\Si=\sihat_1(1,9,\ldots,2^{e-2}-7,1,9,\ldots,2^{e-2}-7,1,9,\ldots,2^{e-2}-7,1,9,\ldots,2^{e-2}-7).$$ By the induction hypothesis, $\Si\equiv2^{e-3}$ (mod $2^{e-2}$), and so our desired expression is $\equiv2^{e-1}$ (mod $2^e$).\end{proof} \begin{proposition}\label{sqprop} If $e\ge1$, then $\displaystyle\sum_{i\in S_e}\dfrac{((2^e-1)!!)^2}{i^2}\equiv 2^{e-1}\pmod{2^e}$.\end{proposition} \begin{proof} By Lemma \ref{8}, it equals the expression in Lemma \ref{9}.\end{proof} \begin{proof}[Proof of Lemma \ref{lem2}.] Let $D_e=\{(a,b)\in S_e\times S_e:\ a