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

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)

Links

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

Example

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

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[unr[w]], {w, 1, 128}]; (for empty sets 0 was used).
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 *)

Prog

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

Crossrefs

Cf. A045763, A073758.

Sequence in context: A073758 A133995 A019629 * A066760 A102393 A228131

Adjacent sequences: A073756 A073757 A073758 * A073760 A073761 A073762

Keyword

nonn

Author

Labos Elemer, Aug 15 2002

Extensions

Name clarified by Sean A. Irvine, Dec 18 2024

Status

approved