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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000790 Primary pretenders: least composite c such that n^c == n (mod c). 9
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 (list; graph; refs; listen; history; text; internal format)
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

REFERENCES

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).

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.

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.

OEIS Index to periodic sequences.

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

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

Adjacent sequences:  A000787 A000788 A000789 * A000791 A000792 A000793

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

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 June 17 05:48 EDT 2019. Contains 324183 sequences. (Running on oeis4.)