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,3

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

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A116921.

Sequence in context: A244796 A080391 A273494 * A086898 A123031 A271709

Adjacent sequences: A116919 A116920 A116921 * A116923 A116924 A116925

Keyword

easy,nonn

Author

Leroy Quet, Feb 26 2006

Extensions

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

Status

approved