cp's OEIS Frontend

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

%I A128311 #24 Jul 07 2022 01:48:39
%S A128311 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,
%T A128311 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,
%U A128311 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
%N A128311 Remainder upon division of 2^(n-1)-1 by n.
%C A128311 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].
%C A128311 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
%H A128311 T. D. Noe, <a href="/A128311/b128311.txt">Table of n, a(n) for n = 1..2048</a>
%H A128311 Wikipedia, <a href="http://en.wikipedia.org/wiki/Fermat&#39;s_little_theorem">Fermat's little theorem</a>
%F A128311 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.
%e A128311 a(1)=0 since any integer == 0 (mod 1);
%e A128311 a(2)=1 since 2^1-1 == 1 (mod 2),
%e A128311 a(3)=0 since 3 is a prime > 2,
%e A128311 a(4)=3 since 2^3-1 = 7 == 3 (mod 4);
%e A128311 a(341)=0 since 341=11*31 is a Sarrus number.
%t A128311 Table[Mod[2^(n-1)-1,n],{n,100}] (* _Harvey P. Dale_, Dec 22 2012 *)
%o A128311 (PARI) a(n)=(1<<(n-1)-1)%n
%o A128311 (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
%o A128311 (Python)
%o A128311 def A128311(n): return (pow(2,n-1,n)-1)%n # _Chai Wah Wu_, Jul 06 2022
%Y A128311 Cf. A001348 (Mersenne numbers), A001567 (Sarrus numbers: pseudoprimes to base 2), A002997 (Carmichael numbers), A084653, A001220 (Wieferich primes).
%K A128311 nonn
%O A128311 1,4
%A A128311 _M. F. Hasler_, May 04 2007