cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

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

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane, Sep 25 2001

Keywords

Comments

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

Examples

			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.
		

References

  • 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).

Crossrefs

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.

Programs

  • Maple
    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..)];
  • Mathematica
    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 *)
  • PARI
    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
    
  • Python
    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

Formula

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

Extensions

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

A000374 Number of cycles (mod n) under doubling map.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 1, 3, 2, 2, 2, 2, 3, 5, 1, 3, 3, 2, 2, 6, 2, 3, 2, 3, 2, 4, 3, 2, 5, 7, 1, 5, 3, 6, 3, 2, 2, 5, 2, 3, 6, 4, 2, 8, 3, 3, 2, 5, 3, 8, 2, 2, 4, 5, 3, 5, 2, 2, 5, 2, 7, 13, 1, 7, 5, 2, 3, 6, 6, 3, 3, 9, 2, 8, 2, 6, 5, 3, 2, 5, 3, 2, 6, 12, 4, 5, 2, 9, 8, 10, 3, 14, 3, 5, 2, 3, 5, 8, 3
Offset: 1

Views

Author

Keywords

Comments

Number of cycles of the function f(x) = 2x mod n. Number of irreducible factors in the factorization of the polynomial x^n-1 over GF(2). - T. D. Noe, Apr 16 2003

Examples

			a(14) = 3 because (1) the function 2x mod 14 has the three cycles (0),(2,4,8),(6,12,10) and (2) the factorization of x^14-1 over integers mod 2 is (1+x)^2 (1+x+x^3)^2 (1+x^2+x^3)^2, which has three unique factors. Note that the length of the cycles is the same as the degree of the factors.
		

References

  • R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983, p. 65.

Crossrefs

Cf. A081844 (number of irreducible factors of x^(2n+1) - 1 over GF(2)).
Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).

Programs

  • Mathematica
    Table[Length[FactorList[x^n - 1, Modulus -> 2]] - 1, {n, 100}]
    CountFactors[p_, n_] := Module[{sum=0, m=n, d, f, i}, While[Mod[m, p]==0, m/=p]; d=Divisors[m]; Do[f=d[[i]]; sum+=EulerPhi[f]/MultiplicativeOrder[p, f], {i, Length[d]}]; sum]; Table[CountFactors[2, n], {n, 100}]
  • PARI
    a(n)={sumdiv(n >> valuation(n,2), d, eulerphi(d)/znorder(Mod(2,d)));}
    vector(100,n,a(n)) \\ Andrew Howroyd, Nov 12 2018
    
  • Python
    from sympy import totient, n_order, divisors
    def A000374(n): return sum(totient(d)//n_order(2,d) for d in divisors(n>>(~n & n-1).bit_length(),generator=True) if d>1)+1 # Chai Wah Wu, Apr 09 2024

Formula

a(n) = Sum_{d|m} phi(d)/ord(2, d), where m is n with all factors of 2 removed. - T. D. Noe, Apr 19 2003
a(n) = (1/ord(2,m))*Sum_{j = 0..ord(2,m)-1} gcd(2^j - 1, m), where m is n with all factors of 2 removed. - Nihar Prakash Gargava, Nov 12 2018

A081844 Number of irreducible factors of x^(2n+1) - 1 over GF(2).

Original entry on oeis.org

1, 2, 2, 3, 3, 2, 2, 5, 3, 2, 6, 3, 3, 4, 2, 7, 5, 6, 2, 5, 3, 4, 8, 3, 5, 8, 2, 5, 5, 2, 2, 13, 7, 2, 6, 3, 9, 8, 6, 3, 5, 2, 12, 5, 9, 10, 14, 5, 3, 8, 2, 3, 15, 2, 4, 5, 5, 6, 12, 9, 3, 8, 4, 19, 11, 2, 10, 11, 3, 2, 6, 5, 7, 10, 2, 11, 13, 14, 4, 5, 9, 2, 14, 3, 3, 12, 2, 9, 5, 2, 2, 5, 7, 8, 20, 3, 3, 20
Offset: 0

Views

Author

N. J. A. Sloane, Apr 11 2003

Keywords

Comments

Also number of nonisomorphic "pure" chain rings with certain parameters.
Number of cycles under doubling map x -> 2*x (mod 2*n+1). - Joerg Arndt, Jan 22 2024

References

  • R. Lidl and H. Niederreiter, Finite Fields, Addison-Wesley, 1983; Theorem 2.47 page 65.

Crossrefs

Cf. A001037.
A000374 gives number of factors of x^n-1 for any n.
Cf. A037226 (number of primitive irreducible factors of x^(2n+1) - 1 over integers mod 2).
Cf. A006694 (number of factors of (x^(2*n+1) - 1) / (x - 1) over GF(2) ).

Programs

  • Maple
    with(numtheory); o := n->if n=1 then 1 else order(2,n); fi; A081844 := proc(n) local d, t1; t1 := 0; for d to n do if n mod d = 0 then t1 := t1 + phi(d)/o(d); end if; end do; t1; end proc;
    Factor(x^(2*n+1)-1) mod 2; nops(%);
  • Mathematica
    a[n_] := Length[Factor[x^(2n+1)-1, Modulus->2] ]; a[0]=1; (* or : *)
    a[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d ], {d, Divisors[2n + 1]}]; Table[ a[n], {n, 0, 97}] (* Jean-François Alcover, Dec 14 2011 *)
  • PARI
    a(n)=sumdiv(2*n+1,d,eulerphi(d)/znorder(Mod(2,d)));
    vector(122,n,a(n-1)) /* Joerg Arndt, Jan 18 2011 */
    
  • Python
    from sympy import totient, n_order, divisors
    def A081844(n): return sum(totient(d)//n_order(2,d) for d in divisors((n+1<<1)-1,generator=True) if d>1) + 1 # Chai Wah Wu, Apr 09 2024

Formula

a(n) = Sum_{ d| 2*n+1 } phi(d)/ord_2(d), where phi = A000010, ord_2 = A002326.
a(n) = A006694(n) + 1. - Joerg Arndt, Apr 01 2019
a(n) = A000374(2*n+1). - Joerg Arndt, Jan 22 2024

A291755 Compound filter (multiplicative order of 2 mod 2n+1 & eulerphi(2n+1)): a(n) = P(A002326(n), A037225(n)), where P(n,k) is sequence A000027 used as a pairing function.

Original entry on oeis.org

1, 5, 25, 31, 61, 181, 265, 59, 261, 613, 142, 507, 761, 613, 1513, 566, 416, 607, 2521, 607, 1731, 1499, 607, 2301, 1912, 749, 5305, 1731, 1396, 6613, 7081, 826, 1723, 8581, 2102, 5391, 3169, 1731, 3946, 6709, 5725, 13285, 2493, 3431, 4764, 3415, 2356, 5707, 10201, 3946, 19801, 11527
Offset: 0

Views

Author

Antti Karttunen, Oct 02 2017

Keywords

Crossrefs

Cf. A000010, A000027, A002326, A037225, A291766 (rgs-version of this filter).
Cf. also A292249, A292268.

Programs

Formula

a(n) = (1/2)*(2 + ((A002326(n) + A000010(2n+1))^2) - A002326(n) - 3*A000010(2n+1)).

A291766 Restricted growth sequence transform of A291755; filter combining multiplicative order of 2 mod 2n+1 & eulerphi(2n+1) (A002326 & A037225).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 10, 14, 15, 16, 17, 18, 17, 19, 20, 17, 21, 22, 23, 24, 19, 25, 26, 27, 28, 29, 30, 31, 32, 33, 19, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 34, 45, 46, 29, 47, 48, 43, 49, 50, 41, 51, 52, 53, 45, 54, 55, 56, 57, 43, 58, 59, 60, 61, 49, 62, 63, 64, 51, 65, 66, 67, 68, 69, 53, 70, 71, 57, 72, 61, 73, 74, 75, 61
Offset: 0

Views

Author

Antti Karttunen, Oct 02 2017

Keywords

Crossrefs

Cf. A291769, A292267 for related filters.

Programs

  • PARI
    rgs_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(om,invec[i]), my(pp = mapget(om, invec[i])); outvec[i] = outvec[pp] , mapput(om,invec[i],i); outvec[i] = u; u++ )); outvec; };
    write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
    A002326(n) = if(n<0, 0, znorder(Mod(2, 2*n+1))); \\ This function from Michael Somos, Mar 31 2005
    A291755(n) = (1/2)*(2 + ((A002326(n)+eulerphi(n+n+1))^2) - A002326(n) - 3*eulerphi(n+n+1));
    write_to_bfile(0,rgs_transform(vector(32769,n,A291755(n-1))),"b291766_upto32768.txt");

A337712 Irregular triangle read by rows: row n gives the complete system of cycles of the doubling sequences modulo N = 2*n+1, for n >= 0.

Original entry on oeis.org

1, 2, 1, 2, 4, 3, 1, 2, 4, 3, 6, 5, 1, 2, 4, 8, 7, 5, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, 2, 4, 8, 7, 14, 13, 11, 1, 2, 4, 8, 16, 15, 13, 9, 3, 6, 12, 7, 14, 11, 5, 10, 1, 2, 4, 8, 16, 13, 7, 14, 9, 18, 17, 15, 11, 3, 6, 12, 5, 10
Offset: 0

Views

Author

Gary W. Adamson and Wolfdieter Lang, Oct 14 2020

Keywords

Comments

The length of row n is A037225(n), for n >= 0.
The doubling sequence modulo N = 2*n+1, for n >= 0, has entries DS(N, s(N,i), j) = s(N,i)*2^j (mod N), with j >= 0, and certain positive odd integer seeds s(N, i), for i = 1, 2, ..., S(N) = A037226((N-1)/2), where gcd(s(N, i), N) = 1 (restricted seeds modulo N). These doubling sequences are periodic with period length P(N) = A002326((N-1)/2) (order of 2 modulo N). Only the periods (cycles) {DS(N, s(N, i), j)}_{j=0..P(N)-1}, for i = 1, 2, ..., S(N), are listed.
N = 1 (n=0) is special: one takes here the restricted residue system modulo N not as [0] but as [1]. The order of 2 modulo 1 is 1, because 2^1 == 1 (mod 1) (== 0 (mod 1)).
In order to obtain the complete system of doubling sequences one starts with seed s(N, 1) = 1, and if all numbers from the smallest positive reduced residue system modulo N (called RRS(N), given in row N of A038566) are obtained, i.e., if P(N) = #RRS(N) = phi(N) = A000010(N), then the system is complete. Otherwise the smallest missing number from RRS(N) is taken as new seed s(N, 2), etc. until the system is complete. This means that the number of seeds needed is S(N) = phi(N)/P(N) = A037226((N-1)/2)).
The irregular subtriangle where only seed s(N, 1) = 1 has been used is given in A201908. But there 0 (not 1) for N = 1 has been used.
From Gary W. Adamson and Wolfdieter Lang, Dec 15 2020: (Start)
The cycles in row n, for N = 2*n + 1, of period length P(N) = A002326((N-1)/2) give the periods of the iterated doubling function D(x) = frac(2*x) with seeds x = s(N, i)/N, for i = 1, 2, ..., S(N) = A037226((N-1)/2), after multiplication with N. This is the doubling function used in the Devaney reference, pp. 24-25, 27, 125. 132, 171,289.
Each cycle in row n can also be used to find from the base 2 version of its first entry (the seed s = s(N, i)) divided by N the other entries by repeated application of a cyclic left shift by one step (called sigma operation) to the period of the base 2 expression of s/N. E.g., n = 7, N = 15, P(N) = 4, s = 1: (1/15){10->2} = .repeat(0001), then (.repeat(0010)){2->10} = 2/10, (.repeat(0100)){2->10} = 4/10 and (.repeat(1000)){2->10} = 8/15. Similarly for s = 7: from (7/15)_{10->2} = .repeat(0111) one obtains by repeated sigma operations 14/15, 13/15 and 11/15. The proof uses the elementary formulas for the conversion from base 10 to base 2, and the reverse one, from base 2 to base 10. See also a comment on the period length P(N) given in A002326. (End)

Examples

			The irregular triangle T(n, k) begins (cycles are separated by a vertical bar)
n,  N \ k 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 ...
0,  1:    1
1,  3:    1 2
2,  5:    1 2 4 3
3,  7:    1 2 4|3  6  5
4,  9:    1 2 4 8  7  5
5,  11:   1 2 4 8  5 10  9  7  3  6
6,  13:   1 2 4 8  3  6 12 11  9  5 10  7
7,  15:   1 2 4 8| 7 14 13 11
8,  17:   1 2 4 8 16 15 13  9| 7 14 11  5 10  3  6 12
9,  19:   1 2 4 8 16 13  7 14  9 18 17 15 11  3  6 12 5 10
10, 21:   1 2 4 8 16 11| 5 10 20 19 17 13
11, 23:   1 2 4 8 16  9 18 13  3  6 12| 5 10 20 17 11 22 21 19 15  7 14
12, 25:   1 2 4 8 16  7 14  3  6 12 24 23 21 17  9 18 11 22 19 13
13, 27:   1 2 4 8 16  5 10 20 13 26 25 23 19 11 22 17  7 14
...
n = 14, N = 29:  1 2 4 8 16  3  6 12 24 19  9 18  7 14 28 27 25 21 13 26 23 17  5 10 20 11 22 15,
n = 15, N = 31: 1 2 4 8 16|3 6 12 24 17|5 10 20 9 18|7 14 28 25 19|11 22 13 26 21|15 30 29 27 23.
		

References

  • Robert L. Devaney, A First Course in Chaotic Dynamical Systems, Addison-Wesley., 1992. pp. 24-25, 27, 125, 132, 171, 289. Second edition 2020.

Crossrefs

Cf. A000010, A002326, A037225, A037226, A201908, A038566, A334430 (modified doubling), A337936 (tripling), A339046 (quadrupling).

Programs

  • Mathematica
    Array[Block[{a = {}, k = 2, n = 2 # + 1, m}, m = EulerPhi[n]; While[Length@ Flatten@ a < m, AppendTo[a, Most@ NestWhileList[Mod[2 #, n] &, If[Length@ a == 0, 1, k], UnsameQ, All]]; Set[k, SelectFirst[Complement[Range[n], Union@ Flatten@ a], GCD[#, n] == 1 &] ]]; a] &, 9] // Flatten (* Michael De Vlieger, Nov 06 2020 *)

Formula

T(n, k) gives the k-th entry in the complete doubling system modulo N = 2*n+1, for n >= 0, with the S(N) = A037226((N-1)/2) cycles of length A002326((N-1)/2) written in row n. See the comment above for DS(N,s(N,i)), i = 1, 2, ..., S(N).
Showing 1-6 of 6 results.