A141379 a(n) = the smallest positive integer non-coprime to both n and phi(n), where phi(n) is the number of positive integers that are <= n and are coprime to n.

6, 2, 10, 2, 14, 2, 3, 2, 22, 2, 26, 2, 6, 2, 34, 2, 38, 2, 3, 2, 46, 2, 5, 2, 3, 2, 58, 2, 62, 2, 6, 2, 10, 2, 74, 2, 3, 2, 82, 2, 86, 2, 3, 2, 94, 2, 7, 2, 6, 2, 106, 2, 5, 2, 3, 2, 118, 2, 122, 2, 3, 2, 10, 2, 134, 2, 6, 2, 142, 2, 146, 2, 5, 2, 14, 2, 158, 2, 3, 2, 166, 2, 10, 2, 6, 2, 178, 2

Offset

3,1

Comments

Apparently, for p > 2 a prime, we have a(p) = 2*p. If n is not a prime, then let q be the smallest prime dividing n. phi(n) then has (q-1) as factor. Therefore (q-1)q is neither coprime to n nor phi(n). Since q is the smallest prime dividing n, we have a(n) < n. - Stefan Steinerberger, Jun 29 2008

Links

David A. Corneth, Table of n, a(n) for n = 3..10002

Formula

a(n) = A141327(n, A000010(n)).

Example

a(4) = 2 as phi(4) = 2 and the gcd of the smallest prime factors of 4 and phi(4) is 2 which is smaller than the product of the smallest prime factors (2*2 = 4). - David A. Corneth, Jul 24 2025

Mathematica

a = {}; For[n = 3, n < 80, n++, i = 2; While[Min[GCD[i, n], GCD[EulerPhi[n], i]] == 1, i++ ]; AppendTo[a, i]]; a (* Stefan Steinerberger, Jun 29 2008 *)

Prog

(PARI) a(n) = {my(f = factor(n), s = eulerphi(f), fs = factor(s), res = f[1, 1] * fs[1, 1], g); g = gcd(n, s); if(g > 1, fg = factor(g); return(min(res, fg[1, 1]))); res
} \\ David A. Corneth, Jul 24 2025

Crossrefs

Cf. A141327, A141377, A141378.

Sequence in context: A018801 A055021 A260329 * A357396 A100616 A097474

Adjacent sequences: A141376 A141377 A141378 * A141380 A141381 A141382

Keyword

nonn,easy

Author

Leroy Quet, Jun 28 2008

Extensions

More terms from Stefan Steinerberger, Jun 29 2008

a(78)-a(88) from Ray Chandler, Jun 24 2009

Status

approved