|
|
A263350
|
|
Maximum gcd of (p-1)/2 and (q-1)/2 for distinct prime factors p and q of the n-th Carmichael number.
|
|
1
|
|
|
1, 2, 3, 2, 3, 1, 3, 2, 3, 6, 5, 6, 3, 2, 9, 5, 5, 6, 9, 4, 15, 9, 10, 14, 18, 6, 3, 11, 15, 4, 9, 18, 15, 6, 10, 5, 5, 9, 9, 9, 15, 15, 9, 9, 9, 9, 9, 21, 15, 18, 8, 11, 33, 15, 10, 15, 9, 18, 9, 13, 9, 18, 5, 21, 15, 32, 14, 9, 25, 26, 45, 9, 5, 9, 11, 15, 20, 30, 14, 15, 32, 21, 5, 26, 30, 8, 27, 3, 21, 8, 20, 6, 18, 15, 10, 39, 20, 33, 18
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
For n <= 246683 the only cases where a(n) = 1 are n=1 and n=6.
|
|
LINKS
|
|
|
EXAMPLE
|
The first Carmichael number is 561 = 3*11*17, and (3-1)/2=1, (11-1)/2=5 and (17-1)/2=8 are pairwise coprime, so a(1) = 1.
The second Carmichael number is 1105 = 5*13*17, and (5-1)/2=2, (13-1)/2=6, (17-1)/2=8 have largest gcd 2, so a(2) = 2.
The 11th Carmichael number is 41041 = 7*11*13*41, and the gcd of (11-1)/2=5 and (41-1)/2=20 is 5, which is the largest of the gcds of any pair of 3,5,6,20, so a(11) = 5.
|
|
MAPLE
|
f:= proc(m)
local q, Q, i, j;
if isprime(m) then return NULL fi;
if 2 &^ (m-1) mod m <> 1 then return NULL fi;
if not numtheory:-issqrfree(m) then return NULL fi;
Q:= numtheory:-factorset(m);
for q in Q do
if (m-1) mod (q-1) <> 0 then return NULL fi
od:
max(seq(seq(igcd((Q[i]-1)/2, (Q[j]-1)/2), j=1..i-1), i=2..nops(Q)))
end proc:
seq(f(2*m+1), m=1..10^6);
|
|
MATHEMATICA
|
f[m_] := Module[{F}, F = FactorInteger[m][[All, 1]]; Max @ Flatten @ Table[ GCD[(F[[i]]-1)/2, (F[[j]]-1)/2], {i, 2, Length[F]}, {j, 1, i-1}]];
carms = Select[Range[1, 10^6, 2], CompositeQ[#] && Mod[#, CarmichaelLambda[ #]] == 1&];
|
|
PROG
|
(PARI) maxgcd(v)=my(t); for(i=1, #v-1, for(j=i+1, #v, t=max(gcd(v[i], v[j]), t))); t
apply(n->maxgcd(factor(n)[, 1]\2), [561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461]) \\ Charles R Greathouse IV, Nov 13 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|