A116921 a(n) = largest integer <= n/2 which is coprime to n.

0, 1, 1, 1, 2, 1, 3, 3, 4, 3, 5, 5, 6, 5, 7, 7, 8, 7, 9, 9, 10, 9, 11, 11, 12, 11, 13, 13, 14, 13, 15, 15, 16, 15, 17, 17, 18, 17, 19, 19, 20, 19, 21, 21, 22, 21, 23, 23, 24, 23, 25, 25, 26, 25, 27, 27, 28, 27, 29, 29, 30, 29, 31, 31, 32, 31, 33, 33, 34, 33, 35, 35, 36, 35, 37, 37

Offset: 1

Author

Leroy Quet, Feb 26 2006

Keywords

• easy
• nonn

Comments

a(n) + A116922(n) = n. For n>= 3, A116922(n) - a(n) is 1 if n is odd, is 2 if n is a multiple of 4 and is 4 if n is congruent to 2 (mod 4).

The arithmetic function v+-(n,2) as defined in A290988. - Robert Price, Aug 22 2017

Links

• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Crossrefs

Cf. A116922, A290988.

Programs

Magma

[0] cat [(2*n-4-2*(-1)^n+(-1)^(n div 2)+(-1)^(3*n div 2)) div 4: n in [3..80]]; // Vincenzo Librandi, May 26 2015

Mathematica

Join[{0, 1}, Table[(2 n - 4 - 2 (-1)^n + (-1)^(n/2) + (-1)^(3 n/2))/4, {n, 3, 50}]] (* Wesley Ivan Hurt, May 26 2015 *)
Table[Which[OddQ[n],(n-1)/2,Divisible[n,4],n/2-1,Mod[n,4]==2,n/2-2],{n,80}]//Abs (* Harvey P. Dale, Jun 24 2017 *)

PARI

a(n) = {forstep(k = n\2, 0, -1, if (gcd(n, k) == 1, return (k)););} \\ Michel Marcus, May 26 2015

PARI

a(n) = {if(n%2, (n-1)/2, if(n==2, 1, n/2 - if(n%4, 2, 1)))} \\ Andrew Howroyd, Aug 22 2019

Python

def A116921(n): return n>>1 if n&1 or n==2 else (n>>1)-(2 if n&2 else 1) # Chai Wah Wu, Jul 31 2024

Formula

For n >= 3, a(n) = (n-1)/2 if n is odd, a(n) = n/2 - 1 if n is a multiple of 4 and a(n) = n/2 - 2 if n is congruent to 2 (mod 4).

a(n) = (2*n-4-2*(-1)^n+(-1)^(n/2)+(-1)^(3*n/2))/4, n>2. - Wesley Ivan Hurt, May 26 2015

For n > 2, a(n) = (n-2+cos(n*Pi/2)-cos(n*Pi))/2. - Wesley Ivan Hurt, Oct 02 2017

G.f.: t^2*(1+t^3-2*t^4+2*t^5)/((1-t)*(1-t^4)). - Mamuka Jibladze, Aug 22 2019

Extensions

More terms from Wyatt Lloyd (wal118(AT)psu.edu), Mar 25 2006