A163209 Catalan pseudoprimes: odd composite integers n=2*m+1 satisfying A000108(m) == (-1)^m * 2 (mod n).

5907, 1194649, 12327121

Offset: 1

Author

Peter Luschny, Jul 24 2009

Keywords

• nonn
• hard
• more
• bref

Comments

Also, Wilson spoilers: composite n which divide A056040(n-1) - (-1)^floor(n/2). For the factorial function, a Wilson spoiler is a composite n that divides (n-1)! + (-1). Lagrange proved that no such n exists. For the swinging factorial (A056040), the situation is different.

Also, composite odd integers n=2*m+1 such that A000984(m) == (-1)^m (mod n).

Contains squares of A001220. In particular, a(2) = A001220(1)^2 = 1093^2 = 1194649 = A001567(274) and a(3) = A001220(2)^2 = 3511^2 = 12327121 = A001567(824).

See the Vardi reference for a binomial setup.

Aebi and Cairns 2008, page 9: a(4) either has more than 2 factors or is > 10^10. - Dana Jacobsen, May 27 2015

a(4) > 10^10. - Dana Jacobsen, Mar 03 2018

References

• I. Vardi, Computational Recreations in Mathematica, 1991, p. 66.

Links

• C. Aebi, G. Cairns (2008). "Catalan numbers, primes and twin primes". Elemente der Mathematik 63 (4): 153-164. doi:10.4171/EM/103
• Peter Luschny, Die schwingende Fakultät und Orbitalsysteme, August 2011.
• Peter Luschny, Swinging Primes.
• Index entries for sequences related to pseudoprimes

Programs

Maple

swing := proc(n) option remember; if n = 0 then 1 elif irem(n, 2) = 1 then swing(n-1)*n else 4*swing(n-1)/n fi end:
WS := proc(f,r,n) select(p->(f(p-1)+r(p)) mod p = 0,[$2..n]);
select(q -> not isprime(q),%) end:
A163209 := n -> WS(swing,p->(-1)^iquo(p+2,2),n);

PARI

v(n,p)=my(s); n*=2; while(n\=p, s+=n%2); s
is(n)=if(n%2==0,return(0)); my(m=Mod(1,n),a=n\2); fordiv(n,d,if(isprime(d) && v(a,d), return(0))); forprime(p=2,a, m*=p^v(a,p)); forprime(p=a+1,n,m*=p); m==(-1)^a
forcomposite(n=4,2e7, if(is(n), print1(n", "))) \\ Charles R Greathouse IV, Mar 06 2015

Perl

# Reasonable for isolated values, slow for the sequence:
use ntheory ":all";
sub is { my $m = ($[0]-1)>>1; (binomial($m<<1,$m) % $[0]) == (($m&1) ? $_[0]-1 : 1); }
foroddcomposites { say if is($) } 2e7;  # _Dana Jacobsen, May 03 2015

Perl

# Much faster for sequential testing:
use Math::GMPz; use ntheory ":all"; { my($c,$l)=(Math::GMPz->new(1),1); sub catalan { while ($[0] > $l) { $l++; $c *= 4*$l-2; Math::GMPz::Rmpz_divexact_ui($c,$c,$l+1); } $c; } } my $m; foroddcomposites { $m = ($-1)>>1; say if (catalan($m) % $) == (($m&1) ? $-2 : 2); } 2e7;  # Dana Jacobsen, May 03 2015

Extensions

a(1) = 5907 = 3*11*179 was found by S. Skiena

Typo corrected Peter Luschny, Jul 25 2009

Edited by Max Alekseyev, Jun 22 2012