login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A090086 Smallest pseudoprime to base n, not necessarily exceeding n (cf. A007535). 15
4, 341, 91, 15, 4, 35, 6, 9, 4, 9, 10, 65, 4, 15, 14, 15, 4, 25, 6, 21, 4, 21, 22, 25, 4, 9, 26, 9, 4, 49, 6, 25, 4, 15, 9, 35, 4, 39, 38, 39, 4, 205, 6, 9, 4, 9, 46, 49, 4, 21, 10, 51, 4, 55, 6, 15, 4, 57, 15, 341, 4, 9, 62, 9, 4, 65, 6, 25, 4, 69, 9, 85, 4, 15, 74, 15, 4, 77, 6, 9, 4, 9, 21, 85, 4, 15, 86, 87, 4, 91, 6 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

As in A000790, only semiprimes (A001358) and numbers in A135721 (Carmichael numbers which have at least one primitive prime factor) can appear in this sequence. Conjecture: All semiprimes and all numbers in A135721 are in this sequence. (Of course, Carmichael numbers which are not in A135721 (for example, 41041 = 7 * 11 * 13 * 41, but 7|1729, 11|561, 13|1105, and 41|6601) have no primitive prime factor, so they cannot appear in this sequence.) - Eric Chen, Feb 23 2015

I found that there are only 6 counterexamples below a(10000): a(648) = a(5952) = a(9228) = 385, a(1298) = 645, a(1995) = 946, and a(9135) = 286. - Eric Chen, Feb 25 2015

From Eric Chen, Feb 22 2015: (Start)

a(n) = n-1 for n = 5, 7, 10, 11, 15, 16, 22, 23, 27, 36, 39, 40, 47, 52, 58, 63, 66, 70, 75, 78, 87, 88, 135, 147, 156, 210, 238, 310, 383, 448, 546, 1012, ...

a(n) = n+1 for n = 8, 14, 20, 24, 38, 48, 54, 84, 90, 110, 140, 158, 200, 308, 572, ... (n-1 must be prime).

a(n) > n+1 for n = 1, 2, 3, 4, 6, 12, 18, 30, 42, 60, 72, 102, 150, 180, 462, ... (except for 1, 2, and 3, both n-1 and n+1 must be prime).

(End)

I found no more terms between 1012 and 10000 are in these three sequences. Conjecture: a(n) <= n+1 for all n > 462, a(n) <= n-1 for all n > 572, a(n) < n-1 for all n > 1012, and a(n)/n --> 0 for n --> infinity, that is, for all delta > 0, there exists an M such that a(n)/n < delta for all n > M. - Eric Chen, Feb 26 2015

From Robert G. Wilson v, Feb 26 2015: (Start)

First occurrence of k-th composite or 0 if k-th composite does not appear: 1, 7, 0, 8, 11, 0, 15, 4, 0, 0, 0, 20, 23, 0, 18, 27, 0, 0, 0, 0, 122, 579, 6, 0, 39, 38, 0, 0, 0, 0, 47, 0, 30, 0, ..., .

First occurrence of the k-th semiprime (A001358): 1, 7, 8, 11, 15, 4, 20, 23, 18, 27, 122, 579, 6, 39, 38, 47, 30, 52, 54, 58, 1683, 63, 12, 70, 75, 78, 3855, 72, 87, 88, 3, 1148, 5735, 2184, 6255, 110, 1404, 8379, 3450, 130, 8175, 1762, 515, 102, 135, 140, ..., .

Records: 4, 341, 382, 447, 949, 1011, 1105, 1441, 1891, 1905, 2047, 2257, 2305, 2465, 3277, 9073, 9361, 12403, ..., .

They first occur at 1, 2, 383, 448, 462, 1012, 1848, 2940, 2964, 36608, 74550, 83538, 99528, 204516, 260610, 360990, 22694490, 27450150, ..., .

(End)

If n-1 is composite, then a(n) < n. - Thomas Ordowski, Aug 08 2018

Conjecture: a(n) = A007535(n) for finitely many n. For n > 2; if a(n) > n, then n-1 is prime (find all these primes). - Thomas Ordowski, Aug 09 2018

It seems that if a(2^p) = p^2, then 2^p-1 is prime. - Thomas Ordowski, Aug 10 2018

LINKS

Eric Chen and Robert G. Wilson v, Table of n, a(n) for n = 1..10000 (first 1024 terms from Eric Chen)

Wikipedia, Pseudoprime

Index entries for sequences related to pseudoprimes

FORMULA

a(n) = LeastComposite{x; n^(x-1) mod x = 1}.

EXAMPLE

From Robert G. Wilson v, Feb 26 2015: (Start)

a(n) = 4 for n = 1 + 4*k, k >= 0.

a(n) = 6 for n = 7 + 12*k, k >= 0.

a(n) = 9 for n = 8 + 18*k, 10 + 18*k, 35 + 36*k, k >= 0.

(End)

a(n) = 10 for n = 51 + 60*k, 11 + 180*k, 131 + 180*k, k >= 0.

MATHEMATICA

f[n_] := Block[{k = 1}, While[ GCD[n, k] > 1 || PrimeQ[k] || PowerMod[n, k - 1, k] != 1, j = k++]; k]; Array[f, 91] (* Robert G. Wilson v, Feb 26 2015 *)

PROG

(PARI) /* a(n) <= 2000 is sufficient up to n = 10000 */

a(n) = for(k=2, 2000, if((n^(k-1))%k==1 && !isprime(k), return(k))) \\ Eric Chen, Feb 22 2015

(PARI) a(n) = {forcomposite(k=2, , if (Mod(n, k)^(k-1) == 1, return (k)); ); } \\ Michel Marcus, Mar 02 2015

CROSSREFS

Cf. A007535, A250200, A090085, A090087, A000790, A239293, A293203.

Cf. A001567, A005935, A005936, A005937, A005938, A005939, A020136 - A020228.

Sequence in context: A265868 A239293 A295997 * A007535 A000783 A098654

Adjacent sequences:  A090083 A090084 A090085 * A090087 A090088 A090089

KEYWORD

nonn

AUTHOR

Labos Elemer, Nov 25 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 20:57 EST 2019. Contains 319282 sequences. (Running on oeis4.)