login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A000790
Primary pretenders: least composite c such that n^c == n (mod c).
12
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,1
COMMENTS
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
LINKS
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. 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).
EXAMPLE
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)).
MAPLE
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
MATHEMATICA
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 *)
PROG
(PARI) a(n)=forcomposite(c=4, 554, if(Mod(n, c)^c==n, return(c))); 561 \\ Charles R Greathouse IV, Feb 23 2014
(Haskell)
import Math.NumberTheory.Moduli (powerMod)
a000790 n = head [c | c <- a002808_list, powerMod n c c == mod n c]
-- Reinhard Zumkeller, Jul 11 2014
(Python)
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
CROSSREFS
Cf. A108574 (all values occurring in this sequence).
Cf. A002808, A090086, A295997 (it has the same set of distinct terms).
Sequence in context: A063439 A218050 A107052 * A068556 A078243 A024246
KEYWORD
nonn,nice
STATUS
approved