OFFSET
3,2
COMMENTS
{R(1),...,R(phi(prime(n)#))} = {(prime(n)#/2 +- {R(1),...,R(k)}*2^{1,2,...,z}) mod prime(n)#}.
The formula is used for the compressed representation of the set of the multiplicative group of integers modulo prime(n)#. This is a new formula in number theory. {R(1),...,R(k)} is the shortcut set of the multiplicative group of integers modulo prime(n)# (or compressed representation of the set of the multiplicative group of integers modulo prime(n)#).
LINKS
Alexey V. Bazhin, Table of n, a(n) for n = 3..24
FORMULA
EXAMPLE
First example:
Let R = {1, 7, 11, 13, 17, 19, 23, 29} be the set of the multiplicative group of integers modulo 30 (or it is the set of positive integers less than 2*3*5 and prime to 2*3*5, or it is the reduced residue system for the 3rd primorial number 30 = A002110(3)).
The cardinality of |R| is equal to 8 elements, 8 = A005867(3).
The set {1} is the shortcut set of the multiplicative group of integers modulo 30.
The cardinality of |{1}| = 1, i.e., a(1) = 1.
R = { (30/2 +- {1}*2^{1, ..., 4}) mod 30 } = {(30/2 +- {1}*2^{1,2,3,4}) mod 30}={(15+2^1) mod 30, (15-2^1) mod 30,(15+2^2) mod 30, (15-2^2) mod 30, (15+2^3) mod 30, (15-2^3) mod 30, (15+2^4) mod 30, (15-2^4) mod 30} = {1,7,11,13,17,19,23,29},
4 is the smallest number m with the property that 2^m-1 is divisible by the first n odd primes.
Second example:
Let R = {1, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 121, 127, 131, 137, 139, 143, 149, 151, 157, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 209} be the set of the multiplicative group of integers modulo 210 (or it is the set of positive integers less than 2*3*5*7 and prime to 2*3*5*7, or it is the reduced residue system for the 4th primorial number 210 = A002110(4)).
The cardinality of |R| is equal to 48 elements, 48 = A005867(5).
The set {1, 11} is the shortcut set of the multiplicative group of integers modulo 210.
The cardinality of |{1, 11}| = 2, i.e., a(2) = 2.
R = { ( 210/2 +- {1, 11}*2 ^{1..12}) mod 210 }, where 210 = A002110(4), 12 = A155747(3), |R| = A005867(4).
12 is the smallest number m with the property that 2^m-1 is divisible by the first n odd primes.
General case:
R = {R(1), ..., R(phi(prime(n)#))},
R = {(prime(n)#/2 +- {R(1),R(2),...,R(k)}*2^{1,2,...,z}) mod prime(n)#}, where prime(n)# is the product of the first n primes, i.e., it is A002110(n); phi is Euler's totient function, which counts the positive integers up to a given argument that are relatively prime to the argument, in our case phi(prime(n)#) is A005867;
R is the set of the multiplicative group of integers modulo prime(n)#;
z is a term of A155747.
k is a term of a(n).
R(1) <= R(k) < R(phi(prime(n)#)).
Table:
+-----+-----------+----------------+---------+------+
| | prime(n)# | phi(prime(n)#) | z | k |
+-----+-----------+----------------+---------+------+
| 0 | 1 | 1 | - | - |
| 1 | 2 | 1 | - | - |
| 2 | 6 | 2 | 2 | - |
| 3 | 30 | 8 | 4 | 1 |
| 4 | 210 | 48 | 12 | 2 |
| 5 | 2310 | 480 | 60 | 4 |
| 6 | 30030 | 5760 | 60 | 48 |
| 7 | 510510 | 92160 | 120 | 384 |
| 8 | 9699690 | 1658880 | 360 | 2304 |
| .. | ... | ... | ... | ... |
PROG
(PARI) f(n) = prod(k=1, n, prime(k)-1); \\ A005867
g(n) = lcm(vector(n, k, znorder(Mod(2, prime(k+1))))); \\ A155747
a(n) = f(n+2)/(g(n+1)*2); \\ Michel Marcus, Jun 25 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alexey V. Bazhin, Jun 15 2019
STATUS
approved