A101208 -id:A101208 - cp's OEIS frontend

A001917 (p-1)/x, where p = prime(n) and x = ord(2,p), the smallest positive integer such that 2^x == 1 (mod p).

1, 1, 2, 1, 1, 2, 1, 2, 1, 6, 1, 2, 3, 2, 1, 1, 1, 1, 2, 8, 2, 1, 8, 2, 1, 2, 1, 3, 4, 18, 1, 2, 1, 1, 10, 3, 1, 2, 1, 1, 1, 2, 2, 1, 2, 1, 6, 1, 3, 8, 2, 10, 5, 16, 2, 1, 2, 3, 4, 3, 1, 3, 2, 2, 1, 11, 16, 1, 1, 4, 2, 2, 1, 1, 2, 1, 9, 2, 2, 1, 1, 10, 6, 6, 1, 2, 6, 1, 2, 1, 2, 2, 1, 3, 2, 1, 2, 1, 1, 1, 1, 1, 2

Offset: 2

N. J. A. Sloane

Also number of cycles in permutations constructed from siteswap juggling pattern 1234...p.
Also the number of irreducible polynomial factors for the polynomial (x^p-1)/(x-1) over GF(2), where p is the n-th prime. - V. Raman, Oct 04 2012
The sequence is unbounded: for any value of M, there exists an element of the sequence divisible by M. See the proof by David Speyer below. - Shreevatsa R, May 24 2013

M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 1, p. 131.
D. H. Lehmer, Guide to Tables in the Theory of Numbers. Bulletin No. 105, National Research Council, Washington, DC, 1941, pp. 7-10.
W. Meissner, Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte Königlich Preussischen Akadamie Wissenschaften Berlin, 35 (1913), 663-667.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 2..10000
I. Anderson and D. A. Preece, Combinatorially fruitful properties of 3*2^(-1) and 3*2^(-2) modulo p, Discr. Math., 310 (2010), 312-324.
Keith Conrad, Wieferich primes, Univ. Conn. (2023).
W. Meissner, Über die Teilbarkeit von 2^p-2 durch das Quadrat der Primzahl p = 1093, Sitzungsberichte Königlich Preussischen Akadamie Wissenschaften Berlin, 35 (1913), 663-667. [Annotated scanned copy]
V. Papadimitriou, The l_2^(p) and the ... ratio of the first hundred million primes
David Speyer, Can the order of 2 mod p be arbitrarily small (relative to p-1)?

Cf. A006694 gives cycle counts of such permutations constructed for all odd numbers.
Cf. A002323, A001122, A115591, A001133, A001134, A001135, A001136, A101208.
Cf. A014664.

[ (p-1)/Modorder(2, p) where p is NthPrime(n): n in [2..100] ]; // Klaus Brockhaus, Dec 09 2008

with(numtheory); [seq((ithprime(n)-1)/order(2,ithprime(n)),n=2..130)];
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(ithprime(j)-1),'disjcyc')),j=2..)];

a6694[n_] := Sum[ EulerPhi[d] / MultiplicativeOrder[2, d], {d, Divisors[2n + 1]}] - 1; a[n_] := a6694[(Prime[n]-1)/2]; Table[ a[n], {n, 2, 104}] (* Jean-François Alcover, Dec 14 2011, after Vladimir Shevelev *)
Table[p = Prime[n]; (p - 1)/MultiplicativeOrder[2, p], {n, 2, 100}] (* T. D. Noe, Apr 11 2012 *)
ord[n_]:=Module[{x=1},While[PowerMod[2,x,n]!=1,x++];(n-1)/x]; ord/@ Prime[ Range[ 2,110]] (* Harvey P. Dale, Jun 25 2014 *)

{for(n=2, 100, p=prime(n); print1((p-1)/znorder(Mod(2, p)), ","))} \\ Klaus Brockhaus, Dec 09 2008

from sympy import prime, n_order
def A001917(n):
    p = prime(n)
    return 1 if n == 2 else (p-1)//n_order(2,p) # Chai Wah Wu, Jan 15 2020

From Vladimir Shevelev, May 26 2008: (Start)
a(n) = A006694((p_n-1)/2) where p_n is the n-th odd prime.
Conjecture: k*a(n) = A006694(((p_n)^k-1)/2). (End)

Additional comments from Antti Karttunen, Jan 05 2000

More terms from N. J. A. Sloane, Dec 24 2009

A054471 Smallest prime p having n different cycles in decimal expansions of k/p, k=1..p-1.

Original entry on oeis.org

7, 3, 103, 53, 11, 79, 211, 41, 73, 281, 353, 37, 2393, 449, 3061, 1889, 137, 2467, 16189, 641, 3109, 4973, 11087, 1321, 101, 7151, 7669, 757, 38629, 1231, 49663, 12289, 859, 239, 27581, 9613, 18131, 13757, 33931, 9161, 118901, 6763, 18233

Offset: 1

Robert G. Wilson v, 1994; Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), May 22 2000

First cyclic number of n-th degree (or n-th order): the reciprocals of these numbers belong to one of n different cycles. Each cycle has (a(n) - 1)/n digits.
From Robert G. Wilson v, Aug 21 2014: (Start)
recursive by indices:
 1,    7,        211,            79337,    634776923741, ...
 2,    3,        103,          2368589, 785245568161181, ...
 4,   53,     135257,    2332901103899, ...
 5,   11,        353,          3795457, 693814982285339, ...
 6,   79,      26861,      23947548497, ...
 8,   41,     118901,    1015118238709, ...
 9,   73,     142789,     267291583927, ...
10,  281,    3097183,   66880786504811, ...
12,   37,      18131,     105385168331, ...
13, 2393,   11160953, 7140939250711817, ...
14, 4999, 2148340247,          > 10^19,
... .
(End)

John H. Conway and R. K. Guy, The Book of Numbers, Copernicus Press, p. 162.
M. Gardner, Mathematical Circus, Cambridge University Press (1996).

Robert G. Wilson v, Table of n, a(n) for n = 1..65000 (first 1000 terms from _T. D. Noe_)
H. Richter, The period length of the decimal expansion of a fraction
Index entries for sequences related to decimal expansion of 1/n

First time n appears in A006556.
Cf. A006883, A097443, A055628, A056157, A056210, A056211, A056212, A056213, A056214, A056215, A056216, A056217, A098680, which are sequences of primes p where the period of the reciprocal is (p-1)/n for n=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.
Cf. A101208, A101209 (similar sequences for base 2 and base 3).

a[n_Integer] := Block[{m = If[ OddQ@ n, 2n, n]}, p = m +1; While[ !PrimeQ@ p || p != 1 + n*MultiplicativeOrder[10, p], p = p += m]; p]; a[1] = 7; a[4] = 53; Array[f, 50] (* Robert G. Wilson v, Apr 19 2005; revised Aug 20 2014 and Feb 14 2025 *)

More terms from David W. Wilson, May 22 2000

A101209 Smallest odd prime p such that n=(p-1)/ord_p(3).

Original entry on oeis.org

5, 11, 67, 13, 41, 61, 883, 313, 271, 431, 5743, 193, 3511, 1583, 2131, 433, 2551, 4177, 8513, 2521, 8779, 683, 10627, 1321, 29851, 1223, 3079, 9661, 49939, 661, 101681, 4129, 42703, 2857, 15401, 1621, 2887, 7297, 547, 13441, 73637, 11173

Offset: 1

Leigh Ellison (le(AT)maths.gla.ac.uk), Dec 14 2004

nonn

Cf. A101208.

A372797 Smallest prime p such that the multiplicative order of 4 modulo p is 2*n, or 0 if no such prime exists.

Original entry on oeis.org

3, 17, 31, 73, 151, 433, 631, 337, 127, 241, 331, 601, 4421, 673, 3061, 257, 1429, 1657, 1103, 3121, 2143, 1321, 18539, 1777, 2351, 37441, 2971, 2857, 3191, 17401, 683, 15809, 17029, 9929, 38431, 1801, 11471, 63689, 49999, 13121, 17467, 21169, 83077, 25609, 5581, 5153, 26227

Offset: 1

Jianing Song, May 13 2024

nonn

First prime p such that the expansion of 1/p has period (p-1)/(2*n) in base 4. Also the first prime p such that {k/p : 1 <= k <= p-1} has 2*n different cycles when written out in base 4.

Since ord(a^m,k) = ord(a,k)/gcd(m,ord(a,k)) for gcd(a,k) = 1, we have that (p-1)/ord(4,p) = ((p-1)/ord(2,p)) * gcd(2,ord(2,p)) is always even. Here ord(a,k) is the multiplicative order of a modulo k.

			In the following examples let () denote the reptend. The prime numbers themselves and the fractions are written out in decimal.
The base-4 expansion of 1/3 is 0.(1), so the reptend has length 1 = (3-1)/2. Also, the base-4 expansions of 1/3 = 0.(1) and 2/3 = 0.(2) have two cycles 1 and 2. 3 is the smallest such prime, so a(1) = 3.
The base-4 expansion of 1/17 is 0.(0033), so the reptend has length 4 = (17-1)/4. Also, the base-4 expansions of 1/17, 2/17, ..., 16/17 have four cycles 0033, 0132, 1023 and 1122. 17 is the smallest such prime, so a(2) = 17.
The base-4 expansion of 1/31 is 0.(00133), so the reptend has length 5 = (31-1)/6. Also, the base-4 expansions of 1/31, 2/31, ..., 30/31 have three cycles 00201, 01203, 02211, 03213, 11223 and 13233. 13 is the smallest such prime, so a(3) = 13.

Jean-François Alcover, Table of n, a(n) for n = 1..1000

Cf. A082654, A216371.

In other bases: A101208, A101209, A372798, A372799, A054471, A372800.

a[n_] := a[n] = For[p = 2, True, p = NextPrime[p], If[MultiplicativeOrder[4, p] == (p-1)/(2n), Return[p]]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 24 2024 *)

a(n,{base=4}) = forprime(p=2, oo, if((base%p) && znorder(Mod(base,p)) == (p-1)/(n * if(issquare(base), 2, 1)), return(p)))

A372798 Smallest prime p such that the multiplicative order of 8 modulo p is n, or 0 if no such prime exists.

Original entry on oeis.org

3, 17, 13, 113, 251, 7, 1163, 89, 109, 431, 1013, 577, 4421, 953, 571, 257, 4523, 127, 15467, 3761, 3109, 7151, 18539, 73, 25301, 14327, 2971, 42953, 72269, 151, 683, 12641, 331, 2687, 42701, 5113, 18797, 1103, 8581, 13121, 172283, 631, 221021, 120737, 3061, 5153, 217517

Offset: 1

Jianing Song, May 13 2024

nonn

First prime p such that the expansion of 1/p has period (p-1)/n in base 8. Also the first prime p such that {k/p : 1 <= k <= p-1} has n different cycles when written out in base 8.

			In the following examples let () denote the reptend. The prime numbers themselves and the fractions are written out in decimal.
The base-8 expansion of 1/3 is 0.(25), so the reptend has length 2 = (3-1)/1. Also, the base-8 expansions of 1/3 = 0.(25) and 2/3 = 0.(52) have only one cycle 25. 3 is the smallest such prime, so a(1) = 3.
The base-8 expansion of 1/17 is 0.(03607417), so the reptend has length 8 = (17-1)/2. Also, the base-8 expansions of 1/17, 2/17, ..., 16/17 have two cycles 03607417 and 13226455. 17 is the smallest such prime, so a(2) = 17.
The base-8 expansion of 1/13 is 0.(0473), so the reptend has length 4 = (13-1)/3. Also, the base-8 expansions of 1/13, 2/13, ..., 12/13 have three cycles 0473, 1166 and 2354. 13 is the smallest such prime, so a(3) = 13.

Jean-François Alcover, Table of n, a(n) for n = 1..1000

Cf. A211244.

In other bases: A101208, A101209, A372797, A372798, A372799, A054471, A372800.

a[n_] := a[n] = For[p = 2, True, p = NextPrime[p], If[MultiplicativeOrder[8, p] == (p-1)/n, Return[p]]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 24 2024 *)

a(n,{base=8}) = forprime(p=2, oo, if((base%p) && znorder(Mod(base,p)) == (p-1)/(n * if(issquare(base), 2, 1)), return(p)))

A372799 Smallest prime p such that the multiplicative order of 9 modulo p is 2*n, or 0 if no such prime exists.

Original entry on oeis.org

5, 13, 67, 313, 41, 61, 883, 433, 271, 2161, 683, 193, 1223, 8317, 2131, 769, 2551, 1621, 8513, 2521, 8779, 4357, 5843, 3889, 7451, 16069, 3079, 19993, 14327, 661, 23747, 95617, 42703, 2857, 15401, 17209, 2887, 7297, 547, 13441, 4019, 757, 41453, 29833, 54631, 31741, 20399

Offset: 1

Jianing Song, May 13 2024

nonn

First prime p such that the expansion of 1/p has period (p-1)/(2*n) in base 9. Also the first prime p such that {k/p : 1 <= k <= p-1} has 2*n different cycles when written out in base 9.

Since ord(a^m,k) = ord(a,k)/gcd(m,ord(a,k)) for gcd(a,k) = 1, we have that (p-1)/ord(9,p) = ((p-1)/ord(3,p)) * gcd(2,ord(3,p)) is always even. Here ord(a,k) is the multiplicative order of a modulo k.

			In the following examples let () denote the reptend. The prime numbers themselves and the fractions are written out in decimal.
The base-9 expansion of 1/5 is 0.(17), so the reptend has length 2 = (5-1)/2. Also, the base-9 expansions of 1/5 = 0.(17), 2/5 = (0.35), 3/5 = 0.(53) and 4/5 = 0.(71) have two cycles 17 and 35. 5 is the smallest such prime, so a(1) = 5.
The base-9 expansion of 1/13 is 0.(062), so the reptend has length 3 = (13-1)/4. Also, the base-9 expansions of 1/13, 2/13, ..., 12/13 have four cycles 062, 134, 268 and 475. 13 is the smallest such prime, so a(2) = 13.
The base-9 expansion of 1/67 is 0.(01178285332), so the reptend has length 11 = (67-1)/6. Also, the base-9 expansions of 1/67, 2/67, ..., 66/67 have six cycles 01178285332, 02367581664, 03556877106, 04746273438, 07224865213 and 08414261545. 67 is the smallest such prime, so a(3) = 67.

Jean-François Alcover, Table of n, a(n) for n = 1..1000

Cf. A211245, A364867.

In other bases: A101208, A101209, A372797, A372798, A054471, A372800.

a[n_] := a[n] = For[p = 2, True, p = NextPrime[p], If[MultiplicativeOrder[9, p] == (p-1)/(2n), Return[p]]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 24 2024 *)

a(n,{base=9}) = forprime(p=2, oo, if((base%p) && znorder(Mod(base,p)) == (p-1)/(n * if(issquare(base), 2, 1)), return(p)))

A372800 Smallest prime p such that the multiplicative order of 16 modulo p is 2*n, or 0 if no such prime exists.

Original entry on oeis.org

3, 5, 31, 17, 151, 109, 631, 113, 127, 1181, 331, 433, 13963, 1709, 3331, 1217, 2687, 397, 1103, 241, 2143, 1013, 18539, 1777, 2351, 4421, 2971, 673, 3191, 3061, 683, 257, 58147, 1429, 38431, 1657, 11471, 22573, 49999, 3121, 17467, 33013, 252583, 1321, 23671, 51797, 26227, 4513

Offset: 1

Jianing Song, May 13 2024

nonn

First prime p such that the expansion of 1/p has period (p-1)/(2*n) in base 16. Also the first prime p such that {k/p : 1 <= k <= p-1} has 2*n different cycles when written out in base 16.

Since ord(a^m,k) = ord(a,k)/gcd(m,ord(a,k)) for gcd(a,k) = 1, we have that (p-1)/ord(16,p) = ((p-1)/ord(2,p)) * gcd(4,ord(2,p)) is always even. Here ord(a,k) is the multiplicative order of a modulo k.

			In the following examples let () denote the reptend. The prime numbers themselves and the fractions are written out in decimal.
The base-16 expansion of 1/3 is 0.(5), so the reptend has length 1 = (3-1)/2. Also, the base-16 expansions of 1/3 = 0.(5) and 2/3 = 0.(A) have two cycles 5 and A. 3 is the smallest such prime, so a(1) = 3.
The base-16 expansion of 1/5 is 0.(3), so the reptend has length 1 = (5-1)/4. Also, the base-16 expansions of 1/5 = 0.(3), 2/5 = (0.6), 3/5 = 0.(9) and 4/5 = 0.(C) have four cycles 3, 6, 9 and A. 5 is the smallest such prime, so a(2) = 5.
The base-16 expansion of 1/31 is 0.(08421), so the reptend has length 5 = (31-1)/6. Also, the base-16 expansions of 1/31, 2/31, ..., 30/31 have six cycles 08421, 18C63, 294A5, 39CE7, 5AD6B and 7BDEF. 31 is the smallest such prime, so a(3) = 31.

Jean-François Alcover, Table of n, a(n) for n = 1..1000

Cf. A372801.

In other bases: A101208, A101209, A372797, A372798, A372799, A054471.

a[n_] := a[n] = For[p = 2, True, p = NextPrime[p], If[MultiplicativeOrder[16, p] == (p-1)/(2n), Return[p]]];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 100}] (* Jean-François Alcover, Nov 24 2024 *)

a(n,{base=16}) = forprime(p=2, oo, if((base%p) && znorder(Mod(base,p)) == (p-1)/(n * if(issquare(base), 2, 1)), return(p)))

A347772 Square array read by antidiagonals downwards: T(n,k) is the smallest prime p not dividing n such that (p-1) / ord_p(n) = k (n>=2, k>=1), or 0 if no such p exists.

Original entry on oeis.org

3, 7, 2, 43, 11, 0, 113, 67, 3, 2, 251, 13, 0, 11, 11, 31, 41, 17, 13, 19, 2, 1163, 61, 0, 101, 7, 3, 3, 73, 883, 31, 0, 5, 73, 17, 2, 397, 313, 0, 199, 31, 29, 13, 5, 7, 151, 271, 73, 827, 139, 1031, 113, 0, 3, 2, 331, 431, 0, 569, 463, 19, 251, 13, 103, 7, 5, 1753, 5743, 151, 487, 97, 43

Offset: 2

Eric Chen, Sep 14 2021

			Table begins:
  n\k |  1   2    3    4     5    6     7    8    9    10    11    12
  ----+--------------------------------------------------------------
   2  |  3   7   43  113   251   31  1163   73  397   151   331  1753
   3  |  2  11   67   13    41   61   883  313  271   431  5743   193
   4  |  0   3    0   17     0   31     0   73    0   151     0   433
   5  |  2  11   13  101     0  199   827  569  487    31  1453   181
   6  | 11  19    7    5    31  139   463   97   37   101   353   241
   7  |  2   3   73   29  1031   19    43  113  883   311   353  1453
   8  |  3  17   13  113   251    7  1163   89  109   431  1013   577
   9  |  2   5    0   13     0   67     0  313    0    41     0    61
  10  |  7   3  103   53    11   79   211   41   73   281   353    37
  11  |  2   7  193    5   191   19   379  449  199  1301  2531  1549
  12  |  5  23   19   37   271   13    29  193  487    11    89   373
  ...

Row 2: A101208.
Row 3: A101209.
Row 10: A054471.
Column 1: A056619.

a(m, n)=forprime(p=2, 2^40, if(gcd(m, p)==1 && znorder(Mod(m, p))==(p-1)/n, return(p)))
is(m, n)=p=core(m); if(p>1 && p%4==1 && n%p==0 && n%2, return(1)); 0
A347772(m, n)=if(is(m, n) || (issquare(m) && n%2 && (m%2==0 || n>1)), 0, a(m, n))

T(n,k) = 0 if n is square, k is odd, n > 1.
T(n,k) = 0 if n is even square, k is odd.
T(n,k) = 0 if (let n' be the squarefree part (A007913) of n) n' == 1 (mod 4), n' > 1, k is divisible by n', k is odd.
T(27,k) = 0 for k == 4 or 8 (mod 12).
T(n,k) == 1 mod k if nonzero.

cp's OEIS Frontend

A001917 (p-1)/x, where p = prime(n) and x = ord(2,p), the smallest positive integer such that 2^x == 1 (mod p).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A054471 Smallest prime p having n different cycles in decimal expansions of k/p, k=1..p-1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Extensions

A101209 Smallest odd prime p such that n=(p-1)/ord_p(3).

Views

Author

Keywords

Crossrefs

A372797 Smallest prime p such that the multiplicative order of 4 modulo p is 2*n, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A372798 Smallest prime p such that the multiplicative order of 8 modulo p is n, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A372799 Smallest prime p such that the multiplicative order of 9 modulo p is 2*n, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A372800 Smallest prime p such that the multiplicative order of 16 modulo p is 2*n, or 0 if no such prime exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A347772 Square array read by antidiagonals downwards: T(n,k) is the smallest prime p not dividing n such that (p-1) / ord_p(n) = k (n>=2, k>=1), or 0 if no such p exists.

Views

Author