

A007535


Smallest pseudoprime ( > n ) to base n: smallest composite number m > n such that n^(m1)1 is divisible by m.
(Formerly M5440)


29



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

a(k1) = k for odd composite numbers k = {9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, ...} = A071904(n).  Alexander Adamchuk, Dec 13 2006


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


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 *)


PROG

(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
(PARI) a(n)=forcomposite(m=n+1, , if(Mod(n, m)^(m1)==1, return(m))) \\ Charles R Greathouse IV, May 18 2015


CROSSREFS

Records in A098653 & A098654.
Cf. A071904, A002808.
Sequence in context: A239293 A295997 A090086 * A000783 A098654 A317058
Adjacent sequences: A007532 A007533 A007534 * A007536 A007537 A007538


KEYWORD

nonn,nice,easy


AUTHOR

N. J. A. Sloane, Mira Bernstein, Robert G. Wilson v


EXTENSIONS

Corrected and extended by Patrick De Geest, October 2000


STATUS

approved



