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). 11
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 October 22 10:24 EDT 2019. Contains 328317 sequences. (Running on oeis4.)