|
|
A128311
|
|
Remainder upon division of 2^(n-1)-1 by n.
|
|
2
|
|
|
0, 1, 0, 3, 0, 1, 0, 7, 3, 1, 0, 7, 0, 1, 3, 15, 0, 13, 0, 7, 3, 1, 0, 7, 15, 1, 12, 7, 0, 1, 0, 31, 3, 1, 8, 31, 0, 1, 3, 7, 0, 31, 0, 7, 30, 1, 0, 31, 14, 11, 3, 7, 0, 13, 48, 15, 3, 1, 0, 7, 0, 1, 3, 63, 15, 31, 0, 7, 3, 21, 0, 31, 0, 1, 33, 7, 8, 31, 0, 47, 39, 1, 0, 31, 15, 1, 3, 39, 0, 31, 63
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
By Fermat's little theorem, if p > 2 is prime, then 2^(p-1) == 1 (mod p), thus a(p)=0. If a(n)=0, then n may be only pseudoprime, as for n = 341 = 11*31 [F. Sarrus, 1820].
See A001567 for the list of all pseudoprimes to base 2, i.e., composite numbers which have a(n) = 0, also called Sarrus or Poulet numbers. Carmichael numbers A002997 are pseudoprimes to all (coprime) bases b >= 2. - M. F. Hasler, Mar 13 2020
|
|
LINKS
|
|
|
FORMULA
|
a(n) = M(n-1) - n floor( M(n-1)/n ) = M(n-1) - max{ k in nZ | k <= M(n-1) } where M(k)=2^k-1.
|
|
EXAMPLE
|
a(1)=0 since any integer == 0 (mod 1);
a(2)=1 since 2^1-1 == 1 (mod 2),
a(3)=0 since 3 is a prime > 2,
a(4)=3 since 2^3-1 = 7 == 3 (mod 4);
a(341)=0 since 341=11*31 is a Sarrus number.
|
|
MATHEMATICA
|
|
|
PROG
|
(PARI) a(n)=(1<<(n-1)-1)%n
(PARI) apply( {A128311(n)=lift(Mod(2, n)^(n-1)-1)}, [1..99]) \\ Much more efficient when n becomes very large. - M. F. Hasler, Mar 13 2020
(Python)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|