cp's OEIS Frontend

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

%I A006694 M0192 #98 Apr 25 2025 03:06:45
%S A006694 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,
%T A006694 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,
%U A006694 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
%N A006694 Number of cyclotomic cosets of 2 mod 2n+1.
%C A006694 a(0) = 0 by convention.
%C A006694 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.
%C A006694 Also the number of irreducible polynomial factors of the polynomial (x^(2n+1) - 1) / (x - 1) over GF(2). - _V. Raman_, Oct 04 2012
%C A006694 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
%D A006694 Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd edition, Addison-Wesley, 1997.
%D A006694 F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North Holland, 1977, pp. 104-105.
%D A006694 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006694 Ray Chandler, <a href="/A006694/b006694.txt">Table of n, a(n) for n = 0..10000</a>
%H A006694 Christopher Adler and Jean-Paul Allouche, <a href="https://doi.org/10.1080/17513472.2022.2116745">Finite self-similar sequences, permutation cycles, and music composition</a>, Journal of Mathematics and the Arts, 16:3, 244-261, (2022).
%H A006694 J.-P. Allouche, <a href="http://www.jstor.org/stable/44165489">Suites infinies à répétitions bornées</a>, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
%H A006694 J.-P. Allouche, <a href="/A006694/a006694.pdf">Suites infinies à répétitions bornées</a>, Séminaire de Théorie des Nombres de Bordeaux, 20 (13 April, 1984), 1-11.
%H A006694 Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, <a href="https://arxiv.org/abs/2504.17564">Doubling modulo odd integers, generalizations, and unexpected occurrences</a>, arXiv:2504.17564 [math.NT], 2025.
%H A006694 Michael Assis, <a href="https://arxiv.org/abs/2403.09277">Folding Pi</a>, arXiv:2403.09277 [math.NT], 2024.
%F A006694 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]
%F A006694 a(n) = A081844(n) - 1.
%F A006694 a(n) = A064286(n) + 2*A064287(n).
%F A006694 From _Vladimir Shevelev_, Jan 19 2011: (Start)
%F A006694 1) a(n)=A037226(n) iff 2n+1 is prime;
%F A006694 2) The only case when a(n) < A037226(n) is n=0;
%F A006694 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)
%F A006694 a(n) = A000374(2*n + 1) - 1. - _Joerg Arndt_, Apr 01 2019
%F A006694 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
%e A006694 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.
%p A006694 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..)];
%t A006694 Needs["Combinatorica`"]; f[n_] := Length[ToCycles[Mod[2Range[2n], 2n + 1]]]; Table[f[n], {n, 0, 100}] (* _Ray Chandler_, Apr 25 2008 *)
%t A006694 f[n_] := Length[FactorList[x^(2n + 1) - 1, Modulus -> 2]] - 2; Table[f[n], {n, 0, 100}] (* _Ray Chandler_, Apr 25 2008 *)
%t A006694 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_ *)
%o A006694 (PARI) a(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1; /* cf. A081844 */
%o A006694 vector(122, n, a(n-1)) \\ _Joerg Arndt_, Jan 18 2011
%o A006694 (Python)
%o A006694 from sympy import totient, n_order, divisors
%o A006694 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
%Y A006694 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.
%Y A006694 A001917 gives cycle counts of such permutations constructed only for odd primes.
%Y A006694 Second column of A357217.
%K A006694 nonn,nice,easy
%O A006694 0,4
%A A006694 _N. J. A. Sloane_, Sep 25 2001
%E A006694 Additional comments from _Antti Karttunen_, Jan 05 2000
%E A006694 Extended by _Ray Chandler_, Apr 25 2008
%E A006694 Edited by _N. J. A. Sloane_, Apr 27 2008 at the suggestion of _Ray Chandler_