A295997 -id:A295997 - cp's OEIS frontend

A000790 Primary pretenders: least composite c such that n^c == n (mod c).

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

N. J. A. Sloane

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

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

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).
OEIS Index to periodic sequences.

Cf. A108574 (all values occurring in this sequence).

Cf. A002808, A090086, A295997 (it has the same set of distinct terms).

import Math.NumberTheory.Moduli (powerMod)
a000790 n = head [c | c <- a002808_list, powerMod n c c == mod n c]
-- Reinhard Zumkeller, Jul 11 2014

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

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

a(n)=forcomposite(c=4,554,if(Mod(n,c)^c==n,return(c))); 561 \\ Charles R Greathouse IV, Feb 23 2014

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

A108574 Range of A000790 (primary pretenders).

Original entry on oeis.org

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 38, 39, 46, 49, 51, 57, 58, 62, 65, 69, 74, 82, 85, 86, 87, 91, 93, 94, 106, 111, 118, 121, 122, 123, 129, 133, 134, 141, 142, 145, 146, 158, 159, 166, 169, 177, 178, 183, 185, 194, 201, 202, 205, 206, 213, 214, 217, 218, 219, 226, 237, 249, 254, 259, 262, 265, 267, 274, 278, 289, 291, 298, 301, 302, 303, 305, 309, 314, 321, 326, 327, 334, 339, 341, 346, 358, 361, 362, 365, 381, 382, 386, 393, 394, 398, 411, 417, 422, 427, 445, 446, 447, 451, 453, 454, 458, 466, 469, 471, 478, 481, 482, 485, 489, 501, 502, 505, 511, 514, 519, 526, 529, 537, 538, 542, 543, 545, 553, 554, 561

Offset: 1

David W. Wilson, Jun 10 2005

All terms except for the last term, 561, are semiprimes (A001358). Semiprimes up to 559 that are not here: 35, 55, 77, 95, 115, 119, 143, 155, 161, 187, 203, 209, 215, 221, 235, 247, 253, 287, 295, 299, 319, 323, 329, 335, 355, 371, 377, 391, 395, 403, 407, 413, 415, 437, 473, 493, 497, 515, 517, 527, 533, 535, 551, 559. - Zak Seidov, Jan 08 2015
The LCM of all terms is 23# * 277# (where # denotes the primorial function A034386), the period of A000790, and therefore also of the related sequence b(n) = gcd(A000790(n), n). - M. F. Hasler, Feb 16 2018
Range of A295997. - Thomas Ordowski, Feb 27 2018
These numbers k < 561 are semiprimes k = pq such that p-1 | q-1, where primes p <= q. Equivalent condition is p-1 | k-1. - Thomas Ordowski, Aug 18 2018
This shows that all even semiprimes < 561 are in this sequence. The odd semiprimes not in this sequence are the semiprimes (equivalently: all terms but 275, 455, 475, 539) less than 561 in A267999 (which equals A121707 up to 695). - M. F. Hasler, Nov 09 2018

J. H. Conway, R. K. Guy, W. A. Schneeberger and N. J. A. Sloane, The Primary Pretenders, Acta Arith. 78 (1997), 307-313.
J. H. Conway, R. K. Guy, W. A. Schneeberger and N. J. A. Sloane, The Primary Pretenders, arXiv:math/0207180 [math.NT], 2002.

Cf. A000790, A001358, A295997.

pp[n_] := For[c = 4, True, c = If[PrimeQ[c+1], c+2, c+1], If[PowerMod[n, c, c] == Mod[n, c], Return[c]]];seq[n_] := seq[n] = Table[pp[k], {k, 0, 2^n}] // Union; seq[10]; seq[n = 11]; While[ Print["n = ", n, " more terms: ", Complement[seq[n], seq[n-1]]]; seq[n] != seq[n-1], n++]; A108574 = seq[n] (* Jean-François Alcover, Oct 18 2013 *)

my(A=List(561)); forprime(q=2,561\2, forprime(p=2,min(q,561\q), (q-1)%(p-1)|| listput(A, p*q))); A108574=Set(A) \\ M. F. Hasler, Nov 09 2018

cp's OEIS Frontend

A000790 Primary pretenders: least composite c such that n^c == n (mod c).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python