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
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).
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
KEYWORD
nonn,nice
AUTHOR
STATUS
approved