login
Pseudoprimes to bases 2, 3, 5 and 7.
5

%I #37 Jul 13 2024 20:38:23

%S 29341,46657,75361,115921,162401,252601,294409,314821,334153,340561,

%T 399001,410041,488881,512461,530881,552721,658801,721801,852841,

%U 1024651,1152271,1193221,1461241,1569457,1615681,1857241,1909001,2100901

%N Pseudoprimes to bases 2, 3, 5 and 7.

%H Amiram Eldar, <a href="/A083739/b083739.txt">Table of n, a(n) for n = 1..7469</a> (terms below 10^12; terms 1..114 from R. J. Mathar)

%H Jens Bernheiden, <a href="https://web.archive.org/web/20160508153313/http://www.mathe-schule.de/download/pdf/Primzahl/PSP.pdf">Pseudoprimes</a> (in German).

%H Fred Richman, <a href="http://math.fau.edu/Richman/carm.htm">Primality testing with Fermat's little theorem</a>.

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>.

%F a(n) = n-th positive integer k(>1) such that 2^(k-1) = 1 (mod k), 3^(k-1) = 1 (mod k), 5^(k-1) = 1 (mod k) and 7^(k-1) = 1 (mod k).

%F A005938 INTERSECT A083737. - _R. J. Mathar_, Feb 07 2008

%e a(1)=29341 since it is the first number such that 2^(k-1) = 1 (mod k), 3^(k-1) = 1 (mod k), 5^(k-1) = 1 (mod k) and 7^(k-1) = 1 (mod k).

%p a001567 := [] : f := fopen("b001567.txt",READ) : bfil := readline(f) : while StringTools[WordCount](bfil) > 0 do if StringTools[FirstFromLeft]("#",bfil ) <> 0 then ; else bfil := sscanf(bfil,"%d %d") ; a001567 := [op(a001567), op(2,bfil) ] ; fi ; bfil := readline(f) ; od: fclose(f) : isPsp := proc(n,b) if n>3 and not isprime(n) and b^(n-1) mod n = 1 then true; else false; fi; end: isA001567 := proc(n) isPsp(n,2) ; end: isA005935 := proc(n) isPsp(n,3) ; end: isA005936 := proc(n) isPsp(n,5) ; end: isA005938 := proc(n) isPsp(n,7) ; end: isA083739 := proc(n) if isA001567(n) and isA005935(n) and isA005936(n) and isA005938(n) then true ; else false ; fi ; end: n := 1: for psp2 from 1 do i := op(psp2,a001567) ; if isA083739(i) then printf("%d %d ",n,i) ; n :=n+1 ; fi ; od: # _R. J. Mathar_, Feb 07 2008

%t Select[ Range[2113920], !PrimeQ[ # ] && PowerMod[2, # - 1, # ] == 1 && PowerMod[3, 1 - 1, # ] == 1 && PowerMod[5, # - 1, # ] == 1 && PowerMod[7, 1 - 1, # ] == 1 & ]

%o (PARI) is(n)=!isprime(n)&&Mod(2,n)^(n-1)==1&&Mod(3,n)^(n-1)==1&&Mod(5,n)^(n-1)==1&&Mod(7,n)^(n-1)==1 \\ _Charles R Greathouse IV_, Apr 12 2012

%Y Cf. A001567, A005935, A005936, A005938.

%Y Proper subset of A083737.

%K nonn

%O 1,1

%A Serhat Sevki Dincer (sevki(AT)ug.bilkent.edu.tr), May 05 2003

%E Edited by _Robert G. Wilson v_, May 06 2003