A086748: Odd numbers m such that when C(2k, k) == 1 (mod m) then k is necessarily even.

A086748: Odd numbers m such that when C(2k, k) == 1 (mod m) then k is necessarily even.

[3, 5, 9, 15, 21, 25, 27, 33, 35, 39, 45, 51, 55, 57, 63, 65, 69, 75, 81, 85, 87, 93, 95, 99, 105, 111, 115, 117, 123, 125, 129, 135, 141, 145, 147, 153, 155, 159, 165, 171, 175, 177, 183, 185, 189, 195, 201, 205, 207, 213, 215, 219, 225, 231, 235, 237, 243, 245]

Robert Israel & MaxAl: Odd is important: all even numbers “voidly” satisfy the definition because C(2k,k) is always even, thus never ==1 (mod even m), so for even m, any k such that ==1 (mod m) [which never happens], is always even.

COMMENT: If m is a term, then m*t is also a term for odd numbers t.

Theorem 1: if C(2k, k) == 1 (mod 3) then k is necessarily even. If C(2k, k) == 2 (mod 3) then k is necessarily odd.

Proof: for k < 6 it is correct. We have C(6r, 3r) == C(2r, r) (mod 3) and C(6r+4, 3r+2) == C(2r, r)C(4, 2) == 0 (mod 3). Suppose k is the least value such that theorem 1 is incorrect, then k must be of the form 3r+1. But C(6r+2, 3r+1) == C(2r, r)C(2, 1) (mod 3), which means that r is a smaller counterexample, a contradiction!

===> therefore all multiples of 3 are in the sequence

Theorem 2: if C(2k, k) == 1 or 4 (mod 5) then k is necessarily even. If C(2k, k) == 2 or 3 (mod 5) then k is necessarily odd.

Note that C(10r, 5r) == C(2r, r) (mod 5), C(10r+2, 5r+1) == C(2r, r)C(2, 1) (mod 5), C(10r+4, 5r+2) == C(2r, r)C(4, 2) (mod 5), C(10r+6, 5r+3) == C(2r, r)C(6, 3) (mod 5) and C(10r+8, 5r+4) == C(2r, r)C(8, 4) (mod 5). The proof is similar to that of theorem 1. (End)

===> therefore all multiples of 5 are in the sequence

Up to m < 1000, all odd m are either of the form 3(2t-1) or 5(2t-1) (as proved by Jinyuan Wang) and in the sequence, or not in the sequence because an odd k <= 7412629 exists such that C(2k, k) == 1 (mod m). - Giovanni Resta, Apr 05 2020

Is this A005408 \ A007775 ? - Antti Karttunen, Jul 11 2024

A005408 = the odd numbers

A007775 Numbers not divisible by 2, 3 or 5.

= 1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, 83, 89, 91, 97, 101, 103, 107, 109, 113, 119, 121, 127, 131, 133, 137, 139, 143, 149, 151, 157, 161, 163, 167, 169, 173, 179, 181, 187, 191, 193, 197, 199, 203, 209

Clearly, all numbers in O35 := A005408 \ A007775, i.e., odd numbers divisible by either 3 or 5, are in A086748.

Q: Do we also have : ( x in A086748 => x in O35 ) ?

Counter-Example would be: x in A086748 but x not in O35, i.e., x not divisible by 3 or 5

*/

chk(S)={ my(L = S[#S], N=[]); /* assume the set S is complete. extend to twice the upper limit by multiplying */
  forstep(k = 3, L\S[1]+1, 2, N = setunion(N, [x | x <- k*S, L < x && x < 2*L]));  
  print("New terms: ", N);
  print("Odd numbers to check: ", L = setminus([x+1 | x <- [S[#S]\/2 .. N[#N]\2]*2], N))
}

EXAMPLE:

• m = 7 is not a term because C(2k,k) = 1 (mod 7) is solvable by the odd k=17.
• m = 11 is not a term because C(2k,k) = 1 (mod 11) is solvable by the odd k=13.
• m = 13 is not a term because C(2k,k) = 1 (mod 13) is solvable by the odd k=2383.
• m = 23 is not a term because C(2k,k) = 1 (mod 23) is solvable by the odd k=3391. - R. J. Mathar, Jul 11 2024

disprove(m, u=Mod(1,m))=forstep(k=1,oo,2,binomial(2*k,k)==u && return(k))

foreach(A5,x,print1([x,disprove(x)]", "))

[1, 1], [7, 17], [11, 13], [13, 2383], [17, 37], [19, 3], [23, 3391], [29, 185], [31, 129], [37, 419], [41, 95], [43, 139], [47, 7], 
[49, 7373], [53, 497], [59, 21], [61, 89], [67, 27], [71, 319], [73, 7], [77, 23], [79, 191], [83, 277], [89, 25], [91, 33635], [97, 137], 
[101, 1957], [103, 347], [107, 879], [109, 889], [113, 47], [119, 57], [121, 411], [127, 263], [131, 63], [133, 57], [137, 63], [139, 143],

%152 = [[1, 1], [7, 17], [11, 13], [13, 2383], [17, 37], [19, 3], [23, 3391], [29, 185], [31, 129], [37, 419], [41, 95], [43, 139], [47, 7], 
[49, 7373], [53, 497], [59, 21], [61, 89], [67, 27], [71, 319], [73, 7], [77, 23], [79, 191], [83, 277], [89, 25], [91, 33635], [97, 137], 
[101, 1957], [103, 347], [107, 879], [109, 889], [113, 47], [119, 57], [121, 411], [127, 263], [131, 63], [133, 57], [137, 63], [139, 143]]

[x[2]|x<-res]
%153 = [1, 17, 13, 2383, 37, 3, 3391, 185, 129, 419, 95, 139, 7, 7373, 497, 21, 89, 27, 319, 7, 23, 191, 277, 25, 33635, 137, 1957, 347, 
        879, 889, 47, 57, 411, 263, 63, 57, 63, 143]

gp > foreach(A5,x,x>139 && print1(disprove(x)", "))
62561, 363, 1679, 861,
  ***   at top-level: ...reach(A5,x,x>139&&print1(disprove(x)", "))
  ***   in function disprove: forstep(k=1,oo,2,binomial(2*k,k)==u&&return(k)
  *** binomial: the PARI stack overflows !
  current stack size: 8000000 (7.629 Mbytes)
  [hint] set 'parisizemax' to a nonzero value in your GPRC

==> we need a function that efficiently computes C(2k,k) mod m.

R.J.Mathar gives a “filter” in a SeqFan post:

Instead of (mod m), compute it (mod p) for the smallest prime divisor of m. (Necessary condition.)

(Several simplifications and improvements of the Maple code:)

LucasT(n,k,p)={ if(n>=k, my(kp = digits(k,p), np = digits(n,p)[-#kp..-1]);
                prod(i=1, #kp, binomial(np[i], kp[i]), Mod(1,p)))}

/* note : using the largest instead of smallest prime factor makes it ~ 3x faster */ 
apply( {A373469(n, m=A007775(n))=m==1 || forstep(k=1, oo, 2, LucasT(2*k, k, vecmax(factor(m)[,1]))==1
  && (isprime(m) || binomial(2*k, k)%m==1) && return(k))}, [1..1])

(yes, “disprove()” is now oeis.org/A373469 :-)

further improvements

• the most problematic cases are squarefree m-values:
  • ``` n A373469(n) m = A007775(n) 43 285735 161 = 7 * 23 50 206349 187 = 11 * 17 56 179817 209 = 11 * 19 58 7205 217 = 7 * 31 59 99271 221 = 13 * 17 68 62561 253 = 11 * 23 77 358549 287 = 7 * 41

foreach([43,50,56,58,59,68,77],n,printf(“%d %10s %d = %s\n”,n,999, m=A007775(n), factor(m)))

LucasT(n,k,p)={ if(n>=k, my(kp = digits(k,p), np = digits(n,p)[-#kp..-1]); prod(i=1, #kp, binomial(np[i], kp[i]), Mod(1,p)))}

## by-product: C_mod(n, k, m)

C_mod(n, k, m) = { if ( isprime(m), my(kp = digits(k,m), np = digits(n,m)[-#kp..-1]); prod(i=1, #kp, binomial(np[i],kp[i]), Mod(1,m)), /* else: / my(f=factor(m)); if ( vecmax(f[,2]) > 1, / not squarefree */ C(n,k) % m, chinese([C_mod(n,k,p) | p <- f[,1]]) ) )} ```