Some 2-adic Integers Related to the Odd Part of 2^{e}!

Donald M. Davis Department of Mathematics Lehigh University Bethlehem, PA 18015 USA

                        dmd1@lehigh.edu

Abstract

The odd part of 2^{e}! as e → ∞ leads to a 2-adic integer z. The bits of z were publicized in OEIS sequence \underline{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.

1 Introduction

In [1], 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 ∞ is a 2-adic integer, which we call z. In sequence \underline{A359349} of the 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 2 and 3, we prove generalizations of both.

Let ν(n) denote the exponent of 2 in the prime factorization of n, and od(n) = 2/2^{ν(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 ≤ e ≤ 30. 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

⋯ 011010001011.  (1)

In \underline{A359349}, a larger table (64 bits for e ≤ 40) is presented.

e

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

Table 1: first 40 bits in BBE of od(2^{e}!).

Bits 0 through e of od(2^{e}!) are stable; they agree with those of z. The unstable bits of od(2^{e}!) are those in position ≥ e + 1; they appear to the right of the space in Table 1. 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 \underline{A359349}.

Theorem 1. There is a 2-adic integer K such that, for all d and e > d, we have

uns(e, d) + K ≡ stab(e + 1, d) (mod 2^{d}).

Example 2. The BBE of K begins 1011011. This will be seen in Example 15. 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 1. We verify Theorem 1 with d = 7 and e = 17 by reversing the order of the bits and checking the binary addition in Table 2.

\begin{matrix}uns(17, 7) & ⋯ 1001010 \\ K & ⋯ 1101101 \\ stab(18, 7) & ⋯ 0110111 \end{matrix}

Table 2: Binary addition check.

This relationship between the stable and unstable parts is, at least, a curiosity. It could be useful in calculations. We will see in Section 2 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 odpr(ℓ, m) denote the product of all odd integers j satisfying ℓ ≤ j ≤ m, and let

h(m) = odpr(2^{m−1} + 1, 2^{m} − 1).  (2)

We begin with the following elementary proposition.

Proposition 3. For any e ≥ 1, we have

od(2^{e}!) = ∏_{m=2}^{e} h(m)^{e+1−m}.

Proof. Each factor j of h(m) occurs with coefficient 2^{i} for 0 ≤ i ≤ e − m in 2^{e}!.

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 \underline{A359349}, makes it more efficient.

Theorem 4. If 2 ≤ m − 1 ≤ B ≤ 3m − 7, and d = 2 + ⌊\frac{B−m}{2}⌋, then

h(m) ≡ odpr(2^{m−1} + 1, 2^{m−1} + 2^{d} − 1)^{2^{m−1−d}} (mod 2^{B}).

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 (2). We compare computing od(2^{49}!) mod 2^{50} via Proposition 3 and computing it using Theorem 4. In either case, we compute h(m) for m < 19 using (2). In Table 3 we list, for even values of m between 20 and 44, the approximate number of multiplications required to compute h(m) using (2) (the Old way) and using Theorem 4 (the New way). Note that h(m) must then be raised to the 50 − m power mod 2^{50}.

\begin{matrix}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 \\ 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{matrix}

Table 3: Two ways of computing od(2^{49}!) mod 2^{50}.

In preliminary discussion, Schoenfield \underline{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.”

2 A formula for the 2-adic integer K in Theorem 1

In this section, we prove Theorem 1 and give a formula for the 2-adic integer K that occurs in it. We begin by reviewing the proof [1] of existence of the 2-adic integer z, as some of the ingredients will be useful later.

Lemma 5. Let I_{e} = {i : 2^{e−1} < i ≤ 2^{e}} and S_{e} = {j : j odd and 1 ≤ j < 2^{e}}. Then od : I_{e} → S_{e} is bijective.

Proof. The inverse function ϕ is defined by ϕ(u) = 2^{t}u where t = max{k : 2^{k}u ≤ 2^{e}}.

Lemma 6. If e ≥ 3, the product of all odd positive integers less than 2^{e} is ≡ 2^{e} + 1 (mod 2^{e+1}).

Proof. We begin with the proof [2, Lemma 1] that the product is ≡ 1 (mod 2^{e}). Pair each element with its inverse in ℤ/2^{e}. Only ±1 and 2^{e−1} ± 1 equal their own inverse, and their product is 1, while all other pairs yield 1.

Let P be the set of pairs (a, b) ∈ S_{e} × S_{e} with a < b and ab ≡ 2^{e} + 1 (mod 2^{e+1}). If (a, b) ∈ P, then so is (2^{e} − b, 2^{e} − a) since a + b is even. Moreover, (a, b) ≠ (2^{e} − b, 2^{e} − a) since, if so, then a(2^{e} − a) ≡ 2^{e} + 1 (mod 2^{e+1}), which cannot occur since a^{2} ≡ 1 (mod 8). Thus the cardinality of P is even, and hence the product of all ab with (a, b) ∈ P is ≡ 1 (mod 2^{e+1}). Other pairs (c, d) with cd ≡ 1 (mod 2^{e}) have cd ≡ 1 (mod 2^{e+1}). Finally we have 1, 2^{e} − 1, and 2^{e−1} ± 1, whose product is ≡ 2^{e} + 1 (mod 2^{e+1}).

Corollary 7. If e ≥ 3, then od(2^{e−1}!) ≡ od(2^{e}!) (mod 2^{e}).

Proof. By Lemmas 5 and 6, we have

\frac{od(2^{e}!)}{od(2^{e−1}!)} = ∏_{i∈I_{e}} od(i) = ∏_{j∈S_{e}} j ≡ 1 (mod 2^{e}).

Corollary 8. There is a 2-adic integer z which equals od(2^{e−1}!) (mod 2^{e}) for all e.

The stronger (mod 2^{e+1}) part of Lemma 6 is not needed here, but will be used shortly. A stronger version of the next result will be proved in Theorem 16.

Proposition 9. If e ≥ 2 and S_{e} is as above, then

∏_{i∈S_{e}} i ≡ ∏_{i∈S_{e}}(2^{e} + i) (mod 2^{2e}).

Proof. If S is a set of cardinality n, let σ̂_{i}(S) = σ_{n−i}(S), where σ is the usual elementary symmetric polynomial. Then σ̂_{1}(S_{e}) is divisible by 2^{e} since, for odd j ≤ 2^{e−1} − 1, the expression

∏_{\begin{matrix}i∈S_{e} \\ i≠j \end{matrix}} i + ∏_{\begin{matrix}i∈S_{e} \\ i≠2^{e}−j \end{matrix}} i

is divisible by 2^{e}. We have

∏_{i∈S_{e}}(2^{e} + i) − ∏_{i∈S_{e}} i = ∑_{j>0} 2^{je}σ̂_{j}(S_{e}) ≡ 2^{e}σ̂_{1}(S_{e}) ≡ 0 (mod 2^{2e}).

Let (2^{e} − 1)!! = odpr(1, 2^{e} − 1).

Corollary 10. If e ≥ 2, then \frac{(2^{e} − 1)!! − 1}{2^{e}} ≡ \frac{(2^{e+1} − 1)!! − 1}{2^{e+1}} (mod 2^{e−1}).

Proof. By Lemma 6, the two expressions are odd integers. We show that their ratio is ≡ 1 (mod 2^{e−1}). Let A = (2^{e} − 1)!! − 1. By Lemma 6, A = 2^{e}u with u odd. By Proposition 9, odpr(2^{e} + 1, 2^{e+1} − 1) = A + 1 + k2^{2e} for some integer k. The desired ratio is

\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} ≡ 1 (mod 2^{e−1}).

Definition 11. We define w to be the 2-adic integer which is congruent to \frac{(2^{e} − 1)!! − 1}{2^{e}} (mod 2^{e−1}) for all e.

This is well-defined by Corollary 10. One can compute that the binary expansion of w ends ⋯ 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 1 in a metastable range.

Theorem 12. If e ≥ 3, then

\frac{od(2^{e}!) − od(2^{e−1}!)}{2^{e}} ≡ zw (mod 2^{e−1}).

Proof. By Lemma 5, we have (2^{e} − 1)!! = \frac{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}} · od(2^{e−1}!) = \frac{od(2^{e}!) − od(2^{e−1}!)}{2^{e}}.

The result follows now from Corollary 8 and Definition 11.

Example 13. The binary expansion of zw ends ⋯ 011000010011, obtained by multiplying the binary numbers in (1) and just after Definition 11. The numbers od(2^{7}!) and od(2^{6}!) agree mod 2^{7}. From Table 1, beginning in the 2^{7} position, the binary expansion of od(2^{7}!) ends ⋯ 1010011, while that of od(2^{6}!) ends with eight 0’s. The difference agrees with zw mod 2^{6}.

We now state the main theorem of this section.

Theorem 14. The 2-adic integer K of Theorem 1 equals −zw.

Proof of Theorems 1 and 14. The difference stab(e + 1, d) − uns(e, d), as described in the

paragraph preceding Theorem 1, equals \frac{od(2^{e+d}!) − od(2^{e}!)}{2^{e+1}} (mod 2^{d}). We have

\frac{od(2^{e+d}!) − od(2^{e}!)}{2^{e+1}} = ∑_{i=1}^{d} \frac{od(2^{e+i}!) − od(2^{e+i−1}!)}{2^{e+1}}

= ∑_{i=1}^{d} 2^{i−1} \frac{od(2^{e+i}!) − od(2^{e+i−1}!)}{2^{e+i}}

≡ ∑_{i=1}^{d} 2^{i−1}zw (mod 2^{e})

≡ ∑_{i=1}^{∞} 2^{i−1}zw (mod 2^{d})

= −zw.

Example 15. The binary expansion of −zw ends ⋯ 010111101101, since adding this to the zw in Example 13 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 1, 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 1 with d = 12 and e = 14.

3 Proof of Theorem 4

In this section, we prove Theorem 4 and some mild generalizations. The bulk of our work is the following strengthening of Proposition 9, the proof of which appears later.

Theorem 16. With S_{e} as defined in Lemma 5, and A any integer, if e ≥ 2, then

∏_{i∈S_{e}}(A2^{e} + i) ≡ ∏_{i∈S_{e}} i (mod 2^{3e−1}).

Corollary 17. For any integers A, B, j, and e ≥ 2, we have

∏_{i∈S_{e}}(A2^{e} + i)^{2^{j}} ≡ ∏_{i∈S_{e}}(B2^{e} + i)^{2^{j}} (mod 2^{3e−1+j}).

Proof. It is elementary that if α ≡ β (mod 2t), then α^{2} ≡ β^{2} (mod 4t). We apply this iteratively to Theorem 16, and then both expressions in the corollary are congruent to ∏ i^{2^{j}}.

Proof of Theorem 4. We write the conjectured congruences in succession, beginning

odpr(2^{m−1} + 1, 2^{m} − 1) ≡ odpr(2^{m−1} + 1, 2^{m−1} + 2^{m−2} − 1)^{2} (mod 2^{3m−7}),

then

odpr(2^{m−1} + 1, 2^{m−1} + 2^{m−2} − 1)^{2} ≡ odpr(2^{m−1} + 1, 2^{m−1} + 2^{m−3} − 1)^{2^{2}} (mod 2^{3m−9}),

with arbitrary entry

odpr(2^{m−1} + 1, 2^{m−1} + 2^{d+1} − 1)^{2^{m−2−d}} ≡ odpr(2^{m−1} + 1, 2^{m−1} + 2^{d} − 1)^{2^{m−1−d}} (mod 2^{2d+m−3}).

After canceling odpr(2^{m−1} + 1, 2^{m−1} + 2^{d} − 1)^{2^{m−2−d}}, this becomes

odpr(2^{m−1} + 2^{d} + 1, 2^{m−1} + 2^{d+1} − 1)^{2^{m−2−d}}

≡ odpr(2^{m−1} + 1, 2^{m−1} + 2^{d} − 1)^{2^{m−2−d}} (mod 2^{2d+m−3}).

We can restate this as

∏_{i∈S_{d}}(2^{m−1} + 2^{d} + i)^{2^{m−2−d}} ≡ ∏_{i∈S_{d}}(2^{m−1} + i)^{2^{m−2−d}} (mod 2^{2d+m−3}),

and this is a consequence of Corollary 17.

We prove the following two lemmas, from which Theorem 16 follows easily. Lemma 18. If e ≥ 2, then σ̂_{1}(S_{e}) ≡ 2^{2e−2} (mod 2^{2e−1}). Lemma 19. If e ≥ 2, then σ̂_{2}(S_{e}) ≡ 2^{e−2} (mod 2^{e−1}). Proof of Theorem 16. We have

∏_{i∈S_{e}}(A2^{e} + i) − ∏_{i∈S_{e}} i = ∑_{j>0}(A2^{e})^{j}σ̂_{j}(S_{e}) ≡ 0 (mod 2^{3e−1})

by Lemmas 18 and 19, with the argument slightly different for the two parities of A. Proof of Lemma 18. If e ≥ 2, then

σ̂_{1}(S_{e}) = ∑_{i=0}^{2^{e−2}−1}(\frac{(2^{e} − 1)!!}{2i + 1} + \frac{(2^{e} − 1)!!}{2^{e} − 1 − 2i}) = 2^{e} ∑_{i=0}^{2^{e−2}−1} \frac{(2^{e} − 1)!!}{(2i + 1)(2^{e} − 1 − 2i)}.

Let H_{e} = ∑_{i=0}^{2^{e−2}−1} \frac{(2^{e} − 1)!!}{(2i + 1)(2^{e} − 1 − 2i)}. We prove by induction that H_{e} ≡ 2^{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} ≡ ∑_{i=0}^{2^{e−2}−1} \frac{((2^{e−1} − 1)!!)^{2}}{(2i + 1)(2^{e−1} − 2i − 1)} (mod 2^{e−1}).

The summands for i and 2^{e−2} − 1 − i are equal. Thus H_{e} ≡ 2(2^{e−1} − 1)!!H_{e−1} (mod 2^{e−1}). By the induction hypothesis, we obtain H_{e} ≡ 2^{e−2} (mod 2^{e−1}), as desired.

The following results will be used in the proof of Lemma 19. Lemma 20. If e ≥ 3, then, of the 2^{e−1} numbers i^{2} mod 2^{e}, i ∈ S_{e}, there are exactly four having each of the 2^{e−3} values less than 2^{e} and ≡ 1 (mod 8).

Proof. Each of the 2^{e−3} numbers, being ≡ 1 (mod 8), is a quadratic residue, and so must occur as i^{2} for some i ∈ 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.

Lemma 21. For e ≥ 3, we have

σ̂_{1}(1, 9, …, 2^{e} − 7, 1, 9, …, 2^{e} − 7, 1, 9, …, 2^{e} − 7, 1, 9, …, 2^{e} − 7) ≡ 2^{e−1} (mod 2^{e}).

Proof. The proof is by induction. The claim is true for e = 3 and 4; we have σ̂_{1}(1, 1, 1, 1) = 4 and σ̂_{1}(1, 9, 1, 9, 1, 9, 1, 9) = 4 · 9^{4} + 4 · 9^{3} = 4 · 9^{3} · 10. For arbitrary e, our expression equals 4 · 9^{3} ⋯ (2^{e} − 7)^{3} · σ̂_{1}(1, 9, … 2^{e} − 7). Because of the 4, we can consider σ̂_{1}(1, 9, …, 2^{e} − 7) mod 2^{e−2}, so we obtain an odd multiple of 4 · Σ with

Σ = σ̂_{1}(1, 9, …, 2^{e−2} − 7, 1, 9, …, 2^{e−2} − 7, 1, 9, …, 2^{e−2} − 7, 1, 9, …, 2^{e−2} − 7).

By the induction hypothesis, Σ ≡ 2^{e−3} (mod 2^{e−2}), and so our desired expression is ≡ 2^{e−1} (mod 2^{e}).

Proposition 22. If e ≥ 1, then ∑_{i∈S_{e}} \frac{((2^{e} − 1)!!)^{2}}{i^{2}} ≡ 2^{e−1} (mod 2^{e}).

Proof. By Lemma 20, it equals the expression in Lemma 21.

Proof of Lemma 19. Let D_{e} = {(a, b) ∈ S_{e} × S_{e} : a < b}. Note that

σ̂_{2}(S_{e}) = ∑_{(a,b)∈D_{e}} \frac{(2^{e} − 1)!!}{a · b},

denoted by T_{e}. Write T_{e} = T_{1,e} + T_{2,e}, where

T_{1,e} = ∑_{\begin{matrix}(a,b)∈D_{e} \\ a≢b (2^{e−1}) \end{matrix}} \frac{(2^{e} − 1)!!}{a · b} and T_{2,e} = ∑_{\begin{matrix}(a,b)∈D_{e} \\ a≡b (2^{e−1}) \end{matrix}} \frac{(2^{e} − 1)!!}{a · b}.

Each summand of T_{2,e} corresponds to a unique element of S_{e−1}, and so

T_{2,e} ≡ ∑_{a∈S_{e−1}} \frac{((2^{e−1} − 1)!!)^{2}}{a^{2}} ≡ 2^{e−2} (mod 2^{e−1})

by Proposition 22.

We prove T_{1,e} ≡ 0 (mod 2^{e−1}) by induction. It is true when e = 3 as we obtain four summands, each with denominator 3. Assume validity for e − 1. Every element of D_{e−1} corresponds to four summands of T_{1,e} which are equal mod 2^{e−1}. We obtain

T_{1,e} ≡ 4 ∑_{(a,b)∈D_{e−1}} \frac{((2^{e−1} − 1)!!)^{2}}{a · b} = 4(2^{e−1} − 1)!!(T_{1,e−1} + T_{2,e−1}) ≡ 0 (mod 2^{e−1}),

using the induction hypothesis for 4T_{1,e−1} and the already-proved result for 4T_{2,e−1}.

4 Acknowledgments

We thank Andrew Granville for providing an alternate proof of Lemma 18, involving properties of Bernoulli numbers. We thank the referee for several comments which improved the exposition.

References

[1] D. M. Davis, Binomial coefficients involving infinite powers of primes, Amer. Math. Monthly 121 (2014) 734–737.

[2] A. Granville, Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. In Organic Mathematics, CMS Conf. Proc., Vol. 20, Amer. Math. Soc., 1997, pp. 253–276.

2020 Mathematics Subject Classification: Primary 11B50; Secondary 11E95, 11A15. Keywords: 2-adic integer, 2-power, factorial, integer sequence.

(Concerned with sequence \underline{A359349}.)

Received October 30 2025; revised version received May 7 2026; May 10 2026. Published in Journal of Integer Sequences, May 15 2026.

Return to Journal of Integer Sequences home page.