cp's OEIS Frontend

A109641 Composite n such that binomial(3n, n) == 3^k (mod n) for some integer k > 0.

%I A109641 #13 Mar 27 2019 10:20:24
%S A109641 4,9,15,25,27,34,36,49,51,57,63,68,75,81,87,93,111,121,125,129,132,
%T A109641 138,141,153,155,159,169,177,237,249,258,261,264,267,274,276,279,289,
%U A109641 298,303,324,339,343,357,361,375,381,387,393,411,417,423,441,447,453,477
%N A109641 Composite n such that binomial(3n, n) == 3^k (mod n) for some integer k > 0.
%C A109641 Includes p^k for k >= 2 and p > 2 in A019334 but not in A014127, as binomial(3n,n) is coprime to p and 3 is a primitive root mod p^k. - _Robert Israel_, Nov 12 2017
%H A109641 Robert Israel, <a href="/A109641/b109641.txt">Table of n, a(n) for n = 1..1000</a>
%e A109641 Binomial(3*34,34) == 3^6 (mod 34), so 34 is a member.
%p A109641 filter:= proc(n) local p,m,k,t;
%p A109641   if isprime(n) then return false fi;
%p A109641   p:= padic:-ordp(n,3);
%p A109641   p:= p + numtheory:-order(3, n/3^p);
%p A109641   m:= binomial(3*n,n) mod n;
%p A109641   t:= 1;
%p A109641   for k from 1 to p do
%p A109641     t:= t*3 mod n;
%p A109641     if t = m then return true fi;
%p A109641   od:
%p A109641 false
%p A109641 end proc;
%p A109641 select(filter, [$2..1000]); # _Robert Israel_, Nov 12 2017
%t A109641 okQ[n_] := Module[{p, m}, If[PrimeQ[n], Return[False]]; p = IntegerExponent[n, 3]; p = p + MultiplicativeOrder[3, n/3^p]; m = Mod[Binomial[3n, n], n]; AnyTrue[Range[p], m == PowerMod[3, #, n]&]];
%t A109641 Select[Range[2, 500], okQ] (* _Jean-François Alcover_, Mar 27 2019, after _Robert Israel_ *)
%Y A109641 Cf. A019334, A080469, A014127, A109642.
%K A109641 nonn
%O A109641 1,1
%A A109641 _Ryan Propper_, Aug 05 2005
%E A109641 Corrected and extended by _Max Alekseyev_, Sep 13 2009
%E A109641 Edited by _Max Alekseyev_, Sep 20 2009