A090086 -id:A090086 - cp's OEIS frontend

A090087 Smallest odd pseudoprimes to base n, not necessarily exceeding n. Compare with A007535 and A090086.

9, 341, 91, 15, 217, 35, 25, 9, 91, 9, 15, 65, 21, 15, 341, 15, 9, 25, 9, 21, 55, 21, 33, 25, 39, 9, 65, 9, 15, 49, 15, 25, 85, 15, 9, 35, 9, 39, 95, 39, 15, 205, 21, 9, 133, 9, 65, 49, 15, 21, 25, 51, 9, 55, 9, 15, 25, 57, 15, 341, 15, 9, 341, 9, 33, 65, 33, 25, 35, 69, 9, 85, 9, 15

Offset: 1

Labos Elemer, Nov 25 2003

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A007535, A090986, A090088, A090089.

a[n_] := Module[{k = 1}, While[GCD[n, k] > 1 || PrimeQ[k] || PowerMod[n, k - 1, k] != 1, k += 2]; k]; Array[a, 100] (* Amiram Eldar, Nov 11 2019 *)

a(n)=Min{x=odd number; Mod[ -1+n^(x-1), x]=0}

A090088 Smallest even pseudoprimes to odd base=2n-1, not necessarily exceeding n. See also A007535 and A090086, A090087.

Original entry on oeis.org

4, 286, 4, 6, 4, 10, 4, 14, 4, 6, 4, 22, 4, 26, 4, 6, 4, 34, 4, 38, 4, 6, 4, 46, 4, 10, 4, 6, 4, 58, 4, 62, 4, 6, 4, 10, 4, 74, 4, 6, 4, 82, 4, 86, 4, 6, 4, 94, 4, 14, 4, 6, 4, 106, 4, 10, 4, 6, 4, 118, 4, 122, 4, 6, 4, 10, 4, 134, 4, 6, 4, 142, 4, 146, 4, 6, 4, 14, 4, 158, 4, 6, 4, 166, 4, 10

Offset: 1

Labos Elemer, Nov 25 2003

nonn

For an even base there are no even pseudoprimes.

			n=2, 2n-2=3 as base, smallest relevant power is -1+2^(286-1) which is divisible by 286.

Antti Karttunen, Table of n, a(n) for n = 1..16520
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Cf. A007535, A090986, A090987, A090089.

Array[Block[{k = 4}, While[PowerMod[2 # - 1, k - 1, k] != 1, k += 2]; k] &, 86] (* Michael De Vlieger, Nov 13 2018 *)

A090088(n) = { forstep(k=4, oo, 2, if(1==(Mod(n+n-1, k)^(k-1)), return (k)); ); } \\ (After code in A090086) - Antti Karttunen, Nov 10 2018

a(n) = Min_{x=even number; (-1 + n^(x-1)) mod x = 0}.

A293203 Numbers k such that A090086(k), the smallest pseudoprime to base k (not necessarily exceeding k), is a Carmichael number.

Original entry on oeis.org

700, 1040, 1150, 1848, 2590, 2660, 6710, 6862, 7000, 7716, 7852, 8060, 8528, 9275, 9875, 10103, 10640, 11830, 12010, 12688, 13340, 16520, 17350, 17570, 17960, 18130, 18340, 19203, 19272, 19420, 19820, 19978, 20410, 20442, 20480, 20612, 20720, 23016, 23463

Offset: 1

Amiram Eldar, Oct 12 2017

nonn

The corresponding Carmichael numbers are 561, 561, 561, 1105, 561, 561, 1729, 561, 561, 1105, 561, 561, 561, 561, 561, 561, 561, 561, 561, ...

Andrzej Schinzel proved that this sequence is infinite. Conjecture: if A090086(n) is a Carmichael number k, then k < n. - Thomas Ordowski, Aug 08 2018

			700 is the sequence since A090086(700) = 561 is a Carmichael number.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Andrzej Rotkiewicz, Periodic sequences of pseudoprimes connected with Carmichael number and the least period of the function l_x^C, Acta Arithmetica, Vol. 91, No. 1 (1999), pp. 75-83.
Andrzej Rotkiewicz, Solved and unsolved problems on pseudoprime numbers and their generalizations, Applications of Fibonacci numbers, Springer Netherlands, 1999, pp. 293-306.

Cf. A002997, A090086.

carmichaelQ[n_] := Divisible[n - 1, CarmichaelLambda[n]] && ! PrimeQ[n];
f[n_] := Block[{k = 1}, While[GCD[n, k] > 1 || PrimeQ[k] || PowerMod[n, k - 1, k] != 1, j = k++]; k]; Select[Range[10000], carmichaelQ[f[#]] &] (* after Robert G.Wilson v at A090086 *)

A316504 Numbers n such that A090086(n+1) > n+1.

Original entry on oeis.org

0, 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 47, 53, 59, 71, 83, 89, 101, 109, 139, 149, 157, 179, 199, 307, 461, 571

Offset: 1

Thomas Ordowski, Aug 12 2018

Probably complete.
Numbers n such that A090086(n+1) = A007535(n+1).
For n > 1, if A090086(n+1) > n+1, then n is a prime.

Cf. A000040, A090086, A007535, A317851.

a090086(n) = {forcomposite(k=2, , if (Mod(n, k)^(k-1) == 1, return (k)); ); }
isok(n) = a090086(n+1) > n+1; \\ Michel Marcus, Aug 12 2018

A317851 Primes p such that A090086(p+1) < p.

Original entry on oeis.org

31, 43, 61, 67, 73, 79, 97, 103, 107, 113, 127, 131, 137, 151, 163, 167, 173, 181, 191, 193, 197, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421

Offset: 1

Thomas Ordowski, Aug 09 2018

nonn

Theorem: if n-1 is composite, then A090086(n) < n.
The inverse theorem is false iff n = p+1 for primes p in this sequence.
Conjecture: the sequence contains all sufficiently large primes. Probably all primes except 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 37, 41, 47, 53, 59, 71, 83, 89, 101, 109, 139, 149, 157, 179, 199, 307, 461, and 571.

			The prime 31 is a term, since A090086(31+1) = 25 < 31.

Cf. A000040, A090086.

b(n) = {forcomposite(k=2, , if (Mod(n, k)^(k-1) == 1, return (k)); ); }
isok(p) = isprime(p) && (b(p+1) < p); \\ Michel Marcus, Aug 09 2018

Corrected and extended by Michel Marcus, Aug 09 2018

A288036 Numbers x such that the trajectory of x under the map x -> A090086(x) does not enter the cycle {14, 15}.

Original entry on oeis.org

38, 39, 40, 220, 248, 508, 623, 662, 688, 723, 740, 742, 875, 898, 922, 950, 1078, 1103, 1130, 1179, 1208, 1262, 1312, 1390, 1598, 1600, 1635, 1652, 1678, 1780, 1787, 2027, 2198, 2319, 2378, 2380, 2495, 2547, 2560, 2588, 2770, 2775, 2900, 2950, 2963, 3003

Offset: 1

Felix Fröhlich, Jun 04 2017

nonn

			The trajectory of 220 enters the cycle {38, 39} after one step, so 220 is a term of the sequence.

Cf. A090086.

Select[Range@ 3000, Function[k, ! MemberQ[NestWhileList[Function[n, Block[{j = 1}, While[GCD[n, j] > 1 || PrimeQ@ j || PowerMod[n, j - 1, j] != 1,i = j++]; j]], k, # != 15 &, 1, 100], 15]]] (* Michael De Vlieger, Jun 06 2017, after Robert G. Wilson v at A090086 *)

a090086(n) = forcomposite(c=1, , if(Mod(n, c)^(c-1)==1, return(c)))
trajectory(n, terms) = my(v=[n]); while(#v < terms, v=concat(v, a090086(v[#v]))); v
is(n) = my(len=2, t=trajectory(n, len), k=#t); while(1, k--; if(t[k]==t[#t], if(t[#t]!=14 && t[#t]!=15, return(1), return(0))); if(k==1, len++; t=trajectory(n, len); k=#t))

A293279 a(n) = k is a number such that A090086(k), the smallest pseudoprime to base k (not necessarily exceeding n), is the n-th Carmichael number.

Original entry on oeis.org

700, 1848, 6710, 204516, 507015, 33985380, 184360410, 998393578

Offset: 1

Amiram Eldar, Oct 12 2017

Subsequence of A293203.

			a(1) = 700 since 700 is the least k such that A090086(k) = 561 = A002997(1), the first Carmichael number.
a(2) = 1848 since 1848 is the least k such that A090086(k) = 1105 = A002997(2), the second Carmichael number.

Cf. A002997, A090086, A293203.

A000790 Primary pretenders: least composite c such that n^c == n (mod c).

Original entry on oeis.org

4, 4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, 6, 4, 4, 6, 6, 4, 4, 6, 15, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 15, 6, 4, 4, 6, 6, 4, 4, 6, 21, 4, 4, 10, 6, 4

Offset: 0

N. J. A. Sloane

It is remarkable that this sequence is periodic with period 19568584333460072587245340037736278982017213829337604336734362\ 294738647777395483196097971852999259921329236506842360439300 = 2^2 * 3^2 * 5^2 * 7^2 * 11^2 * 13^2 * 17^2 * 19^2 * 23^2 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97 * 101 * 103 * 107 * 109 * 113 * 127 * 131 * 137 * 139 * 149 * 151 * 157 * 163 * 167 * 173 * 179 * 181 * 191 * 193 * 197 * 199 * 211 * 223 * 227 * 229 * 233 * 239 * 241 * 251 * 257 * 263 * 269 * 271 * 277.
Note that the period is 277# * 23# (where as usual # is the primorial). - Charles R Greathouse IV, Feb 23 2014
Records are 4, 341, 382 & 561, and they occur at indices of 0, 2, 383 & 10103. - Robert G. Wilson v, Feb 22 2014
Andrzej Schinzel (1961) proved that a(n) > 6 if and only if n == {2, 11} (mod 12). - Thomas Ordowski and Krzysztof Ziemak, Jan 21 2018
We have a(n) <= A090086(n), with equality iff gcd(a(n),n) = 1. - Thomas Ordowski, Feb 13 2018
Sequence b(n) = gcd(a(n), n) is also periodic with period P = 23# * 277#, because this is the LCM of all terms, cf. A108574. - M. F. Hasler, Feb 16 2018

			a(2) = 341 because 2^341 == 2 (mod 341) and there is no smaller composite number c such that 2^c == 2 (mod c).
a(3) = 6 because 3^6 == 3 (mod 6) (whereas 3^4 == 1 (mod 4)).

T. D. Noe, Table of n, a(n) for n = 0..10000
John H. Conway, Richard K. Guy, W. A. Schneeberger and N. J. A. Sloane, The Primary Pretenders, Acta Arith. 78 (1997), 307-313.
Steven Finch, The On-Line Encyclopedia of Integer Sequences, founded in 1964 by N. J. A. Sloane, A Tribute to John Horton Conway, The Mathematical Intelligencer (2021) Vol. 43, 146-147.
A. Rotkiewicz, Periodic sequences of pseudoprimes connected with Carmichael numbers and the least period of the function lx^C, Acta Arith. XCI.1 (1999), 75-83.
A. Schinzel, Sur les nombres composés n qui divisent a^n - a, Rend. Circ. Mat. Palermo (2) 7 (1958), 37-41.
W. Sierpiński, A remark on composite numbers m which are factors of a^m - a, Wiadom. Mat. 4 (1961), 183-184 (in Polish; MR 23#A87).
OEIS Index to periodic sequences.

Cf. A108574 (all values occurring in this sequence).

Cf. A002808, A090086, A295997 (it has the same set of distinct terms).

import Math.NumberTheory.Moduli (powerMod)
a000790 n = head [c | c <- a002808_list, powerMod n c c == mod n c]
-- Reinhard Zumkeller, Jul 11 2014

f:= proc(n) local c;
  for c from 4 do
    if not isprime(c) and n &^ c - n mod c = 0 then return c fi
  od
end proc:
map(f, [$0..100]); # Robert Israel, Jan 21 2018

a[n_] := For[c = 4, True, c = If[PrimeQ[c + 1], c + 2, c + 1], If[PowerMod[n, c, c] == Mod[n, c], Return[c]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 18 2013 *)

a(n)=forcomposite(c=4,554,if(Mod(n,c)^c==n,return(c))); 561 \\ Charles R Greathouse IV, Feb 23 2014

from sympy import isprime
def A000790(n):
    c = 4
    while pow(n,c,c) != (n % c) or isprime(c):
        c += 1
    return c # Chai Wah Wu, Apr 02 2021

A090096 Least n-pseudoprime which is a power of a prime number; smallest prime-power pseudoprime to base n.

Original entry on oeis.org

4, 1194649, 121, 1194649, 4, 4377277921, 25, 9, 4, 9, 5041, 7252249, 4, 841, 848615161, 1194649, 4, 25, 9, 78961, 4, 169, 169, 25, 4, 9, 121, 9, 4, 49, 49, 25, 4, 2129445719544546771481, 9, 4377277921, 4, 289, 64625521, 121, 4, 529, 25, 9, 4, 9

Offset: 1

Labos Elemer, Dec 01 2003

			n=2: -1+2^(1092*1094) = K*1093*1093 = K*1194649;
n=4k+1: a(4k+1)=4; for a(k)=9 see A090097; a(k)=25 see A090098.
Some large values after a(46): a(52)=219521; a(56)=418609; a(58)=17161; a(59)=7711729; a(83)=23726641; a(84)=26569; a(86)=4656561121; a(87)=3996001; a(92)=528529; a(95)=4566769; a(96)=11881.
Hard bases below 100 are 47, 66, 72, 88, 90.

Index entries for sequences related to pseudoprimes

Cf. A007535, A090086, A247072, A039951.

t=list-of-true-p-powers-generated-independently lf[x_] := Length[FactorInteger[x]] base=6;Do[s=Mod[ -1+base^(Part[t, n]-1), Part[t, n]]; If[Equal[s, 0], Print[Part[t, n]]], {n, 1, Length[t]}]

a(n) = A039951(n)^2.

More terms from Michel Marcus, Aug 30 2019

A090097 Bases n such that the smallest prime-power-pseudoprime to base n is 9.

Original entry on oeis.org

8, 10, 19, 26, 28, 35, 44, 46, 55, 62, 64, 71, 80, 82, 91, 98, 100, 107, 116, 118, 127, 134, 136, 143, 152, 154, 163, 170, 172, 179, 188, 190, 199, 206, 208, 215, 224, 226, 235, 242, 244, 251, 260, 262, 271, 278, 280, 287, 296, 298, 307, 314, 316, 323, 332, 334

Offset: 1

Labos Elemer, Dec 01 2003

nonn

Values of x such that A090096(x) = 9.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A007535, A090086, A090096.

pspQ[n_,b_] := CompositeQ[n] &&  PowerMod[b, n - 1,n ] == 1 ; aQ[n_]:=pspQ[9, n] && AllTrue[{4,8}, !pspQ[#, n] &]; Select[Range[1000], aQ] (* Amiram Eldar, Sep 09 2019 *)

More terms from Amiram Eldar, Sep 09 2019

cp's OEIS Frontend

A090087 Smallest odd pseudoprimes to base n, not necessarily exceeding n. Compare with A007535 and A090086.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A090088 Smallest even pseudoprimes to odd base=2n-1, not necessarily exceeding n. See also A007535 and A090086, A090087.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A293203 Numbers k such that A090086(k), the smallest pseudoprime to base k (not necessarily exceeding k), is a Carmichael number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A316504 Numbers n such that A090086(n+1) > n+1.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

A317851 Primes p such that A090086(p+1) < p.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A288036 Numbers x such that the trajectory of x under the map x -> A090086(x) does not enter the cycle {14, 15}.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

A293279 a(n) = k is a number such that A090086(k), the smallest pseudoprime to base k (not necessarily exceeding n), is the n-th Carmichael number.

Views

Author

Keywords

Comments

Examples

Crossrefs

A000790 Primary pretenders: least composite c such that n^c == n (mod c).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python