login
Largest number that is neither a divisor of nor relatively prime to n, or 0 if no such number exists.
6

%I #20 Mar 29 2016 23:37:34

%S 0,0,0,0,0,4,0,6,6,8,0,10,0,12,12,14,0,16,0,18,18,20,0,22,20,24,24,26,

%T 0,28,0,30,30,32,30,34,0,36,36,38,0,40,0,42,42,44,0,46,42,48,48,50,0,

%U 52,50,54,54,56,0,58,0,60,60,62,60,64,0,66,66,68,0,70,0,72,72,74,70,76

%N Largest number that is neither a divisor of nor relatively prime to n, or 0 if no such number exists.

%C Largest "unrelated" number to n.

%C From _Michael De Vlieger_, Mar 28 2016 (Start):

%C Primes n have no unrelated numbers m < n since all such numbers are coprime to n.

%C Unrelated numbers m must be composite since primes must either divide or be coprime to n.

%C m = 1 is not counted as unrelated as it divides and is coprime to n.

%C a(4) = 0 since 4 is the smallest composite and unrelated numbers m with respect to n must be composite and smaller than n. All other composite n have at least one unrelated number m.

%C The test for unrelated numbers m that belong to n is 1 < gcd(m, n) < m.

%C (End)

%H Michael De Vlieger, <a href="/A073759/b073759.txt">Table of n, a(n) for n = 1..10000</a>

%e n = 20: unrelated set to 20 = {6,8,12,14,15,16,18},largest is a(20) = 18.

%t tn[x_] := Table[w, {w, 1, x}]; di[x_] := Divisors[x]; dr[x_] := Union[di[x], rrs[x]]; rrs[x_] := Flatten[Position[GCD[tn[x], x], 1]]; unr[x_]: =Complement[tn[x], dr[x]]; Table[Max[unr[w]], {w, 1, 128}]; (for empty sets 0 was used).

%t Table[t = Select[r = Range[n - 1], Divisible[n, #] || GCD[n, #] == 1 &]; Max[Join[{0}, Complement[r, t]]], {n, 78}] (* _Jayanta Basu_, Jul 09 2013 *)

%t Table[SelectFirst[Range[n - 2, 2, -1], 1 < GCD[#, n] < # &] /. n_ /; MissingQ@ n -> 0, {n, 100}] (* _Michael De Vlieger_, Mar 28 2016, Version 10.2 *)

%o (PARI) a(n) = {forstep(k=n-2, 1, -1, if ((gcd(n,k) != 1) && (n % k), return (k));); 0;} \\ _Michel Marcus_, Mar 29 2016

%Y Cf. A045763, A073758.

%K nonn

%O 1,6

%A _Labos Elemer_, Aug 15 2002