OFFSET
1,1
COMMENTS
Let m(n) = A003418(n) = lcm(1,2,...,n). Then a(n) <= m(n)+1, with equality if and only if n=1 or n is prime. - David W. Wilson, Vladeta Jovovic, Dean Hickerson
MATHEMATICA
<<NumberTheory`NumberTheoryFunctions` (* Load ChineseRemainder function, needed below. *)
f[n_, m_] := Select[Range[0, m-1], PowerMod[ #, n, m]==1&]; a[1]=2; a[n_] := Module[{lcm, pe, i, m, s, j, x}, lcm=LCM@@Range[n]; pe=Sort[Select[Range[n], Length[FactorInteger[ # ]]==1&&#*FactorInteger[ # ][[1, 1]]>n&], Length[f[n, #1]]/#1<Length[f[n, #2]]/#2&]; For[i=1; m=1; s={0}, i<=Length[pe], i++, s=Union@@Outer[ChineseRemainder[{#1, #2}, {m, pe[[i]]}]&, s, f[n, pe[[i]]]]; m*=pe[[i]]; For[j=2, j<=Length[s], j++, If[PowerMod[x=s[[j]], n, lcm]==1, Return[x]]]; If[PowerMod[1+m, n, lcm]==1, Return[1+m]]; ]]; (* f[n, m] is list of x with x^n==1 (mod m), 0 <= x < m *)
a[1] = 2; a[n_ /; n <= 10] := (s = 2; While[ Sum[ Sign[ Mod[s^n - 1, i]], {i, 1, n}] > 0, s++]; s); a[n_?PrimeQ] := LCM @@ Range[n] + 1; a[n_] := a[n] = (km = If[n <= 24, 6, 7]; redu = Reduce[ And @@ Table[ Mod[x^n, n - k] == 1, {k, 0, km}], x, Integers]; candidates = Join @@ Table[ Sort[ List @@ (redu /. C[1] -> c)[[All, 2]]], {c, 0, n}]; First[ Select[ candidates, # > 1 && And @@ Table[ Mod[ #^n, k] == 1, {k, 2, n - km - 1}] & ]]); Table[ Print[a[n]]; a[n], {n, 1, 32}] (* Jean-François Alcover, Jan 13 2012, after PARI for n <= 10 *)
PROG
(PARI) for(n=1, 12, s=2; while(sum(i=1, n, sign((s^n-1)%i))>0, s++); print1(s, ", "))
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Benoit Cloitre, May 30 2002
EXTENSIONS
Edited by Robert G. Wilson v, Jun 07 2002
More terms from Don Reble, Jun 07 2002
Corrected and extended by Vladeta Jovovic, Jun 09 2002
Corrected and extended by Dean Hickerson, Jun 13 2002
STATUS
approved