A006694 -id:A006694 - cp's OEIS frontend

A060495 Each permutation in the list A060117 converted to Site Swap notation, with "zero throws" (fixed elements) replaced with n, the length of siteswap.

1, 11, 312, 111, 231, 222, 4413, 1313, 4112, 1111, 2411, 2312, 4242, 1241, 4233, 1223, 2222, 2231, 3441, 3342, 3131, 3122, 3423, 3333, 55514, 14514, 51414, 11314, 25314, 24414, 55113, 14113, 51112, 11111, 25111, 24112, 52512, 12511, 52413

Offset: 0

Antti Karttunen, Mar 21 2001

This sequence is not well-defined for n >= 3628800 because the Site Swap notation can contain values exceeding 9, for example, the Site Swap notation for a(3628800) is [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 10]. - Sean A. Irvine, Nov 25 2022

Site Swap notation explained.

Cf. factorial base representation A007623 and A060496, A006694.

See also A060498, A060499, A061417. Average of digits gives number of balls: A060501.

Perm2SiteSwap1 := proc(p) local ip,n,i,a; n := nops(p); ip := convert(invperm(convert(p,'disjcyc')),'permlist',n); a := []; for i from 1 to n do a := [op(a),((ip[i]-i) mod n)]; od; RETURN(a); end;
SiteSwap1ToDec := proc(s) local i,z,n; n := nops(s); z := 0; for i from 1 to n do z := 10*z; if(0 = s[i]) then z := z+n; else z := z+s[i]; fi; od; RETURN(z); end;

a(n) = SiteSwap1ToDec(Perm2SiteSwap1(PermUnrank3R(n))).

A037226 a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.

Original entry on oeis.org

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, 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, 2, 1, 2, 2, 4, 2, 1, 10, 4, 6, 3, 2, 4

Offset: 0

N. J. A. Sloane

nonn

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

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

T. D. Noe, Table of n, a(n) for n = 0..10000
Brillhart, John; Lomont, J. S.; Morton, Patrick. Cyclotomic properties of the Rudin-Shapiro polynomials, J. Reine Angew. Math.288 (1976), 37--65. See Table 2. MR0498479 (58 #16589).
Jarkko Peltomäki and Aleksi Saarela, Standard words and solutions of the word equation X_1^2 ... X_n^2 = (X_1 ... X_n)^2, Journal of Combinatorial Theory, Series A (2021) Vol. 178, 105340. See also arXiv:2004.14657 [cs.FL], 2020.

Cf. A000374 (number of irreducible factors of x^n - 1 over integers mod 2), A081844.

Cf. A006694 (cyclotomic cosets of 2 mod 2n+1).

a[n_] := EulerPhi[2n+1]/MultiplicativeOrder[2, 2n+1]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Dec 10 2015 *)

a(n)=eulerphi(2*n+1)/znorder(Mod(2,2*n+1)) \\ Charles R Greathouse IV, Dec 29 2013

a(n) = Sum{d|2n+1} mu((2n+1)/d) A000374(d), the inverse Mobius transform of A000374 - T. D. Noe, Aug 01 2003

a(n) = A037225(n)/A002326(n).

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

A160267 Minimum of A122458(n) and A160266(n).

Original entry on oeis.org

2, 1, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 1, 1, 1, 4, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 5, 1, 1, 1, 17, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 4, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 9, 1, 2, 1, 1, 1, 2, 1, 3, 1, 1, 1, 8, 1, 1, 1, 5, 1, 2, 1, 1, 1, 2, 1

Offset: 1

Vladimir Shevelev, May 07 2009, May 11 2009

nonn

Let f be the operation defined in A159885, namely f(2n+1) = A075677(n+1), and f^k its k-fold iteration.

Then a(n) is the smallest k such that either f^k(2n+1)< 2n+1 or A006694((f^k(2n+1)-1)/2) < A006694(n).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006694, A075677, A122458, A159885, A159945, A160198, A160266.

f(n) = ((3*((n-1)/2))+2)/A006519((3*((n-1)/2))+2); \\ Defined for odd n only. Cf. A075677.
A006519(n) = (1<A006694(n) = (sumdiv(2*n+1, d, eulerphi(d)/znorder(Mod(2, d))) - 1); \\ From A006694
A160267(n) = { my(w=A006694(n), u = (n+n+1), k=0); while((u >= (n+n+1))&&(A006694((u-1)/2) >= w), k++; u = f(u)); (k); }; \\ Antti Karttunen, Sep 22 2018

a(47) corrected and more terms appended by R. J. Mathar, Aug 08 2010

A138193 Odd composite numbers n for which A137576((n-1)/2)-1 is divisible by phi(n).

Original entry on oeis.org

9, 15, 25, 27, 33, 39, 49, 55, 57, 63, 81, 87, 95, 111, 119, 121, 125, 135, 143, 153, 159, 161, 169, 175, 177, 183, 201, 207, 209, 225, 243, 249, 287, 289, 295, 297, 303, 319, 321, 329, 335, 343, 351, 361, 369, 375, 391, 393, 407, 415, 417, 423, 447, 489, 497

Offset: 1

Vladimir Shevelev, May 04 2008

nonn

If p is an odd prime then A137576((p-1)/2)=p. Therefore the composite numbers n may be considered as quasiprimes. In particular, if (m,n)=1 we have a natural generalization of the little Fermat theorem: m^(A137576((n-1)/ 2)-1)=1 mod n.

			a(1)=9: A137576(4)=13 and 13-1 is divisible by phi(9)=6.

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

Cf. A137576, A002326, A006694.

A137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1];
okQ[n_] := OddQ[n] && CompositeQ[n] && Divisible[A137576[(n - 1)/2] - 1, EulerPhi[n]];
Reap[For[k = 1, k < 500, k += 2, If[okQ[k], Print[k]; Sow[k]]]][[2, 1]] (* Jean-François Alcover, Jan 11 2019 *)

Extended by Ray Chandler, May 08 2008

A138217 Odd numbers n for which A137576((n-1)/2)-1 is a multiple of A000010(n).

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 53, 55, 57, 59, 61, 63, 67, 71, 73, 79, 81, 83, 87, 89, 95, 97, 101, 103, 107, 109, 111, 113, 119, 121, 125, 127, 131, 135, 137, 139, 143, 149, 151, 153, 157, 159, 161, 163, 167, 169, 173

Offset: 1

Vladimir Shevelev, May 05 2008

nonn

The sequence contains all odd primes. Indeed, if p is a prime then A137576((p-1)/2)-1=p-1=A000010(p).
Conjecture: the sequence contains infinitely many composite numbers.
The conjecture is true because of the sequence contains all powers of odd primes. Indeed, A137576((P^k-1)/2)-1=k*A000010(p^k). - Vladimir Shevelev, May 29 2008

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

Cf. A137576, A000010, A002326, A006694.

A137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1];
okQ[n_] := OddQ[n] && Divisible[A137576[(n - 1)/2] - 1, EulerPhi[n]];
Reap[For[k = 1, k < 200, k += 2, If[okQ[k], Sow[k]]]][[2, 1]] (* Jean-François Alcover, Jan 11 2019 *)

Extended by Ray Chandler, May 08 2008

A138227 Odd positive integers n for which A137576((n-1)/2)-1 is not a multiple of A000010(n).

Original entry on oeis.org

21, 35, 45, 51, 65, 69, 75, 77, 85, 91, 93, 99, 105, 115, 117, 123, 129, 133, 141, 145, 147, 155, 165, 171, 185, 187, 189, 195, 203, 205, 213, 215, 217, 219, 221, 231, 235, 237, 245, 247, 253, 255, 259, 261, 265, 267, 273, 275, 279, 285, 291, 299, 301, 305

Offset: 1

Vladimir Shevelev, May 05 2008

nonn

All terms are composite numbers since if p is an odd prime then A137576((p-1)/2)-1=p-1=A000010(p).

Conjecture. This sequence is infinite.

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

Cf. A137576, A000010, A002326, A006694.

A137576[n_] := With[{t = MultiplicativeOrder[2, 2 n + 1]}, t*DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1]; Select[Range[1, 1000, 2], !Divisible[A137576[(# - 1)/2] - 1, EulerPhi[#]]&] (* Jean-François Alcover, Dec 07 2015 *)

is(n)=my(t); n%2 && (sumdiv(n,d,eulerphi(d)/(t=znorder(Mod(2, d))))*t-t)%eulerphi(n)>0 \\ Charles R Greathouse IV, Feb 20 2013

Extended by Ray Chandler, May 08 2008

A060496 Each permutation in the list A060117 converted to Site Swap notation, with digits reversed. "Zero throws" (fixed elements) indicated with 0's.

Original entry on oeis.org

0, 11, 210, 111, 102, 222, 3100, 3131, 2110, 1111, 1102, 2132, 2020, 1021, 3320, 3221, 2222, 1322, 1003, 2033, 1313, 2213, 3203, 3333, 41000, 41041, 41410, 41311, 41302, 41442, 31100, 31141, 21110, 11111, 11102, 21142, 21020, 11021, 31420

Offset: 0

Antti Karttunen, Mar 21 2001

This sequence is not well-defined for n >= 3628800 because the Site Swap notation can contain values exceeding 9, for example, the Site Swap notation for a(3628800) is [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 10]. - Sean A. Irvine, Nov 25 2022

Site Swap notation explained.

Cf. factorial base representation A007623 and A060495, A006694.

In A060498 the digits are also "inverted", giving valid siteswap juggling patterns.

SiteSwap2ToDec := proc(s) local i,z; z := 0; for i from nops(s) by -1 to 1 do z := 10*z + s[i]; od; RETURN(z); end;

a(n) = SiteSwap2ToDec(Perm2SiteSwap1(PermUnrank3R(n))).

A064287 Number of cyclotomic cosets C of 2 mod 2n+1 such that -C is not equal to C, divided by 2.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 0, 2, 0, 1, 0, 0, 2, 1, 2, 2, 0, 1, 0, 0, 0, 5, 0, 0, 2, 1, 4, 2, 2, 1, 0, 0, 4, 1, 4, 4, 6, 1, 0, 0, 0, 1, 6, 0, 0, 1, 0, 2, 4, 3, 0, 2, 0, 9, 0, 0, 4, 3, 0, 0, 2, 1, 0, 4, 0, 5, 4, 6, 0, 1, 4, 0, 4, 1, 0, 0, 0, 3, 0, 0, 0, 1, 0, 2, 8, 1, 0, 6, 0, 1, 0, 2, 0, 3, 0, 0

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 {1, 2, 4, 8} and {7, 14, 13, 11} have the desired property, so a(7) = 2/2 = 1.

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

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

Extended by Ray Chandler, Apr 25 2008

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

N. J. A. Sloane, Apr 11 2003

nonn

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

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

T. D. Noe, Table of n, a(n) for n = 0..10000
Jean-Paul Allouche, Manon Stipulanti, and Jia-Yan Yao, Doubling modulo odd integers, generalizations, and unexpected occurrences, arXiv:2504.17564 [math.NT], 2025.
G. Chassé, Combinatorial cycles of a polynomial map over a commutative field, Discrete Math. 61 (1986), 21-26.
E. W. Clark and J. J. Liang, Enumeration of finite commutative chain rings, J. Algebra 27 (1973), 445-453.
Pieter Moree, Number of irreducible factors of x^n-1 over a finite field, Posting to Number Theory List, Apr 11, 2003.
T. D. Rogers, The graph of the square mapping on the prime fields, Discrete Math. 148 (1996), 317-324
D. Ulmer, Elliptic curves with large rank over function fields, Ann. of Math. 155 (2002), 295-315
D. Ulmer, Elliptic curves with large rank over function fields, arXiv:math/0109163 [math.NT].
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.

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

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(%);

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 *)

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

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

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

cp's OEIS Frontend

A060495 Each permutation in the list A060117 converted to Site Swap notation, with "zero throws" (fixed elements) replaced with n, the length of siteswap.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A037226 a(n) = phi(2n+1) / multiplicative order of 2 mod 2n+1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A160267 Minimum of A122458(n) and A160266(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A138193 Odd composite numbers n for which A137576((n-1)/2)-1 is divisible by phi(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A138217 Odd numbers n for which A137576((n-1)/2)-1 is a multiple of A000010(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A138227 Odd positive integers n for which A137576((n-1)/2)-1 is not a multiple of A000010(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A060496 Each permutation in the list A060117 converted to Site Swap notation, with digits reversed. "Zero throws" (fixed elements) indicated with 0's.

Views

Author