login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A073758 Smallest number that is neither a divisor of nor relatively prime to n, or 0 if no such number exists. 5
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,6

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)

LINKS

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

EXAMPLE

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}.

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 *)

PROG

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

CROSSREFS

Cf. A045763.

Sequence in context: A291540 A075443 A021250 * A133995 A019629 A073759

Adjacent sequences:  A073755 A073756 A073757 * A073759 A073760 A073761

KEYWORD

nonn

AUTHOR

Labos Elemer, Aug 08 2002

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 9 20:09 EDT 2020. Contains 336326 sequences. (Running on oeis4.)