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

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, 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, 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

Offset: 1

Author

Labos Elemer, Aug 15 2002

Keywords

• nonn

Comments

Largest "unrelated" number to n.

From Michael De Vlieger, Mar 28 2016: (Start)

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

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

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

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.

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

Examples

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

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A045763, A073758.

Programs

Mathematica

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[Join[{0}, unr[w]]], {w, 1, 78}]
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 *)
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 *)

PARI

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

Extensions

Name clarified by Sean A. Irvine, Dec 18 2024