Search: a302141 -id:a302141
|
| |
|
|
A053447
|
|
Multiplicative order of 4 mod 2n+1.
|
|
+0
23
|
|
|
|
1, 1, 2, 3, 3, 5, 6, 2, 4, 9, 3, 11, 10, 9, 14, 5, 5, 6, 18, 6, 10, 7, 6, 23, 21, 4, 26, 10, 9, 29, 30, 3, 6, 33, 11, 35, 9, 10, 15, 39, 27, 41, 4, 14, 11, 6, 5, 18, 24, 15, 50, 51, 6, 53, 18, 18, 14, 22, 6, 12, 55, 10, 50, 7, 7, 65, 9, 18, 34, 69, 23, 30, 14, 21, 74, 15, 12, 10, 26
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
For a set S = {x, y} (x < y), let f(S) = {2x, y - x}, then a(n) is the smallest k > 0 such that f_k({1, 2n}) = {1, 2n} where f_k(S) denotes iteration for k times. E.g., for n = 3 we have: f_1({1, 6}) = f({1, 6}) = {2, 5}, f_2({1, 6}) = f({2, 5}) = {3, 4}, f_3({1, 6}) = f({3, 4}) = {1, 6}. - Jianing Song, Jan 27 2019
Let psi = A002322. For n > 0, we have 4^(psi(2*n+1)/2) = 2^psi(2*n+1) == 1 (mod 2*n+1), so a(n) divides psi(2*n+1)/2 => a(n) <= psi(2*n+1)/2 <= n. a(n) = psi(2*n+1)/2 if and only if one of the two following conditions holds: (a) the multiplicative order of 2 modulo 2*n+1 is psi(2*n+1); (b) the multiplicative order of 2 modulo 2*n+1 is psi(2*n+1)/2, and psi(2*n+1) == 2 (mod 4).
Additionally, a(n) = n if and only if 2*n+1 = p is a prime, and one of the two following conditions holds: (a) 2 is a primitive root modulo p; (b) p == 3 (mod 4), and the multiplicative order of 2 modulo p is (p-1)/2 (in this case, we have p == 7 (mod 8) since 2 is a quadratic residue modulo p). Such primes p are listed in A216371. (End)
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let b = A002326, then a(n) = b(n) if b(n) is odd, otherwise a(n) = b(n)/2. - Joerg Arndt, Feb 03 2019
|
|
|
MATHEMATICA
|
|
|
|
PROG
|
(Magma) [1] cat [Modorder(4, 2*n+1): n in [1..100]]; // Vincenzo Librandi, Apr 01 2014
(PARI) a(n) = znorder(Mod(4, 2*n+1)); \\ Michel Marcus, Feb 05 2015
(GAP) List([0..80], n->OrderMod(4, 2*n+1)); # Muniru A Asiru, Feb 25 2019
|
|
|
CROSSREFS
|
Cf. A050976, A070667-A070675, A002326, A070676, A070677, A070681, A070678, A053451, A070679, A070682, A070680, A070683, A302141.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A105876
|
|
Primes for which -4 is a primitive root.
|
|
+0
5
|
|
|
|
3, 7, 11, 19, 23, 47, 59, 67, 71, 79, 83, 103, 107, 131, 139, 163, 167, 179, 191, 199, 211, 227, 239, 263, 271, 311, 347, 359, 367, 379, 383, 419, 443, 463, 467, 479, 487, 491, 503, 523, 547, 563, 587, 599, 607, 619, 647, 659, 719, 743, 751, 787, 823, 827, 839, 859, 863
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Also, primes for which -16 is a primitive root. For proof see following comments from Michael Somos, Aug 07 2009:
Let p = 8*t + 3 be prime. It is well-known that 2 is a primitive root.
We will use the obvious fact that if a primitive root is a power of another element, then that other element is also a primitive root. So
-1 == 2^(4*t+1) (mod p) because 2 is primitive root.
-2 == 2^(4*t+2) == 4^(2*t+1) (mod p) obvious
2 == (-4)^(2*t+1) (mod p) obvious, therefore -4 is also primitive root.
2 == 2^(8*t+3) (mod p) obviously works not just for 2
4 == 2^(8*t+4) == 16^(2*t+1) (mod p) obvious
-4 == (-16)^(2*t+1) (mod p) obvious, therefore -16 is also primitive root.
The case where p = 8*t + 7 is similar.
Equivalently, primes p == 3 (mod 4) such that the multiplicative order of 4 modulo p is (p-1)/2 (a subsequence of A216371).
Proof of equivalence: let ord(a,k) be the multiplicative of a modulo k. First we notice that all terms are congruent to 3 modulo 4, since -4 is a quadratic residue modulo p if p == 1 (mod 4). If ord(4,p) = (p-1)/2. Note that (p-1)/2 is odd, so it is coprime to ord(-1,p) = 2. As a result, ord(-4,p) = ((p-1)/2) * 2 = p-1. Conversely, If ord(-4,p) = p-1, we must have ord(4,p) = (p-1)/2 by noting that ord(-4,p) <= lcm(2,ord(4,p)).
Also primes p such that the multiplicative order of 16 modulo p is (p-1)/2. Proof: note that ord(16,p) = ord(-4,p)/gcd(ord(-4,p),2). If ord(-4,p) = p-1, then ord(16,p) = (p-1)/2. Conversely, if ord(16,p) = (p-1)/2, then ord(-4,p) = p-1, since otherwise ord(-4,p) = (p-1)/2 is odd, which is impossible since that -4 is not a quadratic residue modulo a prime p == 3 (mod 4).
{(a(n)-1)/2} is the sequence of indices of fixed points of A302141.
An odd prime p is a term if and only if p == 3 (mod 4) and the multiplicative order of 2 modulo p is p-1 or (p-1)/2 (p-1 if p == 3 (mod 8), (p-1)/2 if p == 7 (mod 8)).
It seems that a(n) = 2*A163778(n-1) + 1 for n >= 2. (End)
|
|
|
LINKS
|
|
|
|
MATHEMATICA
|
pr=-4; Select[Prime[Range[200]], MultiplicativeOrder[pr, # ] == #-1 &] (* OR *)
a[p_, q_]:=Sum[2 Cos[2^n Pi/((2 q+1)(2 p+1))], {n, 1, 2 q p}]
2 Select[Range[500], Rationalize[N[a[#, 2], 20]]==1 &]+1
|
|
|
PROG
|
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A372801
|
|
Order of 16 modulo the n-th prime: least k such that prime(n) divides 16^k-1.
|
|
+0
5
|
|
|
|
1, 1, 3, 5, 3, 2, 9, 11, 7, 5, 9, 5, 7, 23, 13, 29, 15, 33, 35, 9, 39, 41, 11, 12, 25, 51, 53, 9, 7, 7, 65, 17, 69, 37, 15, 13, 81, 83, 43, 89, 45, 95, 24, 49, 99, 105, 37, 113, 19, 29, 119, 6, 25, 4, 131, 67, 135, 23, 35, 47, 73, 51, 155, 39, 79, 15, 21, 173, 87, 22, 179
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
2,3
|
|
|
COMMENTS
|
a(n) is the period of the expansion of 1/prime(n) in hexadecimal.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) <= (prime(n) - 1)/2.
|
|
|
PROG
|
(PARI) a(n) = znorder(Mod(16, prime(n))).
|
|
|
CROSSREFS
|
Cf. A302141 (order of 16 mod 2n+1).
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.007 seconds
|
