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

%I #39 Jul 31 2024 13:14:45

%S 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,

%T 15,15,16,15,17,17,18,17,19,19,20,19,21,21,22,21,23,23,24,23,25,25,26,

%U 25,27,27,28,27,29,29,30,29,31,31,32,31,33,33,34,33,35,35,36,35,37,37

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

%C 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).

%C The arithmetic function v+-(n,2) as defined in A290988. - _Robert Price_, Aug 22 2017

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,0,1,-1).

%F 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).

%F a(n) = (2*n-4-2*(-1)^n+(-1)^(n/2)+(-1)^(3*n/2))/4, n>2. - _Wesley Ivan Hurt_, May 26 2015

%F For n > 2, a(n) = (n-2+cos(n*Pi/2)-cos(n*Pi))/2. - _Wesley Ivan Hurt_, Oct 02 2017

%F G.f.: t^2*(1+t^3-2*t^4+2*t^5)/((1-t)*(1-t^4)). - _Mamuka Jibladze_, Aug 22 2019

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

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

%o (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

%o (PARI) a(n) = {forstep(k = n\2, 0, -1, if (gcd(n, k) == 1, return (k)););} \\ _Michel Marcus_, May 26 2015

%o (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

%o (Python)

%o 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

%Y Cf. A116922, A290988.

%K easy,nonn

%O 1,5

%A _Leroy Quet_, Feb 26 2006

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