|
%I #23 Jan 19 2021 21:00:46
%S 1,1,1,2,1,1,1,2,2,1,2,2,1,1,1,6,2,2,1,2,2,3,2,2,2,4,1,2,2,1,1,6,4,1,
%T 2,2,8,2,2,2,1,1,8,2,8,6,6,2,2,2,1,2,4,1,3,2,4,2,6,4,1,4,1,18,6,1,6,2,
%U 2,1,2,2,4,2,1,10,4,6,3,2,4
%N a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.
%C Number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2. There are no primitive irreducible factors for x^(2n)-1 because it always has the same factors as x^n-1. Considering that A000374 also counts the cycles in the map f(x) = 2x mod n, a(n) is also the number of primitive cycles of that mapping. - _T. D. Noe_, Aug 01 2003
%C Equals number of irreducible factors of the cyclotomic polynomial Phi(2n+1,x) over Z/2Z. All factors have the same degree. - _T. D. Noe_, Mar 01 2008
%H T. D. Noe, <a href="/A037226/b037226.txt">Table of n, a(n) for n = 0..10000</a>
%H Brillhart, John; Lomont, J. S.; Morton, Patrick. <a href="http://resolver.sub.uni-goettingen.de/purl?GDZPPN002192802">Cyclotomic properties of the Rudin-Shapiro polynomials</a>, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
%H Jarkko Peltomäki and Aleksi Saarela, <a href="https://doi.org/10.1016/j.jcta.2020.105340">Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2</a>, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also <a href="https://arxiv.org/abs/2004.14657">arXiv:2004.14657</a> [cs.FL], 2020.
%F a(n) = Sum{d|2n+1} mu((2n+1)/d) A000374(d), the inverse Mobius transform of A000374 - _T. D. Noe_, Aug 01 2003
%F a(n) = A037225(n)/A002326(n).
%t a[n_] := EulerPhi[2n+1]/MultiplicativeOrder[2, 2n+1]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Dec 10 2015 *)
%o (PARI) a(n)=eulerphi(2*n+1)/znorder(Mod(2,2*n+1)) \\ _Charles R Greathouse IV_, Dec 29 2013
%Y Cf. A000374 (number of irreducible factors of x^n - 1 over integers mod 2), A081844.
%Y Cf. A006694 (cyclotomic cosets of 2 mod 2n+1).
%K nonn
%O 0,4
%A _N. J. A. Sloane_.
|
