A072451 Number of odd terms in the reduced residue system of 2*n-1.

1, 1, 2, 3, 3, 5, 6, 4, 8, 9, 6, 11, 10, 9, 14, 15, 10, 12, 18, 12, 20, 21, 12, 23, 21, 16, 26, 20, 18, 29, 30, 18, 24, 33, 22, 35, 36, 20, 30, 39, 27, 41, 32, 28, 44, 36, 30, 36, 48, 30, 50, 51, 24, 53, 54, 36, 56, 44, 36, 48, 55, 40, 50, 63, 42, 65, 54, 36, 68, 69, 46, 60, 56

Offset

1,3

Comments

Given the quasi-order and coach theorems of Hilton and Pedersen (cf. A003558): phi(b) = 2 * k * c with b odd. Dividing through by 2 we obtain phi(b)/2 = k * c which is the same as a(n) = A003558(n-1) * A135303(n-1). Here k refers to the "least exponent" (cf. A003558), while c is the number of coaches for odd b (cf. A135303). - Gary W. Adamson, Sep 25 2012

After the initial term, this is the totient function phi(2n-1)/2 (A037225(n-1)/2). Also a(n) is the number of partitions of the odd number (2n+1) into two ordered relatively prime parts. If p and q are such parts where p > q and p+q = 2n+1 then they can generate primitive Pythagorean triples of the form (p^2 - q^2, 2*p*q, p^2 + q^2). - Frank M Jackson, Oct 30 2012

References

Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, p. 200.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

Formula

a(1) = 1, and for n > 1, a(n) = phi(2n-1)/2. - Benoit Cloitre, Oct 11 2002

It would appear that a(n) = Sum_{k=0..n} abs(Jacobi(k, 2n-2k+1)). - Paul Barry, Jul 20 2005

a(n) = A055034(2*n-1), n >= 1. - Wolfdieter Lang, Feb 07 2020

G.f.: (x + Sum_{n>=1} mu(2n-1) * x^n * (1 + x^(2n-1)) / (1 - x^(2n-1))^2) / 2. - Mamuka Jibladze, Dec 13 2022

Sum_{k=1..n} a(k) ~ c * n^2, where c = 4/Pi^2 = 0.405284... (A185199). - Amiram Eldar, Feb 11 2023

Example

n=105: phi(105)=48 with 24 odd, 24 even; for even n=2k reduced residue system consists only of odd terms, so number of odd terms equals phi(n).
With odd integer 33, A072451(17) = 10 = A003558(16) * A135303(16); or 10 = 5 * 2.

Maple

A072451 := n -> ceil(numtheory:-phi(2*n-1)/2):
seq(A072451(n), n=1..73); # Peter Luschny, Feb 24 2020

Mathematica

gw[x_] := Table[GCD[x, w], {w, 1, x}] rrs[x_] := Flatten[Position[gw[x], 1]] Table[Count[OddQ[rrs[2*w-1]], True], {w, 1, 128}]
(* Additional programs: *)
Table[Count[Range[1, #, 2], k_ /; CoprimeQ[k, #]] &[2 n - 1], {n, 73}] (* or *) Array[If[# == 1, #, EulerPhi[2 # - 1]/2] &, 73] (* Michael De Vlieger, Jul 24 2017 *)

Prog

(PARI) A072451(n) = if(1==n, n, eulerphi(n+n-1)/2); \\ (After Benoit Cloitre's formula) - Antti Karttunen, Jul 24 2017

Crossrefs

Cf. A000010, A037225, A003558, A135303, A055034, A185199.

Sequence in context: A234094 A301853 A141419 * A349669 A023156 A051599

Adjacent sequences: A072448 A072449 A072450 * A072452 A072453 A072454

Keyword

nonn

Author

Labos Elemer, Jun 19 2002

Status

approved