A064287 -id:A064287 - cp's OEIS frontend

A006694 Number of cyclotomic cosets of 2 mod 2n+1.

0, 1, 1, 2, 2, 1, 1, 4, 2, 1, 5, 2, 2, 3, 1, 6, 4, 5, 1, 4, 2, 3, 7, 2, 4, 7, 1, 4, 4, 1, 1, 12, 6, 1, 5, 2, 8, 7, 5, 2, 4, 1, 11, 4, 8, 9, 13, 4, 2, 7, 1, 2, 14, 1, 3, 4, 4, 5, 11, 8, 2, 7, 3, 18, 10, 1, 9, 10, 2, 1, 5, 4, 6, 9, 1, 10, 12, 13, 3, 4, 8, 1, 13, 2, 2, 11, 1, 8, 4, 1, 1, 4, 6, 7, 19, 2, 2, 19, 1, 2

Offset: 0

N. J. A. Sloane, Sep 25 2001

a(0) = 0 by convention.
The number of cycles in permutations constructed from siteswap juggling patterns 1, 123, 12345, 1234567, etc., i.e., the number of ball orbits in such patterns minus one.
Also the number of irreducible polynomial factors of the polynomial (x^(2n+1) - 1) / (x - 1) over GF(2). - V. Raman, Oct 04 2012
Also, a(n) is the number of cycles of the Josephus permutation for n elements and a count of 2. For n >= 1, the Josephus permutation is given by the n-th row of A321298. See Knuth 1997 (exercise 1.3.3-29). - Pontus von Brömssen, Sep 18 2022

			Mod 15 there are 4 cosets: {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}, so a(7) = 4. Mod 13 there is only one coset: {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7}, so a(6) = 1.

Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd edition, Addison-Wesley, 1997.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North Holland, 1977, pp. 104-105.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Ray Chandler, Table of n, a(n) for n = 0..10000
Christopher Adler and Jean-Paul Allouche, Finite self-similar sequences, permutation cycles, and music composition, Journal of Mathematics and the Arts, 16:3, 244-261, (2022).
J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
J.-P. Allouche, Suites infinies à répétitions bornées, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
Michael Assis, Folding Pi, arXiv:2403.09277 [math.NT], 2024.

Cf. A000010, A000374 (number of factors of x^n - 1 over GF(2)), A002326 (order of 2 mod 2n+1), A037226, A064286, A064287, A081844, A139767, A321298.
A001917 gives cycle counts of such permutations constructed only for odd primes.
Second column of A357217.

with(group); with(numtheory); gen_rss_perm := proc(n) local a, i; a := []; for i from 1 to n do a := [op(a), ((2*i) mod (n+1))]; od; RETURN(a); end; count_of_disjcyc_seq := [seq(nops(convert(gen_rss_perm(2*j),'disjcyc')),j=0..)];

Needs["Combinatorica`"]; f[n_] := Length[ToCycles[Mod[2Range[2n], 2n + 1]]]; Table[f[n], {n, 0, 100}] (* Ray Chandler, Apr 25 2008 *)
f[n_] := Length[FactorList[x^(2n + 1) - 1, Modulus -> 2]] - 2; Table[f[n], {n, 0, 100}] (* Ray Chandler, Apr 25 2008 *)
a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d], {d, Divisors[2n + 1]}] - 1; Table[a[n], {n, 0, 99}] (* Jean-François Alcover, Dec 14 2011, after Joerg Arndt *)

a(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1; /* cf. A081844 */
vector(122, n, a(n-1)) \\ Joerg Arndt, Jan 18 2011

from sympy import totient, n_order, divisors
def A006694(n): return sum(totient(d)//n_order(2,d) for d in divisors((n+1<<1)-1,generator=True) if d>1) # Chai Wah Wu, Apr 09 2024

Conjecture: a((3^n-1)/2) = n. - Vladimir Shevelev, May 26 2008 [This is correct. 2*((3^n-1)/2) + 1 = 3^n and the polynomial (x^(3^n) - 1) / (x - 1) factors over GF(2) into Product_{k=0..n-1} x^(2*3^k) + x^(3^k) + 1. - Joerg Arndt, Apr 01 2019]
a(n) = A081844(n) - 1.
a(n) = A064286(n) + 2*A064287(n).
From Vladimir Shevelev, Jan 19 2011: (Start)
1) a(n)=A037226(n) iff 2n+1 is prime;
2) The only case when a(n) < A037226(n) is n=0;
3) If {C_i}, i=1..a(n), is the set of all cyclotomic cosets of 2 mod (2n+1), then lcm(|C_1|, ..., |C_{a(n)}|) = A002326(n). (End)
a(n) = A000374(2*n + 1) - 1. - Joerg Arndt, Apr 01 2019
a(n) = (Sum_{d|(2n+1)} phi(d)/ord(2,d)) - 1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Additional comments from Antti Karttunen, Jan 05 2000
Extended by Ray Chandler, Apr 25 2008
Edited by N. J. A. Sloane, Apr 27 2008 at the suggestion of Ray Chandler

A139035 Primes of the form 4*k+3 with primitive root -2.

Original entry on oeis.org

7, 23, 47, 71, 79, 103, 167, 191, 199, 239, 263, 271, 311, 359, 367, 383, 463, 479, 487, 503, 599, 607, 647, 719, 743, 751, 823, 839, 863, 887, 967, 983, 991, 1031, 1039, 1063, 1087, 1151, 1223, 1231, 1279, 1303, 1319, 1367, 1439, 1447, 1487, 1511, 1543, 1559

Offset: 1

Vladimir Shevelev, May 31 2008, Jun 06 2008

nonn

Original name: Primes with semiprimitive root 2.
If p is a prime, then we call r a semiprimitive root if it has order (p-1)/2 and there is no x for which a^x is congruent to -1 (mod p).  So +/- r^k, 0 <= k <= (p-3)/2 is a complete set of nonzero residues (mod p).
If r=2, then (-1/p)=-1 and, consequently, a(n)==-1(mod 4).
Besides, (2/a(n))=1. Indeed, since 2^((p-1)/2)=1 (mod p), then 2==2^((p+1)/2)=(2^((p+1)/4))^2. Therefore, (a(n))^2==1(mod 16) and thus a(n)==-1(mod 8). This yields that residues 1,2,...,2^((p-3)/2) are quadratic residues modulo a(n), while -1,-2,...,-2^((p-3)/2) are quadratic nonresidues modulo a(n). Primitive root of a(n) is greater than or equal to 3. All terms are in A115591.
Conjecture: primes that have both primitive root -2 and -4. - Davide Rotondo, Dec 20 2024

Amiram Eldar, Table of n, a(n) for n = 1..10000
Christian Elsholtz, Almost all primes have a multiple of small Hamming weight, arXiv:1602.05974 [math.NT], 2016. See p. 6.
Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv preprint arXiv:1608.00862 [math.GM], 2016.
Vladimir Shevelev, On the Newman sum over multiples of a prime with a primitive or semiprimitive root 2, arXiv:0710.1354 [math.NT], 2007.
Vladimir Shevelev Exact exponent in the remainder term of Gelfond's digit theorem in the binary case, Acta Arithm. 136 (2009) 91-100, eq. (10).

Cf. A006694, A002326, A064287, A001917, A001122, A133954, A115591.

Reap[For[p = 3, p <= 10^4, p = NextPrime[p], rp = MultiplicativeOrder[2, p]; rm = MultiplicativeOrder[-2, p]; If[rp != p-1 && rm == p-1, Sow[p]]] ][[2, 1]] (* Jean-François Alcover, Sep 03 2016, after Joerg Arndt *)

{ forprime (p=3, 10^4,
    rp = znorder(Mod(+2,p));
    rm = znorder(Mod(-2,p));
    if ( (rp!=p-1) && (rm==p-1), print1(p,", ") );
);}
/* Joerg Arndt, Jun 03 2012 */

is(n)=n%8==7 && isprime(n) && znorder(Mod(-2,n))==n-1 \\ Charles R Greathouse IV, Nov 30 2017

Prime p is in the sequence iff p==-1(mod 8) and A002326((p-1)/2)=(p-1)/2. A sufficient condition: if p==-1 (mod 8) and (p-1)/2 is prime, then p is in the sequence (the converse statement, generally speaking, is not true).

A006694((a(n)-1)/2)=2 and A064287((a(n)-1)/2)=1.

New name from Joerg Arndt, Jun 03 2012

A064286 Number of cyclotomic cosets C of 2 mod 2n+1 such that -C = C.

Original entry on oeis.org

1, 1, 0, 2, 1, 1, 2, 2, 1, 1, 0, 2, 3, 1, 0, 4, 1, 1, 2, 2, 3, 3, 0, 0, 3, 1, 2, 4, 1, 1, 2, 6, 1, 1, 0, 0, 3, 1, 0, 4, 1, 3, 2, 0, 1, 1, 2, 2, 7, 1, 0, 2, 1, 3, 2, 4, 1, 3, 2, 2, 3, 3, 0, 10, 1, 1, 4, 2, 1, 1, 2, 6, 1, 1, 0, 4, 1, 3, 2, 0, 1, 5, 0, 2, 11, 1, 2, 4, 1, 1, 2, 6, 3, 3, 0, 2, 7, 1, 0, 4, 1, 11, 2, 4

Offset: 1

N. J. A. Sloane, Sep 25 2001

			Mod 15 there are 4 cosets: {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}. Only the cosets {3, 6, 12, 9} and {5, 10} have the desired property. So a(7) = 2.

F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North Holland, 1977, pp. 104-105.

Ray Chandler, Table of n, a(n) for n = 1..10000

Cf. A006694, A064287.

A006694(n) = a(n) + 2*A064287(n).

Extended by Ray Chandler, Apr 25 2008

cp's OEIS Frontend

A139042 Composite numbers c for which A064287((c-1)/2)=1.

Views

Author

Keywords

Comments

Crossrefs

Extensions

A006694 Number of cyclotomic cosets of 2 mod 2n+1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A139035 Primes of the form 4*k+3 with primitive root -2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A064286 Number of cyclotomic cosets C of 2 mod 2n+1 such that -C = C.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Formula

Extensions