A128311 Remainder upon division of 2^(n-1)-1 by n.

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

Offset: 1

Author

M. F. Hasler, May 04 2007

Keywords

• nonn

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

Examples

			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.
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..2048
• Wikipedia, Fermat's little theorem

Crossrefs

Cf. A001348 (Mersenne numbers), A001567 (Sarrus numbers: pseudoprimes to base 2), A002997 (Carmichael numbers), A084653, A001220 (Wieferich primes).

Programs

Mathematica

Table[Mod[2^(n-1)-1,n],{n,100}] (* Harvey P. Dale, Dec 22 2012 *)

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

def A128311(n): return (pow(2,n-1,n)-1)%n # Chai Wah Wu, Jul 06 2022

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.