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.

A084654 Smallest prime factor of pseudoprimes in A084653.

Original entry on oeis.org

11, 19, 23, 53, 59, 97, 71, 103, 101, 167, 149, 271, 263, 163, 191, 293, 359, 443, 389, 467, 107, 487, 491, 431, 227, 479, 1093, 733, 569, 599, 347, 619, 727, 751, 937, 997, 373, 1193, 743, 1069, 773, 863, 883, 1609, 1061, 1597, 941, 1087, 1091, 853
Offset: 1

Views

Author

T. D. Noe, Jun 02 2003

Keywords

Links

A084655 Largest prime factor of pseudoprimes in A084653.

Original entry on oeis.org

31, 73, 89, 157, 233, 193, 281, 307, 601, 499, 593, 811, 1049, 2593, 2281, 1753, 1433, 1327, 1553, 1399, 6361, 1459, 1471, 1721, 3391, 1913, 1093, 1709, 2273, 2393, 4153, 2473, 2179, 2251, 1873, 1993, 5581, 1789, 2969, 2137, 3089, 3449, 3529, 2011, 3181
Offset: 1

Views

Author

T. D. Noe, Jun 02 2003

Keywords

Links

A001567 Fermat pseudoprimes to base 2, also called Sarrus numbers or Poulet numbers.

Original entry on oeis.org

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, 10261, 10585, 11305, 12801, 13741, 13747, 13981, 14491, 15709, 15841, 16705, 18705, 18721, 19951, 23001, 23377, 25761, 29341
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

A composite number n is a Fermat pseudoprime to base b if and only if b^(n-1) == 1 (mod n). Fermat pseudoprimes to base 2 are often simply called pseudoprimes.
Theorem: If both numbers q and 2q - 1 are primes (q is in the sequence A005382) and n = q*(2q-1) then 2^(n-1) == 1 (mod n) (n is in the sequence) if and only if q is of the form 12k + 1. The sequence 2701, 18721, 49141, 104653, 226801, 665281, 721801, ... is related. This subsequence is also a subsequence of the sequences A005937 and A020137. - Farideh Firoozbakht, Sep 15 2006
Also, composite odd numbers n such that n divides 2^n - 2 (cf. A006935). It is known that all primes p divide 2^(p-1) - 1. There are only two known numbers n such that n^2 divides 2^(n-1) - 1, A001220(n) = {1093, 3511} Wieferich primes p: p^2 divides 2^(p-1) - 1. 1093^2 and 3511^2 are the terms of a(n). - Alexander Adamchuk, Nov 06 2006
An odd composite number 2n + 1 is in the sequence if and only if multiplicative order of 2 (mod 2n+1) divides 2n. - Ray Chandler, May 26 2008
The Carmichael numbers A002997 are a subset of this sequence. For the Sarrus numbers which are not Carmichael numbers, see A153508. - Artur Jasinski, Dec 28 2008
An odd number n greater than 1 is a Fermat pseudoprime to base b if and only if ((n-1)! - 1)*b^(n-1) == -1 (mod n). - Arkadiusz Wesolowski, Aug 20 2012
The name "Sarrus numbers" is after Frédéric Sarrus, who, in 1819, discovered that 341 is a counterexample to the "Chinese hypothesis" that n is prime if and only if 2^n is congruent to 2 (mod n). - Alonso del Arte, Apr 28 2013
The name "Poulet numbers" appears in Monografie Matematyczne 42 from 1932, apparently because Poulet in 1928 produced a list of these numbers (cf. Miller, 1975). - Felix Fröhlich, Aug 18 2014
Numbers n > 2 such that (n-1)! + 2^(n-1) == 1 (mod n). Composite numbers n such that (n-2)^(n-1) == 1 (mod n). - Thomas Ordowski, Feb 20 2016
The only twin pseudoprimes up to 10^13 are 4369, 4371. - Thomas Ordowski, Feb 12 2016
Theorem (A. Rotkiewicz, 1965): (2^p-1)*(2^q-1) is a pseudoprime if and only if p*q is a pseudoprime, where p,q are different primes. - Thomas Ordowski, Mar 31 2016
Theorem (W. Sierpiński, 1947): if n is a pseudoprime (odd or even), then 2^n-1 is a pseudoprime. - Thomas Ordowski, Apr 01 2016
If 2^n-1 is a pseudoprime, then n is a prime or a pseudoprime (odd or even). - Thomas Ordowski, Sep 05 2016
From Amiram Eldar, Jun 19 2021, Apr 21 2024: (Start)
Erdős (1950) called these numbers "almost primes".
According to Erdős (1949) and Piza (1954), the term "pseudoprime" was coined by D. H. Lehmer.
Named after the French mathematician Pierre de Fermat (1607-1665), or, alternatively, after the Belgian mathematician Paul Poulet (1887-1946), or, the French mathematician Pierre Frédéric Sarrus (1798-1861). (End)
If m is a term of this sequence, then (m-1)/ord(2,m) >= 5, where ord(a,m) is the multiplicative order of a modulo m; see my link below. Actually, it seems that we always have (m-1)/ord(2,m) >= 9. - Jianing Song, Nov 04 2024

References

  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §3.2 Prime Numbers, p. 80.
  • Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section A12, pp. 44-50.
  • George P. Loweke, The Lore of Prime Numbers. New York: Vantage Press (1982), p. 22.
  • Øystein Ore, Number Theory and Its History, McGraw-Hill, 1948.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 88-92.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 145.

Links

Crossrefs

Cf. A002997, A005382, A020137, A052155, A083737, A084653, A153508.
Cf. A001220 = Wieferich primes p: p^2 divides 2^(p-1) - 1.
Cf. A005935, A005936, A005937, A005938, A005939, A020136-A020228 (pseudoprimes to bases 3 through 100).

Programs

  • Magma
    [n: n in [3..3*10^4 by 2] | IsOne(Modexp(2,n-1,n)) and not IsPrime(n)]; // Bruno Berselli, Jan 17 2013
  • Maple
    select(t -> not isprime(t) and 2 &^(t-1) mod t = 1, [seq(i,i=3..10^5,2)]); # Robert Israel, Feb 18 2016
  • Mathematica
    Select[Range[3,30000,2], ! PrimeQ[ # ] && PowerMod[2, (# - 1), # ] == 1 &] (* Farideh Firoozbakht, Sep 15 2006 *)
  • PARI
    q=1;vector(50,i,until( !isprime(q) & (1<<(q-1)-1)%q == 0, q+=2);q) \\ M. F. Hasler, May 04 2007
  • PARI
    is_A001567(n)={Mod(2,n)^(n-1)==1 && !isprime(n) && n>1}  \\ M. F. Hasler, Oct 07 2012, updated to current PARI syntax and to exclude even pseudoprimes on Mar 01 2019

Formula

Sum_{n>=1} 1/a(n) is in the interval (0.015260, 33) (Bayless and Kinlaw, 2017). The upper bound was reduced to 0.0911 by Kinlaw (2023). - Amiram Eldar, Oct 15 2020, Feb 24 2024

Extensions

More terms from David W. Wilson, Aug 15 1996
Replacement of broken geocities link by Jason G. Wurtzel, Sep 05 2010
"Poulet numbers" added to name by Joerg Arndt, Aug 18 2014

A128311 Remainder upon division of 2^(n-1)-1 by n.

Original entry on oeis.org

0, 1, 0, 3, 0, 1, 0, 7, 3, 1, 0, 7, 0, 1, 3, 15, 0, 13, 0, 7, 3, 1, 0, 7, 15, 1, 12, 7, 0, 1, 0, 31, 3, 1, 8, 31, 0, 1, 3, 7, 0, 31, 0, 7, 30, 1, 0, 31, 14, 11, 3, 7, 0, 13, 48, 15, 3, 1, 0, 7, 0, 1, 3, 63, 15, 31, 0, 7, 3, 21, 0, 31, 0, 1, 33, 7, 8, 31, 0, 47, 39, 1, 0, 31, 15, 1, 3, 39, 0, 31, 63
Offset: 1

Views

Author

M. F. Hasler, May 04 2007

Keywords

Comments

By Fermat's little theorem, if p > 2 is prime, then 2^(p-1) == 1 (mod p), thus a(p)=0. If a(n)=0, then n may be only pseudoprime, as for n = 341 = 11*31 [F. Sarrus, 1820].
See A001567 for the list of all pseudoprimes to base 2, i.e., composite numbers which have a(n) = 0, also called Sarrus or Poulet numbers. Carmichael numbers A002997 are pseudoprimes to all (coprime) bases b >= 2. - M. F. Hasler, Mar 13 2020

Examples

			a(1)=0 since any integer == 0 (mod 1);
a(2)=1 since 2^1-1 == 1 (mod 2),
a(3)=0 since 3 is a prime > 2,
a(4)=3 since 2^3-1 = 7 == 3 (mod 4);
a(341)=0 since 341=11*31 is a Sarrus number.

Links

Crossrefs

Cf. A001348 (Mersenne numbers), A001567 (Sarrus numbers: pseudoprimes to base 2), A002997 (Carmichael numbers), A084653, A001220 (Wieferich primes).

Programs

  • Mathematica
    Table[Mod[2^(n-1)-1,n],{n,100}] (* Harvey P. Dale, Dec 22 2012 *)
  • PARI
    a(n)=(1<<(n-1)-1)%n
  • PARI
    apply( {A128311(n)=lift(Mod(2,n)^(n-1)-1)}, [1..99]) \\ Much more efficient when n becomes very large. - M. F. Hasler, Mar 13 2020
  • Python
    def A128311(n): return (pow(2,n-1,n)-1)%n # Chai Wah Wu, Jul 06 2022

Formula

a(n) = M(n-1) - n floor( M(n-1)/n ) = M(n-1) - max{ k in nZ | k <= M(n-1) } where M(k)=2^k-1.

A086837 Brilliant Sarrus numbers.

Original entry on oeis.org

341, 1387, 2047, 2701, 31621, 42799, 49141, 49981, 60701, 83333, 88357, 90751, 104653, 129889, 130561, 150851, 162193, 164737, 219781, 226801, 241001, 249841, 282133, 1194649, 1678541, 2035153, 2134277, 2163001, 2284453, 2304167, 2491637
Offset: 1

Views

Author

Jason Earls, Aug 08 2003

Keywords

Examples

			2701 is a term because 2^2700 == 1 (mod 2701) and 2701 = 37*73.

References

  • J. Earls, Mathematical Bliss, Pleroma Publications, 2009, page 10. [From Jason Earls, Nov 21 2009]

Links

Crossrefs

Intersection of A001567 and A078972.
Cf. A084653.

Programs

  • Mathematica
    brilQ[n_] := Block[{fi = FactorInteger@n}, Plus @@ Last /@ fi == 2 && Floor[ Log[10, fi[[1, 1]]]] == Floor[Log[10, fi[[-1, 1]]]]]; Select[Range[10^5], PowerMod[2, # - 1, #] == 1 && brilQ[#] &] (* Amiram Eldar, Jun 28 2019 after Robert G. Wilson v at A078972 *)

Extensions

More terms from Jack Brennen, Dec 21 2004

A242276 Irregular array of factors of n-th Poulet number read by rows, where row n corresponds to A001567(n).

Original entry on oeis.org

11, 31, 3, 11, 17, 3, 5, 43, 5, 13, 17, 19, 73, 7, 13, 19, 3, 5, 127, 23, 89, 5, 17, 29, 37, 73, 7, 13, 31, 29, 113, 37, 109, 17, 257, 3, 31, 47, 31, 151, 43, 127, 7, 23, 41, 73, 109, 53, 157, 3, 11, 257, 7, 19, 67, 31, 331, 5, 29, 73, 5, 7, 17, 19, 3, 17, 251, 7, 13, 151, 59, 233, 11, 31, 41, 43, 337, 23, 683, 7, 31, 73, 5, 13
Offset: 1

Views

Author

Felix Fröhlich, Aug 16 2014

Keywords

Examples

			The first three Poulet numbers (2-pseudoprimes) are 341 = 11*31, 561 = 3*11*17, and 645 = 3*5*43, so the sequence begins:
11, 31;
3, 11, 17;
3, 5, 43;
etc.

Links

Crossrefs

Cf. A001567, A007011, A084653, A084654, A084655.

Programs

  • PARI
    forcomposite(n=1, 1e4, if(Mod(2, n)^(n-1)==1, f=factor(n)[, 1]; for(i=1, #f, print1(f[i], ", "))))
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.