A137576 -id:A137576 - cp's OEIS frontend

A141232 Overpseudoprimes to base 2: composite k such that k = A137576((k-1)/2).

2047, 3277, 4033, 8321, 65281, 80581, 85489, 88357, 104653, 130561, 220729, 253241, 256999, 280601, 390937, 458989, 486737, 514447, 580337, 818201, 838861, 877099, 916327, 976873, 1016801, 1082401, 1145257, 1194649, 1207361, 1251949, 1252697, 1325843

Offset: 1

Vladimir Shevelev, Jun 16 2008

nonn

Numbers are found by prime factorization of numbers from A001262 and a simple testing of the conditions indicated in comment to A141216.
All composite Mersenne numbers (A001348), Fermat numbers (A000215) and squares of Wieferich primes (A001220) are in this sequence. - Vladimir Shevelev, Jul 15 2008
C. Pomerance proved that this sequence is infinite (see Theorem 4 in the third reference). - Vladimir Shevelev, Oct 29 2011
Odd composite numbers k such that ord(2,k) * ((Sum_{d|k} phi(d)/ord(2,d)) - 1) = k-1, where phi = A000010 and ord(2,d) is the multiplicative order of 2 modulo d. - Jianing Song, Nov 13 2021

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..664 from Michel Marcus)
J. H. Castillo, G. García-Pulgarín and J. M. Velásquez-Soto, q-pseudoprimality: A natural generalization of strong pseudoprimality, arXiv:1412.5226 [math.NT], 2014.
Vladimir Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich primes, arXiv:0806.3412 [math.NT], 2008-2012.
Vladimir Shevelev, Process of "primoverization" of numbers of the form a^n-1, arXiv:0807.2332 [math.NT], 2008.
Vladimir Shevelev, On upper estimate for the overpseudoprime counting function, arXiv:0807.1975 [math.NT], 2008.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers, J. Integer Seq. 15 (2012) Article 12.7.7.
Vladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat numbers as primover numbers, arXiv:1206.0606 [math.NT], 2012.

Cf. A000010, A001262, A141216, A001567, A002326.

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

f(n)=my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isok(n) = (n>1) && !isprime(n) && (n == f((n-1)/2)); \\ Michel Marcus, Oct 05 2018

Sum_{n:a(n)<=x} 1 <= x^(3/4)(1+o(1)).

Name edited by Michel Marcus, Oct 05 2018

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

A140140 Positions of first appearances of odd primes in A137576.

Original entry on oeis.org

1, 2, 3, 5, 4, 7, 9, 11, 14, 10, 18, 12, 21, 23, 26, 29, 17, 33, 35, 28, 39, 41, 42, 48, 50, 51, 53, 45, 43, 63, 46, 68, 69, 74, 38, 78, 66, 83, 86, 89, 90, 95, 59, 98, 85, 49, 111, 113, 97, 88, 119, 71, 125, 128, 131, 134, 135, 138, 93, 141, 146, 109, 155, 84, 158, 165, 145

Offset: 1

Vladimir Shevelev, May 10 2008

nonn

a(n) <= (p_n-1)/2, where p_n is the n-th odd prime (A065091).

Cf. A137576, A065091.

terms = 100;
a137576[n_] := Module[{t}, (t = MultiplicativeOrder[2, 2 n + 1])* DivisorSum[2 n + 1, EulerPhi[#]/MultiplicativeOrder[2, #] &] - t + 1];
A137576 = Array[a137576, 3 terms];
FirstPosition[A137576, #][[1]]& /@ Prime[Range[2, terms+1]] (* Jean-François Alcover, Jan 11 2019 *)

Corrected and extended by Ray Chandler, May 19 2008

A140607 (A039649(2n+1)+A137576(n))/2.

Original entry on oeis.org

3, 5, 7, 10, 11, 13, 13, 17, 19, 22, 23, 31, 37, 29, 31, 31, 43, 37, 37, 41, 43, 55, 47, 64, 45, 53, 61, 55, 59, 61, 55, 61, 67, 78, 71, 73, 91, 106, 79, 136, 83, 77, 85, 89, 91, 96, 109, 97, 136, 101, 103, 109, 107, 109, 109, 113, 155, 103, 145, 166, 111, 201, 127, 113

Offset: 1

Vladimir Shevelev, May 18 2008

nonn

If 2n+1 is a prime then a(n) = 2n+1.

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

Cf. A039649, A137576, A000010, A000040, A140140, A138193, A138217, A138227, A138535, A138536, A138537, A138539, A140141, A140608, A138786, A140667.

Extended by Ray Chandler, May 20 2008, May 24 2008

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Original entry on oeis.org

30, 320, 224, 240, 72, 360, 728, 0, 672, 216, 1320, 0, 0, 16, 5060, 60, 126, 10560, 216, 0, 3360, 2574, 150, 5040, 2808, 3600, 3600, 232, 400, 420, 22, 2700, 2784, 224, 96, 70, 1640, 240, 9200, 3600, 2760, 58344, 616, 504, 102, 5600, 8064, 264, 11880, 1440, 7488, 252

Offset: 1

Vladimir Shevelev, Jun 14 2008, Jul 13 2008

nonn

The zero terms are of a special interest. Indeed, since for any odd prime p, A137576((p-1)/2)=p, then it is natural to call "overpseudoprimes" those Poulet pseudoprimes A001567(n) for which a(n)=0.
Theorem. A squarefree composite number m = p_1*p_2*...*p_k is an overpseudoprime if and only if A002326((p_1-1)/2) = A002326((p_2-1)/2) = ... = A002326((p_k-1)/2). Moreover, every overpseudoprime is in A001262.
Note that in A001262 there exist terms which are not squarefree. The first is A001262(52) = 1194649 = 1093^2.
It can be shown that if an overpseudoprime is not a multiple of the square of a Wieferich prime (see A001220) then it is squarefree. Also all squares of Wieferich primes are overpseudoprimes.

Amiram Eldar, Table of n, a(n) for n = 1..10000
V. Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich Primes, arxiv:0806.3412 [math.NT], 2008-2012.

Cf. A137576, A001567, A001262, A002326, A006694.

fppQ[n_]:=PowerMod[2,n,n]==2;f[n_] := (t = MultiplicativeOrder[2, 2n+1])*DivisorSum[2n+1, EulerPhi[#] / MultiplicativeOrder[2, #]&]-t+1; s={}; Do[If[fppQ[n] && CompositeQ[n],AppendTo[s,f[(n-1)/2 ]-n]],{n,1,10000}]; s (* Amiram Eldar, Dec 09 2018 after Jean-François Alcover at A137576 *)

f(n) = my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1; \\ A137576
isfpp(n) = {Mod(2, n)^n==2 & !isprime(n) & n>1}; \\ A001567
lista(nn) = {for (n=1, nn, if (isfpp(n), print1(f((n-1)/2) - n, ", ");););} \\ Michel Marcus, Dec 09 2018

More terms via b137576.txt from R. J. Mathar, Jun 12 2010

More terms from Michel Marcus, Dec 09 2018

A140197 A137576((k-1)/2) for composite numbers k from A141229.

Original entry on oeis.org

55, 301, 3631, 6085, 19495, 70645, 147853, 438205, 605695, 669781, 888823, 1694695, 3060301, 3640783, 6692791, 7998895, 9857245, 12912535, 15443365, 17109895, 17690941, 22819693, 28048231, 34936663, 58178245, 75203725, 95263573, 124984543, 127160245, 155267965

Offset: 1

Vladimir Shevelev, Jun 15 2008

nonn

Cf. A137576, A141229, A006694, A002326.

r[n_] := EulerPhi[n]/MultiplicativeOrder[2, n]; d[n_] := DivisorSum[n, r[#] &]; f[n_] := (m = MultiplicativeOrder[2, n])*d[n] - m + 1; f /@ Select[Range[10^5], CompositeQ[#] && Total@(r /@ Divisors[#]) - 1 == 3 &] (* Amiram Eldar, Sep 12 2019 *)

More terms from Amiram Eldar, Sep 12 2019

A140320 a(n) = A137576((3^n-1)/2).

Original entry on oeis.org

1, 3, 13, 55, 217, 811, 2917, 10207, 34993, 118099, 393661, 1299079, 4251529, 13817467, 44641045, 143489071, 459165025, 1463588515, 4649045869, 14721978583, 46490458681, 146444944843, 460255540933, 1443528742015, 4518872583697, 14121476824051, 44059007691037, 137260754729767

Offset: 0

Vladimir Shevelev, May 26 2008

nonn

Conjecture. a(n) = 2n*3^(n-1)+1.
If conjecture is true then limsup(A137576(n)/n)=infinity while liminf(A137576(n)/n)=2 with a realization on primes.
a(n) is also the number of edges in the graph generated from the n-dimensional hypercube (plus 1) in the following manner: connect all (d + 1)-dimensional faces to the d faces that are incident. Each d-dimensional face should be incident on (n - d) (d + 1)-dimensional faces. [Roy Liu (royliu(AT)cs.ucsd.edu), Jul 26 2010]

Wikipedia, Hypercube

Cf. A037576, A002326, A006694, A025192.

a137576(n) = my(t); sumdiv(2*n+1, d, eulerphi(d)/(t=znorder(Mod(2, d))))*t-t+1;
a(n) = a137576((3^n-1)/2); \\ Michel Marcus, Dec 18 2018

Sum_{m = 0}^{n} 2^(n - m) * binomial(n,m) is the number of m-dimensional faces in the n-dimensional hypercube. Consequently, Sum_{m = 0..n} (n - m) * 2^(n - m) * binomial(n,m) gives the number of incidence edges, which yields said sequence minus 1. The recurrence relation is: a(n) = 3 * a(n - 1) + 2 * 3^(n - 1) - 2. [Roy Liu (royliu(AT)cs.ucsd.edu), Jul 26 2010]

Empirical G.f.: (1-4*x+7*x^2)/(1-7*x+15*x^2-9*x^3). [Colin Barker, Jan 09 2012]

More terms from Michel Marcus, Dec 18 2018

A014664 Order of 2 modulo the n-th prime.

Original entry on oeis.org

2, 4, 3, 10, 12, 8, 18, 11, 28, 5, 36, 20, 14, 23, 52, 58, 60, 66, 35, 9, 39, 82, 11, 48, 100, 51, 106, 36, 28, 7, 130, 68, 138, 148, 15, 52, 162, 83, 172, 178, 180, 95, 96, 196, 99, 210, 37, 226, 76, 29, 119, 24, 50, 16, 131, 268, 135, 92, 70, 94, 292, 102, 155, 156, 316

Offset: 2

N. J. A. Sloane

In other words, a(n), n >= 2, is the least k such that prime(n) divides 2^k-1.
Concerning the complexity of computing this sequence, see for example Bach and Shallit, p. 115, exercise 8.
Also A002326((p_n-1)/2). Conjecture: If p_n is not a Wieferich prime (1093, 3511, ...) then A002326(((p_n)^k-1)/2) = a(n)*(p_n)^(k-1). - Vladimir Shevelev, May 26 2008
If for distinct i,j,...,k we have a(i)=a(j)=...=a(k) then the number N = p_i*p_j*...*p_k is in A001262 and moreover A137576((N-1)/2) = N. For example, a(16)=a(37)=a(255)=52. Therefore we could take N = p_16*p_37*p_255 = 53*157*1613 = 13421773. - Vladimir Shevelev, Jun 14 2008
Also degree of the 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
Is this the same as the smallest k > 1 not already in the sequence such that p = prime(n) is a factor of 2^k-1 (A270600)? If the answer is yes, is the sequence a permutation of the positive integers > 1? - Felix Fröhlich, Feb 21 2016. Answer: No, it is easy to prove that 6 is missing and obviously 11 appears twice. - N. J. A. Sloane, Feb 21 2016
pi(A112927(m)) is the index at which a given number m first appears in this sequence. - M. F. Hasler, Feb 21 2016

			2^2 == 1 (mod 3) and so a(2) = 2;
2^4 == 1 (mod 5) and so a(3) = 4;
2^3 == 1 (mod 7) and so a(4) = 3;
2^10 == 1 (mod 11) and so a(5) = 10; etc.
[Conway & Guy, p. 166]: Referring to the work of Euler, 1/13 in base 2 = 0.000100111011...; (cycle length of 12). - _Gary W. Adamson_, Aug 22 2009

E. Bach and Jeffrey Shallit, Algorithmic Number Theory, I.
Albert H. Beiler, "Recreations in the Theory of Numbers", Dover, 1966; Table 48, page 98, "Exponents to Which a Belongs, MOD p and MOD p^n.
John H. Conway and Richard Guy, "The Book of Numbers", Springer-Verlag, 1996; p. 166: "How does the Cycle Length Change with the Base?". [From Gary W. Adamson, Aug 22 2009]
S. K. Sehgal, Group rings, pp. 455-541 in Handbook of Algebra, Vol. 3, Elsevier, 2003; see p. 493.

Michael De Vlieger, Table of n, a(n) for n = 2..10001 (terms 2..1001 from Nick Hobson, terms 1002..5001 from Zak Seidov)
Gary W. Adamson, Further comments.
O. N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets, Funct. Anal. Other Math. 1 (2006), 175-180.
O. N. Karpenkov, On examples of difference operators for {0,1}-valued functions over finite sets, arXiv:math/0611940 [math.CO], 2006.

Cf. A002326 (order of 2 mod 2n+1), A001122 (full reptend primes in base 2), A065941, A112927.

In other bases: A062117, A082654, A211241, A211242, A211243, A211244, A211245, A002371.

P:=Filtered([1..350],IsPrime);; a:=List([2..Length(P)],n->OrderMod(2,P[n]));; Print(a); # Muniru A Asiru, Jan 29 2019

with(numtheory): [ seq(order(2,ithprime(n)), n=2..60) ];

Reap[Do[p=Prime[i];Do[If[PowerMod[2,k,p]==1,Print[{i,k}];Sow[{i,k}];Goto[ni]],{k,1,10^6}];Label[ni],{i,2,5001}]][[2,1]] (* Zak Seidov, Jan 26 2009 *)
Table[MultiplicativeOrder[2, Prime[n]], {n, 2, 70}] (* Jean-François Alcover, Dec 10 2015 *)

a(n)=if(n<0,0,k=1;while((2^k-1)%prime(n)>0,k++);k)

A014664(n)=znorder(Mod(2, prime(n))) \\ Nick Hobson, Jan 08 2007, edited by M. F. Hasler, Feb 21 2016

forprime(p=3, 800, print(factormod((x^p+1)/(x+1), 2, 1)[1, 1])) \\ V. Raman, Oct 04 2012

from sympy import n_order, prime
def A014664(n): return n_order(2,prime(n)) # Chai Wah Wu, Nov 09 2023

a(n) = (A000040(n)-1)/A001917(n); a(A072190(n)) = A001122(n) - 1. - Benoit Cloitre, Jun 06 2004

More terms from Benoit Cloitre, Apr 11 2003

cp's OEIS Frontend

A141232 Overpseudoprimes to base 2: composite k such that k = A137576((k-1)/2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A140140 Positions of first appearances of odd primes in A137576.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A140607 (A039649(2n+1)+A137576(n))/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A141216 a(n) = A137576((N-1)/2) - N, where N = A001567(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A140197 A137576((k-1)/2) for composite numbers k from A141229.

Views

Author

Keywords

Crossrefs

Programs

Mathematica