A116922 a(n) = smallest integer >= n/2 which is coprime to n.

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

Offset: 1

Author

Leroy Quet, Feb 26 2006

Keywords

• easy
• nonn

Comments

A116921(n) + a(n) = n.

For n>= 3, a(n) - A116921(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).

Links

• Harvey P. Dale, Table of n, a(n) for n = 1..1000
• Index entries for linear recurrences with constant coefficients, signature (1,0,0,1,-1).

Crossrefs

Cf. A116921.

Programs

Mathematica

cp[n_]:=Module[{k=Ceiling[n/2]},While[!CoprimeQ[n,k],k++];k]; Array[cp,80] (* Harvey P. Dale, Nov 06 2013 *)

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 A116922(n): return n+1>>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).

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

Extensions

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