A007535 Smallest pseudoprime ( > n ) to base n: smallest composite number m > n such that n^(m-1)-1 is divisible by m.
4, 341, 91, 15, 124, 35, 25, 9, 28, 33, 15, 65, 21, 15, 341, 51, 45, 25, 45, 21, 55, 69, 33, 25, 28, 27, 65, 45, 35, 49, 49, 33, 85, 35, 51, 91, 45, 39, 95, 91, 105, 205, 77, 45, 76, 133, 65, 49, 66, 51, 65, 85, 65, 55, 63, 57, 65, 133, 87, 341, 91, 63, 341, 65, 112, 91
Offset: 1
References
- A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 42 (but beware errors in his table for n = 28, 58, 65, 77, 100).
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
- G. P. Michon, Pseudoprimes
- Eric Weisstein's World of Mathematics, Fermat's Little Theorem.
- Wikipedia, Pseudoprime
- Index entries for sequences related to pseudoprimes
Programs
-
Haskell
import Math.NumberTheory.Moduli (powerMod) a007535 n = head [m | m <- dropWhile (<= n) a002808_list, powerMod n (m - 1) m == 1] -- Reinhard Zumkeller, Jul 11 2014 -
Mathematica
f[n_] := Block[{k = n + 1}, While[PrimeQ[k] || PowerMod[n, k - 1, k] != 1, k++ ]; k]; Table[ f[n], {n, 67}] (* Robert G. Wilson v, Sep 18 2004 *) -
PARI
a(n)=forcomposite(m=n+1,, if(Mod(n, m)^(m-1)==1, return(m))) \\ Charles R Greathouse IV, May 18 2015
Extensions
Corrected and extended by Patrick De Geest, October 2000
Comments