|
| |
|
|
A063994
|
|
Product_{primes p dividing n } GCD(p-1, n-1).
|
|
5
| |
|
|
1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, 4, 3, 52, 1, 4, 1, 4, 1, 58, 1, 60, 1, 4, 1, 16, 5, 66, 1, 4, 3, 70, 1, 72, 1, 4, 3, 4, 1, 78, 1, 2, 1, 82, 1, 16, 1, 4, 1, 88, 1, 36, 1
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| a(n) = number of bases b mod n for which b^{n-1} = 1 mod n.
|
|
|
REFERENCES
| Baillie and Wagstaff, Lucas pseudoprimes, Mathematics of Computation, 35 (1980), 1391-1417.
P. Erdos and C. Pomerance, On the number of false witnesses for a composite number, Mathematics of Computation, 46 (1986), 259-279.
Keith Gibson, posting to Number Theory List, Sep 07, 2001.
Carl Pomerance, posting to Number Theory List, Sep 07, 2001.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=1..1000
W. R. Alford, A. Granville and C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math. (2) 139 (1994), no. 3, 703-722.
|
|
|
MATHEMATICA
| f[n_] := Times @@ GCD[n - 1, First /@ FactorInteger@ n - 1]; f[1] = 1; Array[f, 92] (* Robert G. Wilson v, Aug 08 2011 *)
|
|
|
PROG
| (PARI) { for (n=1, 1000, f=factor(n)~; a=1; for (i=1, length(f), a*=gcd(f[1, i] - 1, n - 1)); write("b063994.txt", n, " ", a) ) } [From Harry J. Smith (hjsmithh(AT)sbcglobal.net), Sep 05 2009]
(Python)
def a(n):
..prime_witnesses = 0
..for witness in range(1, n):
....if (pow(witness, n-1, n) == 1):
......prime_witnesses += 1
..return prime_witnesses
|
|
|
CROSSREFS
| Cf. A002997.
Sequence in context: A057237 A187730 A049559 * A076512 A128707 A161510
Adjacent sequences: A063991 A063992 A063993 * A063995 A063996 A063997
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Sep 18 2001
|
|
|
EXTENSIONS
| More terms from Robert G. Wilson v (rgwv(AT)rgwv.com), Sep 21 2001
|
| |
|
|
