cp's OEIS Frontend

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

%I A072451 #50 Feb 11 2023 08:11:36
%S A072451 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,
%T A072451 20,18,29,30,18,24,33,22,35,36,20,30,39,27,41,32,28,44,36,30,36,48,30,
%U A072451 50,51,24,53,54,36,56,44,36,48,55,40,50,63,42,65,54,36,68,69,46,60,56
%N A072451 Number of odd terms in the reduced residue system of 2*n-1.
%C A072451 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
%C A072451 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
%D A072451 Peter Hilton and Jean Pedersen, A Mathematical Tapestry, Demonstrating the Beautiful Unity of Mathematics, Cambridge University Press, 2010, p. 200.
%H A072451 Antti Karttunen, <a href="/A072451/b072451.txt">Table of n, a(n) for n = 1..10000</a>
%F A072451 a(1) = 1, and for n > 1, a(n) = phi(2n-1)/2. - _Benoit Cloitre_, Oct 11 2002
%F A072451 It would appear that a(n) = Sum_{k=0..n} abs(Jacobi(k, 2n-2k+1)). - _Paul Barry_, Jul 20 2005
%F A072451 a(n) = A055034(2*n-1), n >= 1. - _Wolfdieter Lang_, Feb 07 2020
%F A072451 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
%F A072451 Sum_{k=1..n} a(k) ~ c * n^2, where c = 4/Pi^2 = 0.405284... (A185199). - _Amiram Eldar_, Feb 11 2023
%e A072451 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).
%e A072451 With odd integer 33, A072451(17) = 10 = A003558(16) * A135303(16); or 10 = 5 * 2.
%p A072451 A072451 := n -> ceil(numtheory:-phi(2*n-1)/2):
%p A072451 seq(A072451(n), n=1..73); # _Peter Luschny_, Feb 24 2020
%t A072451 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}]
%t A072451 (* Additional programs: *)
%t A072451 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 *)
%o A072451 (PARI) A072451(n) = if(1==n,n,eulerphi(n+n-1)/2); \\ (After _Benoit Cloitre_'s formula) - _Antti Karttunen_, Jul 24 2017
%Y A072451 Cf. A000010, A037225, A003558, A135303, A055034, A185199.
%K A072451 nonn
%O A072451 1,3
%A A072451 _Labos Elemer_, Jun 19 2002