A112927 -id:A112927 - cp's OEIS frontend

A379642 Smallest primitive prime factor of 9^n-1.

2, 5, 7, 41, 11, 73, 547, 17, 19, 1181, 23, 6481, 398581, 29, 31, 21523361, 103, 530713, 1597, 42521761, 43, 5501, 47, 97, 151, 53, 109, 430697, 59, 47763361, 683, 926510094425921, 25411, 956353, 71, 282429005041, 18427, 5301533, 79, 14401, 83, 2857, 431, 89

Offset: 1

Sean A. Irvine, Dec 28 2024

nonn

Also, smallest prime p such that 1/p has nonary period n.

Max Alekseyev, Table of n, a(n) for n = 1..730 (first 690 terms from Sean A. Irvine)

Cf. A112927 (base 2), A143663 (base 3), A112092 (base 4), A143665 (base 5), A379639 (base 6), A379640 (base 7), A379641 (base 8), A379642 (base 9), A007138 (base 10), A379644 (base 11), A252170 (base 12).

Cf. A274909.

listap(nn) = {prf = []; for (n=1, nn, vp = (factor(9^n-1)[, 1])~; f = setminus(Set(vp), Set(prf)); prf = concat(prf, f); print1(vecmin(Vec(f)), ", "); ); }

A086251 Number of primitive prime factors of 2^n - 1.

Original entry on oeis.org

0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 3, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 1, 2, 1, 3, 2, 2, 1, 3, 2, 1, 2, 3, 3, 3, 1, 3, 1, 2, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 3, 1, 2, 3, 2, 3, 2, 2, 3, 1, 1, 3, 1, 3, 2, 2, 2, 1, 1, 2, 2, 1, 1, 3, 4, 1, 2, 3, 2, 2, 1, 3, 3, 2, 3, 2, 2, 3

Offset: 1

T. D. Noe, Jul 14 2003

A prime factor of 2^n - 1 is called primitive if it does not divide 2^r - 1 for any r < n. Equivalently, p is a primitive prime factor of 2^n - 1 if ord(2,p) = n. Zsigmondy's theorem says that there is at least one primitive prime factor for n > 1, except for n=6. See A086252 for those n that have a record number of primitive prime factors.
Number of odd primes p such that A002326((p-1)/2) = n. Number of occurrences of number n in A014664. - Thomas Ordowski, Sep 12 2017
The prime factors are not counted with multiplicity, which matters for a(364)=4 and a(1755)=6. - Jeppe Stig Nielsen, Sep 01 2020

			a(11) = 2 because 2^11 - 1 = 23*89 and both 23 and 89 have order 11.

Table of n, a(n) for n = 1..1206
Eric Weisstein's World of Mathematics, Zsigmondy Theorem

Cf. A046800, A046051 (number of prime factors, with repetition, of 2^n-1), A086252, A002588, A005420, A002184, A046801, A049093, A049094, A059499, A085021, A097406, A112927, A237043.

Join[{0}, Table[cnt=0; f=Transpose[FactorInteger[2^n-1]][[1]]; Do[If[MultiplicativeOrder[2, f[[i]]]==n, cnt++ ], {i, Length[f]}]; cnt, {n, 2, 200}]]

a(n) = sumdiv(n, d, moebius(n/d)*omega(2^d-1)); \\ Michel Marcus, Sep 12 2017

a(n) = my(m=polcyclo(n, 2)); omega(m/gcd(m,n)) \\ Jeppe Stig Nielsen, Sep 01 2020

a(n) = Sum{d|n} mu(n/d) A046800(d), inverse Mobius transform of A046800.
a(n) <= A182590(n). - Thomas Ordowski, Sep 14 2017
a(n) = A001221(A064078(n)). - Thomas Ordowski, Oct 26 2017

Terms to a(500) in b-file from T. D. Noe, Nov 11 2010
Terms a(501)-a(1200) in b-file from Charles R Greathouse IV, Sep 14 2017
Terms a(1201)-a(1206) in b-file from Max Alekseyev, Sep 11 2022

A379639 Smallest primitive prime factor of 6^n-1.

Original entry on oeis.org

5, 7, 43, 37, 311, 31, 55987, 1297, 19, 11, 23, 13, 3433, 29, 1171, 17, 239, 46441, 191, 241, 1822428931, 51828151, 47, 1678321, 18198701, 53, 163, 421, 7369130657357778596659, 1950271, 5333, 353, 67, 190537, 71, 73, 149, 1787, 3143401, 41, 8648131, 2527867231

Offset: 1

Sean A. Irvine, Dec 28 2024

nonn

Also, smallest prime p such that 1/p has senary period n.

Max Alekseyev, Table of n, a(n) for n = 1..436 (first 420 terms from Sean A. Irvine)

Cf. A112927 (base 2), A143663 (base 3), A112092 (base 4), A143665 (base 5), A379639 (base 6), A379640 (base 7), A379641 (base 8), A379642 (base 9), A007138 (base 10), A379644 (base 11), A252170 (base 12).

Cf. A274907.

listap(nn) = {prf = []; for (n=1, nn, vp = (factor(6^n-1)[, 1])~; f = setminus(Set(vp), Set(prf)); prf = concat(prf, f); print1(vecmin(Vec(f)), ", "); ); }

A379644 Smallest primitive prime factor of 11^n-1.

Original entry on oeis.org

2, 3, 7, 61, 3221, 37, 43, 7321, 1772893, 13421, 15797, 13, 1093, 1623931, 195019441, 17, 50544702849929377, 590077, 6115909044841454629, 212601841, 1723, 23, 829, 10657, 3001, 53, 5559917315850179173, 29, 523, 31, 50159, 51329, 661, 71707, 211, 3138426605161

Offset: 1

Sean A. Irvine, Dec 28 2024

nonn

Also, smallest prime p such that 1/p has undecimal period n.

Max Alekseyev, Table of n, a(n) for n = 1..330 (first 253 terms from Sean A. Irvine)

Cf. A112927 (base 2), A143663 (base 3), A112092 (base 4), A143665 (base 5), A379639 (base 6), A379640 (base 7), A379641 (base 8), A379642 (base 9), A007138 (base 10), A379644 (base 11), A252170 (base 12).

Cf. A274910.

listap(nn) = {prf = []; for (n=1, nn, vp = (factor(11^n-1)[, 1])~; f = setminus(Set(vp), Set(prf)); prf = concat(prf, f); print1(vecmin(Vec(f)), ", "); ); }

A144755 Primes which divide none of overpseudoprimes to base 2 (A141232).

Original entry on oeis.org

2, 3, 5, 7, 11, 13, 17, 19, 31, 41, 43, 73, 127, 151, 241, 257, 331, 337, 683, 2731, 5419, 8191, 43691, 61681, 65537, 87211, 131071, 174763, 262657, 524287, 599479, 2796203, 15790321, 18837001, 22366891, 715827883, 2147483647, 4278255361

Offset: 1

Vladimir Shevelev, Sep 20 2008

nonn

Odd prime p is in the sequence iff A064078(A002326((p-1)/2))=p. For example, for p=127 we have A002326((127-1)/2)=7 and A064078(7)=127. Thus p=127 is in the sequence.
Primes p such that the binary expansion of 1/p has a unique period length; that is, no other prime has the same period. Sequence A161509 sorted. - T. D. Noe, Apr 13 2010
Since A161509 has terms of varying magnitude, sorting any finite initial segment of A161509 cannot provide a guarantee that there are no other terms missed in between. Any prime p not (yet) appearing in A161509 should be tested via A064078(A002326((p-1)/2))=p to conclude whether it belongs to the current sequence. - Max Alekseyev, Feb 10 2024

			Overpseudoprimes to base 2 are odd, then a(1)=2.

Cf. A141232, A002326, A064078, A112927.

Cf. A040017 (unique-period primes in base 10). - T. D. Noe, Apr 13 2010

b=2; t={}; Do[c=Cyclotomic[n,b]; q=c/GCD[n,c]; If[PrimePowerQ[q], p=FactorInteger[q][[1,1]]; If[p<10^12, AppendTo[t,p]; Print[{n,p}]]], {n,1000}]; t=Sort[t] (* T. D. Noe, Apr 13 2010 *)

{ is_a144755(p) = my(q,m,g); q=znorder(Mod(2,p)); m=2^q-1; fordiv(q,d, if(d1,m\=g))); m==p; } \\ Max Alekseyev, Feb 10 2024

Extended by T. D. Noe, Apr 13 2010

b-file deleted by Max Alekseyev, Feb 10 2024.

A097406 Largest primitive prime factor of 2^n-1, or a(n) = 1 if no such prime exists.

Original entry on oeis.org

1, 3, 7, 5, 31, 1, 127, 17, 73, 11, 89, 13, 8191, 43, 151, 257, 131071, 19, 524287, 41, 337, 683, 178481, 241, 1801, 2731, 262657, 113, 2089, 331, 2147483647, 65537, 599479, 43691, 122921, 109, 616318177, 174763, 121369, 61681, 164511353, 5419

Offset: 1

Marco Matosic, Aug 16 2004

By Zsigmondy's theorem, a(n) > 1 except for n = 1 or 6.
Conjectures: (1) For every n the highest unique prime factor is of the form kn+1. The values for k are in A097407. (2) For each composite n many factors of the form kn+1 occur intermittently but always singly in any cofactor pair. (3) For each prime n every factor is of the form kn+1.
A prime factor of 2^n-1 is called primitive if it does not divide 2^r-1 for any rA086251.
a(n) is the greatest prime such that the multiplicative order of 2 mod a(n) equals n, or a(n)=1 if no such prime exists. - Jianing Song, Oct 23 2019

Max Alekseyev, Table of n, a(n) for n = 1..1206

Cf. A064078, A097407.

For the smallest primitive prime factor of 2^n-1 see A112927.

isprimitive(p, n) = {for (r=1, n-1, if (((2^r-1) % p) == 0, return (0));); return (1);}
a(n) = {f = factor(2^n-1); forstep(i=#f~, 1, -1, if (isprimitive(f[i, 1], n), return (f[i, 1]));); return (1);} \\ Michel Marcus, Jul 15 2013

a(n) = A006530(A064078(n)). - Jianing Song, Oct 23 2019

More terms and better description from Vladeta Jovovic, Sep 03 2004

a(1) and a(6) changed from 0 to 1 by Jianing Song, Oct 23 2019

A118106 Period of the vector sequence d(n)^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 4, 1, 2, 1, 3, 4, 1, 1, 6, 1, 4, 6, 10, 1, 2, 1, 12, 1, 6, 1, 4, 1, 1, 10, 8, 12, 6, 1, 18, 3, 4, 1, 6, 1, 10, 12, 11, 1, 4, 1, 20, 16, 12, 1, 18, 5, 6, 18, 28, 1, 4, 1, 5, 6, 1, 4, 10, 1, 8, 22, 12, 1, 6, 1, 36, 20, 18, 30, 12, 1, 4, 1, 20, 1, 6, 16, 14, 28, 10, 1, 12, 12

Offset: 1

T. D. Noe, Apr 13 2006

nonn

This sequence is related to the period of sigma_k(n) mod n. Note that a(n)=1 iff n is a power of a prime.
The record periods of p-1 occur at n=2p, where p is a prime with primitive root 2 (A001122). - T. D. Noe, Oct 25 2007
From Jianing Song, Nov 03 2019: (Start)
The smallest index m such that from the m-th term on, the sequence {d(n)^k mod n: k >= 0} enters into a cycle is m = A051903(n).
Let b(n) be the period of {sigma_k(n) mod n: k >= 0}, then b(n) | a(n) for all n, but generally they are not necessarily the same (for example, a(576) = 48 while b(576) = 16).
Every number m occurs in this sequence. Suppose m != 1, 6, by Zsigmondy's theorem, 2^m - 1 has at least one primitive factor p. Here a primitive factor p means that ord(2,p) = m. So we have a(2p) = lcm(ord(2,p), ord(p,2)) = m (see the formula below). Specially, we have a(2*A112927(m)) = a(2*A097406(m)) = m for m != 1, 6. (End)

			a(35)=12 because d(35)=(1,5,7,35) and (1,5,7,35)^k (mod 35) is the sequence of vectors (1,5,7,0), (1,25,14,0), (1,20,28,0), (1,30,21,0), (1,10,7,0), (1,15,14,0), (1,5,28,0), (1,25,21,0), (1,20,7,0), (1,30,14,0), (1,10,28,0), (1,15,21,0), (1,5,7,0),..., which has a period of 12.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (terms 1..1000 from T. D. Noe)

Cf. A118107 (period of the vector sequence d(n)^2^k mod n), A051903.

Table[d=Divisors[n]; k=0; found=False; While[i=0; While[i

A118106(n) = { my(divs=apply(d -> (d%n),divisors(n)), odivs = Vec(divs), vs = Map()); mapput(vs, odivs, 0); for(k=1,oo,divs = vector(#divs,i,(divs[i]*odivs[i])%n); if(mapisdefined(vs, divs), return(k-mapget(vs, divs)), mapput(vs, divs, k))); }; \\ Antti Karttunen, Sep 23 2018

a(n) = my(m=omega(n), M=vector(m^2),f=factor(n)); for(i=1, m, for(j=1, m, M[(i-1)*m+j]=if(i==j, 1, znorder(Mod(f[i,1],f[j,1]^f[j,2]))))); lcm(M) \\ Jianing Song, Nov 03 2019

Write n = Product_{i=1..t} p_i^e_i, then a(n) = lcm_{1<=i,j<=t, i!=j} ord(p_i,p_j^e_j), where ord(a,r) is the multiplicative order of a modulo r. - Jianing Song, Nov 03 2019

A002184 a(n) = least primitive factor of 2^(2n+1) - 1.

Original entry on oeis.org

1, 7, 31, 127, 73, 23, 8191, 151, 131071, 524287, 337, 47, 601, 262657, 233, 2147483647, 599479, 71, 223, 79, 13367, 431, 631, 2351, 4432676798593, 103, 6361, 881, 32377, 179951, 2305843009213693951, 92737, 145295143558111, 193707721, 10052678938039, 228479, 439, 100801, 581283643249112959, 2687, 2593, 167

Offset: 0

N. J. A. Sloane

nonn

For n > 0, 2^(a(n)-2n-2) == 1 (mod a(n)), since 2^(a(n)-1) == 2^(2n+1) == 1 (mod a(n)). - Thomas Ordowski, Aug 11 2021

a(n) == 1 (mod 2n+1). - Thomas Ordowski, Aug 11 2021

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 2, p. 84.
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).

Max Alekseyev, Table of n, a(n) for n = 0..602
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
S. S. Wagstaff, Jr., The Cunningham Project

Cf. A002588, A112927.

a(n) = A112927(2n+1). - Max Alekseyev, Apr 26 2022

More terms from Don Reble, Nov 14 2006

A002185 Smallest primitive factor of 2^(2n+1) + 1.

Original entry on oeis.org

3, 1, 11, 43, 19, 683, 2731, 331, 43691, 174763, 5419, 2796203, 251, 87211, 59, 715827883, 67, 281, 1777, 22366891, 83, 2932031007403, 18837001, 283, 4363953127297, 307, 107, 2971, 571, 2833, 768614336404564651, 77158673929, 131, 7327657, 139, 56409643, 1753

Offset: 0

N. J. A. Sloane

nonn

J. Brillhart et al., Factorizations of b^n +- 1. Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 2nd edition, 1985; and later supplements.
M. Kraitchik, Recherches sur la Théorie des Nombres. Gauthiers-Villars, Paris, Vol. 1, 1924, Vol. 2, 1929, see Vol. 2, p. 85.
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).

Max Alekseyev, Table of n, a(n) for n = 0..568
J. Brillhart et al., Factorizations of b^n +- 1, Contemporary Mathematics, Vol. 22, Amer. Math. Soc., Providence, RI, 3rd edition, 2002.
S. S. Wagstaff, Jr., The Cunningham Project

Cf. A002589, A086257, A112927.

Terms a(25) onward from Max Alekseyev, Oct 16 2022

A242292 Least prime divisor of 2^n - n which does not divide any 2^k - k with 0 < k < n, or 1 if such a primitive prime divisor of 2^n - n does not exist.

Original entry on oeis.org

1, 2, 5, 3, 1, 29, 11, 31, 503, 13, 7, 1021, 8179, 1637, 4679, 1, 8737, 131063, 524269, 262139, 2097131, 349, 131, 773, 271, 197, 457, 1493, 317, 17, 6733, 73, 41, 157109, 83, 53, 1741, 3329, 49977801259, 997, 149, 2199023255531, 61, 4398046511093, 3769453

Offset: 1

Zhi-Wei Sun, May 10 2014

nonn

Conjecture: a(n) = 1 only for n = 1, 5, 16.

In constrast, a classical theorem of Bang asserts that if n > 1 is different from 6 then 2^n - 1 has a prime divisor which does not divide any 2^k - 1 with 0 < k < n.

			a(4) = 3 since 2^4 - 4 = 2^2*3 with 3 dividing none of 2^1 - 1 = 1, 2^2 - 2 = 2 and 2^3 - 3 = 5.

A. S. Bang, Taltheoretiske Undersgelser, Tidsskrift fur Mat. 4(1886), no. 5, 70--80, 130--137.

Zhi-Wei Sun, Table of n, a(n) for n = 1..215
Z.-W. Sun, New observations on primitive roots modulo primes, arXiv preprint arXiv:1405.0290 [math.NT], 2014.

Cf. A000040, A000325, A112927, A242169, A242170, A242171, A242173, A242174, A242193, A242194, A242195, A242207.

u[n_]:=2^n-n
f[n_]:=FactorInteger[u[n]]
p[n_]:=Table[Part[Part[f[n], k], 1], {k, 1, Length[f[n]]}]
Do[If[u[n]<2, Goto[cc]]; Do[Do[If[Mod[u[i], Part[p[n], k]]==0, Goto[aa]], {i, 1, n-1}]; Print[n, " ", Part[p[n], k]]; Goto[bb]; Label[aa]; Continue, {k, 1, Length[p[n]]}]; Label[cc]; Print[n, " ", 1]; Label[bb]; Continue, {n, 1, 45}]

cp's OEIS Frontend

A379642 Smallest primitive prime factor of 9^n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A086251 Number of primitive prime factors of 2^n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A379639 Smallest primitive prime factor of 6^n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A379644 Smallest primitive prime factor of 11^n-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A144755 Primes which divide none of overpseudoprimes to base 2 (A141232).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A097406 Largest primitive prime factor of 2^n-1, or a(n) = 1 if no such prime exists.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

A118106 Period of the vector sequence d(n)^k mod n for k=1,2,3,..., where d(n) is the vector of divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A002184 a(n) = least primitive factor of 2^(2n+1) - 1.

Views

Author