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
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
KEYWORD
nonn,more
AUTHOR
Donald M Davis, Jul 05 2023
EXTENSIONS
a(22)-a(41) from Jon E. Schoenfield, Jul 12 2023
STATUS
approved