A359349 The initial bits, written from left to right, in the 2-adic limit of the mod 2^e value of the odd factor of (2^e)!.

1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0

Offset

1

Comments

Here we refer to the table in the Example, in which the bits of our number, called stable bits, appear to the left of the space. Here is a conjectured relationship between the stable bits starting at any point and the unstable bits on the previous line of the table. There is a 2-adic integer K such that, for any d and n > d, uns(n,d) + K = stab(n+1,d) mod 2^d. Here uns(n,d) is the number whose backwards binary expansion (BBE) is the first d bits after the space on line n, and stab(n+1,d) is the number whose BBE is bits (n+1) to (n+d) of our number, where the numbering of the bits starts at 0. The BBE of K begins 1011011. For example, the BBE of uns(17,7) is 0101001 and that of stab(18,7) is 1110110. Perform the binary addition uns(17,7) + K from left to right on these.

If g[n] = (2^n)!/2^(2^n-1), then

stab(n+1,d) = (g[n+1+d] - (g[n+1+d] mod 2^(n+2)))/ 2^(n+2) mod 2^d, while

uns(n,d) = (g[n] - (g[n] mod 2^(n+1)))/2^(n+1) mod 2^d.

From Jon E. Schoenfield, Jul 22 2023: (Start)

For any positive integer e, let f(e) be the odd part of (2^e)!, i.e., f(e) = (2^e)!/2^(2^e - 1), and let h(m) be the product of all m-bit odd numbers, i.e., h(m) = Product_{j odd, j = 2^(m-1) + 1 .. 2^m - 1} j for m >= 2. Then f(e) = Product_{m=2..e} h(m)^(e+1-m).

Thus, the B least significant bits of the odd part of (2^e)! -- i.e., f(e) mod 2^B -- can be computed as Product_{m=2..e} h(m)^(e+1-m) mod 2^B (where only the remainder modulo 2^B is retained at each multiplication).

But computing h(m) mod 2^B can become time-consuming as m gets larger, because there are 2^(m-2) consecutive odd numbers to be multiplied. However, if the following conjecture holds, then there is a much faster way to compute those products mod 2^B, depending on the values of e and B.

Conjecture: for all e,B such that 3 <= e < B <= 3*e - 5,

Product_{j odd, j = 2^(e-1) + 1 .. 2^e - 1) ==

(Product_{j odd, j = 2^(e-1) + 1 .. 2^(e-1) + 2^d - 1)^(2^(e-1-d)) (mod 2^B)

where d = 2 + floor((B-e)/2).

(When d < e-1, the product on the right-hand side of the conjectured congruence requires only 1/2^(e-1-d) as many multiplications to compute, after which that product merely needs to be squared one or more times, with the residue mod 2^B taken after each squaring, so this can be much faster than taking the product on the left-hand side of the conjectured congruence.)

(End)

Links

Table of n, a(n) for n=1..41.

Donald M. Davis, Binomial coefficients involving infinite powers of primes, arXiv:1301.6285 [math.NT], 2013.

Donald M. Davis, Binomial coefficients involving infinite powers of primes, Amer Math Monthly 121 (2014) 734-737.

Jon E. Schoenfield, Magma program for calculating ((2^e)! / 2^(2^e - 1)) mod 2^40 for e = 1..28 and listing the bits (see table in Example section).

Jon E. Schoenfield, 128 least significant bits of (2^e)! / 2^(2^e - 1) for e = 2..40.

Example

The odd part of (2^4)! is 3*(5*3*7)*(9*5*11*3*13*7*15) = 3^3*(5*7)^2*(9*11*13*15), which explains the Maple program below.
From Jon E. Schoenfield, Jul 07 2023: (Start)
The table below shows, for e = 2..40, the 64 least significant bits of the odd part of (2^e)!, with the least significant bit at the left end, and with a space inserted immediately after the (e+1)st bit. For every row after the e=1 row, the first e+1 bits appear to have converged to their final values, and the (e+2)nd bit is the opposite of its apparent limiting value.
.
   e |        64 least significant bits of (2^e)! / 2^(2^e - 1)
  ---+------------------------------------------------------------------
   2 | 110 0000000000000000000000000000000000000000000000000000000000000
   3 | 1101 110010000000000000000000000000000000000000000000000000000000
   4 | 11010 11101110111011100000110010000000000000000000000000000000000
   5 | 110100 1011001110100011000001101010001001011100110001110101010100
   6 | 1101000 000000001101000110100010110011110010011111011101100011000
   7 | 11010001 10010101001010001010001101011100101011111100000011100010
   8 | 110100010 0111100111001000110000010011101001010011011110111101110
   9 | 1101000101 000110101110110000001011000011110010110111000000001101
  10 | 11010001011 10101101100010111001010101001000111000001110000010111
  11 | 110100010110 0010011111110101111010110111011111110111111000001001
  12 | 1101000101101 110111110000001100111011011001001110011110011100011
  13 | 11010001011010 11100001101100011101011000100010110100010111101000
  14 | 110100010110100 1011001111011110110100001011000011010110110001101
  15 | 1101000101101000 000011110100000100110000000000101000111010111100
  16 | 11010001011010001 10000001011001001111011101000110001100111111001
  17 | 110100010110100010 0101001000011101001001001110110111101010011110
  18 | 1101000101101000101 011101001000000000010011011001011111000011010
  19 | 11010001011010001011 00000101101001010101010110010100110101001110
  20 | 110100010110100010111 1001101111101111101111001000000000100100001
  21 | 1101000101101000101110 011011110000010111010010100110010110010001
  22 | 11010001011010001011101 00100001101011100101101110111100001011110
  23 | 110100010110100010111011 1101001111111011100011001000001111001111
  24 | 1101000101101000101110110 111101110010100110111111001001110010010
  25 | 11010001011010001011101100 10000001111101101100010011011100000001
  26 | 110100010110100010111011000 0101001100111010011011010111011011000
  27 | 1101000101101000101110110001 011101101100101111111110100110000000
  28 | 11010001011010001011101100011 00000011011100010010011100001001001
  29 | 110100010110100010111011000111 1001011000110111011010010000100011
  30 | 1101000101101000101110110001110 011111001101100000001110000110110
  31 | 11010001011010001011101100011101 00010101010011010011101000110011
  32 | 110100010110100010111011000111011 1011101001111111010010100110011
  33 | 1101000101101000101110110001110110 000111000010010001110010110011
  34 | 11010001011010001011101100011101101 10100100111011011101001110011
  35 | 110100010110100010111011000111011010 0011100100000001010100001011
  36 | 1101000101101000101110110001110110101 111010101010011110010101011
  37 | 11010001011010001011101100011101101010 10101101111010011001111011
  38 | 110100010110100010111011000111011010100 0010011100001110100001111
  39 | 1101000101101000101110110001110110101001 110111101011101010101000
  40 | 11010001011010001011101100011101101010010 11100011110010101111010
       <-------------- stable bits ------------->\<--- unstable bits ...
(End)

Maple

for i from 0 to 19 do F[i]:=product(2*j+1, j=2^i..2^(i+1)-1) mod 2^21 od:
P:=1: for i from 0 to 19 do P:=(P*F[i]^(20-i)) mod 2^21 od:
with(ListTools): Reverse(convert(P, base, 2));

Prog

(PARI) lista(nn) = my(v=Vecrev(binary((2^nn)!/2^(2^nn-1) % 2^nn))); while (#v != nn, v = concat(v, 0)); v; \\ Michel Marcus, Jul 11 2023

Crossrefs

Cf. A000722, A067667.

Sequence in context: A181101 A321512 A297054 * A266459 A354199 A214509

Adjacent sequences: A359346 A359347 A359348 * A359350 A359351 A359352

Keyword

nonn,more

Author

Donald M Davis, Jul 05 2023

Extensions

a(22)-a(41) from Jon E. Schoenfield, Jul 12 2023

Status

approved