A109641 - OEIS

%I #13 Mar 27 2019 10:20:24

%S 4,9,15,25,27,34,36,49,51,57,63,68,75,81,87,93,111,121,125,129,132,

%T 138,141,153,155,159,169,177,237,249,258,261,264,267,274,276,279,289,

%U 298,303,324,339,343,357,361,375,381,387,393,411,417,423,441,447,453,477

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

%C 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 Robert Israel, <a href="/A109641/b109641.txt">Table of n, a(n) for n = 1..1000</a>

%e Binomial(3*34,34) == 3^6 (mod 34), so 34 is a member.

%p filter:= proc(n) local p,m,k,t;

%p   if isprime(n) then return false fi;

%p   p:= padic:-ordp(n,3);

%p   p:= p + numtheory:-order(3, n/3^p);

%p   m:= binomial(3*n,n) mod n;

%p   t:= 1;

%p   for k from 1 to p do

%p     t:= t*3 mod n;

%p     if t = m then return true fi;

%p   od:

%p false

%p end proc;

%p select(filter, [$2..1000]); # _Robert Israel_, Nov 12 2017

%t 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 Select[Range[2, 500], okQ] (* _Jean-François Alcover_, Mar 27 2019, after _Robert Israel_ *)

%Y Cf. A019334, A080469, A014127, A109642.

%K nonn

%O 1,1

%A _Ryan Propper_, Aug 05 2005

%E Corrected and extended by _Max Alekseyev_, Sep 13 2009

%E Edited by _Max Alekseyev_, Sep 20 2009