|
%I M0192 #94 Apr 10 2024 03:30:07
%S 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 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 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 Number of cyclotomic cosets of 2 mod 2n+1.
%C a(0) = 0 by convention.
%C 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 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 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 Donald E. Knuth, The Art of Computer Programming, Vol. 1, 3rd edition, Addison-Wesley, 1997.
%D F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, Elsevier/North Holland, 1977, pp. 104-105.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Ray Chandler, <a href="/A006694/b006694.txt">Table of n, a(n) for n = 0..10000</a>
%H 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 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 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 Michael Assis, <a href="https://arxiv.org/abs/2403.09277">Folding Pi</a>, arXiv:2403.09277 [math.NT], 2024.
%F 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 a(n) = A081844(n) - 1.
%F a(n) = A064286(n) + 2*A064287(n).
%F From _Vladimir Shevelev_, Jan 19 2011: (Start)
%F 1) a(n)=A037226(n) iff 2n+1 is prime;
%F 2) The only case when a(n) < A037226(n) is n=0;
%F 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 a(n) = A000374(2*n + 1) - 1. - _Joerg Arndt_, Apr 01 2019
%F 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 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 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 Needs["Combinatorica`"]; f[n_] := Length[ToCycles[Mod[2Range[2n], 2n + 1]]]; Table[f[n], {n, 0, 100}] (* _Ray Chandler_, Apr 25 2008 *)
%t f[n_] := Length[FactorList[x^(2n + 1) - 1, Modulus -> 2]] - 2; Table[f[n], {n, 0, 100}] (* _Ray Chandler_, Apr 25 2008 *)
%t 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 (PARI) a(n)=sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1; /* cf. A081844 */
%o vector(122, n, a(n-1)) \\ _Joerg Arndt_, Jan 18 2011
%o (Python)
%o from sympy import totient, n_order, divisors
%o 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 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 A001917 gives cycle counts of such permutations constructed only for odd primes.
%Y Second column of A357217.
%K nonn,nice,easy
%O 0,4
%A _N. J. A. Sloane_, Sep 25 2001
%E Additional comments from _Antti Karttunen_, Jan 05 2000
%E Extended by _Ray Chandler_, Apr 25 2008
%E Edited by _N. J. A. Sloane_, Apr 27 2008 at the suggestion of _Ray Chandler_
|
