A073758 Smallest number 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, 4, 0, 8, 0, 4, 6, 6, 0, 4, 0, 6, 6, 4, 0, 9, 10, 4, 6, 6, 0, 4, 0, 6, 6, 4, 10, 8, 0, 4, 6, 6, 0, 4, 0, 6, 6, 4, 0, 9, 14, 4, 6, 6, 0, 4, 10, 6, 6, 4, 0, 8, 0, 4, 6, 6, 10, 4, 0, 6, 6, 4, 0, 10, 0, 4, 6, 6, 14, 4, 0, 6, 6, 4, 0, 8, 10, 4, 6, 6, 0, 4, 14, 6, 6, 4, 10, 9, 0, 4, 6

Offset: 1

Author

Labos Elemer, Aug 08 2002

Keywords

• nonn

Comments

Original name: Smallest number of "unrelated set" belonging to n [=URS(n)]. Least number, neither divisor nor relatively prime to n. Or a(n)=0 if unrelated set is empty.

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.

a(6) = A073759(6), a(8) = A073759(8), a(9) = A073759(9). (End)

Examples

			a(20) = 6 since it is the smallest term of the set of numbers m that neither divide nor are coprime to 20, i.e., {6, 8, 12, 14, 15, 16, 18}.
		

Links

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

Crossrefs

Cf. A045763.

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[Min[unr[w]], {w, 1, 128}] (* + or -Infinity is replaced by 0 *)
Table[SelectFirst[Range[4, n - 2], 1 < GCD[#, n] < # &] /. n_ /; MissingQ@ n -> 0, {n, 99}] (* Michael De Vlieger, Mar 28 2016, Version 10.2 *)

PARI

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