A076388 a(n) = minimum of y-x such that x <= y, x*y = n and gcd(x,y)=1.

0, 1, 2, 3, 4, 1, 6, 7, 8, 3, 10, 1, 12, 5, 2, 15, 16, 7, 18, 1, 4, 9, 22, 5, 24, 11, 26, 3, 28, 1, 30, 31, 8, 15, 2, 5, 36, 17, 10, 3, 40, 1, 42, 7, 4, 21, 46, 13, 48, 23, 14, 9, 52, 25, 6, 1, 16, 27, 58, 7, 60, 29, 2, 63, 8, 5, 66, 13, 20, 3, 70, 1, 72, 35, 22, 15, 4, 7, 78, 11, 80, 39

Offset: 1

Author

T. D. Noe, Oct 11 2002

Keywords

• easy
• nonn

Comments

If n is a prime or a power of a prime, a(n) = n-1. Similar to A056737, which does not have the gcd(x,y)=1 condition.

Examples

			a(12) = 1 because of the possible (x,y) pairs, (1,12), (2,6), (3,4), the pair (3,4) yields the minimum difference and satisfies gcd(x,y)=1.
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..10000 (terms 2..10000 from Ivan Neretin)
• Antti Karttunen, Data supplement: n, a(n) computed for n = 1..100000

Crossrefs

Cf. A034699, A052128, A056737, A354933.

Differs from |A354988(n)| for the first time at n=60, where a(60) = 7, while A354988(60) = -11.

Programs

Mathematica

nMax = 100; Table[dvs = Divisors[n]; i = 1; j = 1; While[n/dvs[[i]] > dvs[[i]], If[GCD[n/dvs[[i]], dvs[[i]]] == 1, j = i]; i++ ]; n/dvs[[j]] - dvs[[j]], {n, 2, nMax}]

PARI

A076388(n) = fordiv(n,d,if((d>=(n/d)) && 1==gcd(d,n/d), return(d-(n/d)))); \\ Antti Karttunen, Jun 16 2022

Formula

a(n) = A354933(n) - A052128(n). - Corrected by Antti Karttunen, Jun 16 2022

Extensions

Definition formally changed from x < y to x <= y, to accommodate the prepended term a(1)=0 - Antti Karttunen, Jun 16 2022