cp's OEIS Frontend

A023022 Number of partitions of n into two relatively prime parts. After initial term, this is the "half-totient" function phi(n)/2 (A000010(n)/2).

%I A023022 N0058 #155 Jul 08 2025 17:10:04
%S A023022 1,1,1,2,1,3,2,3,2,5,2,6,3,4,4,8,3,9,4,6,5,11,4,10,6,9,6,14,4,15,8,10,
%T A023022 8,12,6,18,9,12,8,20,6,21,10,12,11,23,8,21,10,16,12,26,9,20,12,18,14,
%U A023022 29,8,30,15,18,16,24,10,33,16,22,12,35,12,36,18,20,18,30,12,39,16,27,20,41,12
%N A023022 Number of partitions of n into two relatively prime parts. After initial term, this is the "half-totient" function phi(n)/2 (A000010(n)/2).
%C A023022 The number of distinct linear fractional transformations of order n. Also the half-totient function can be used to construct a tree containing all the integers. On the zeroth rank we have just the integers 1 and 2: immediate "ancestors" of 1 and 2 are (1: 3,4,6 2: 5,8,10,12) etc. - _Benoit Cloitre_, Jun 03 2002
%C A023022 Moebius transform of floor(n/2). - _Paul Barry_, Mar 20 2005
%C A023022 Also number of different kinds of regular n-gons, one convex, the others self-intersecting. - _Reinhard Zumkeller_, Aug 20 2005
%C A023022 From _Artur Jasinski_, Oct 28 2008: (Start)
%C A023022 Degrees of minimal polynomials of cos(2*Pi/n). The first few are
%C A023022    1: x - 1
%C A023022    2: x + 1
%C A023022    3: 2*x + 1
%C A023022    4: x
%C A023022    5: 4*x^2 + 2*x - 1
%C A023022    6: 2*x - 1
%C A023022    7: 8*x^3 + 4*x^2 - 4*x - 1
%C A023022    8: 2*x^2 - 1
%C A023022    9: 8*x^3 - 6*x + 1
%C A023022   10: 4*x^2 - 2*x - 1
%C A023022   11: 32*x^5 + 16*x^4 - 32*x^3 - 12*x^2 + 6*x + 1
%C A023022 These polynomials have solvable Galois groups, so their roots can be expressed by radicals. (End)
%C A023022 a(n) is the number of rationals p/q in the interval [0,1] such that p + q = n. - _Geoffrey Critzer_, Oct 10 2011
%C A023022 It appears that, for n > 2, a(n) = A023896(n)/n. Also, it appears that a record occurs at n > 2 in this sequence if and only if n is a prime.  For example, records occur at n=5, 7, 11, 13, 17, ..., all of which are prime. - _John W. Layman_, Mar 26 2012
%C A023022 From _Wolfdieter Lang_, Dec 19 2013: (Start)
%C A023022 a(n) is the degree of the algebraic number of s(n)^2 = (2*sin(Pi/n))^2, starting at a(1)=1. s(n) = 2*sin(Pi/n) is the length ratio side/R for a regular n-gon inscribed in a circle of radius R (in some length units). For the coefficient table of the minimal polynomials of s(n)^2 see A232633.
%C A023022 Because for even n, s(n)^2 lives in the algebraic number field Q(rho(n/2)), with rho(k) = 2*cos(Pi/k), the degree is a(2*l) = A055034(l). For odd n, s(n)^2 is an integer in Q(rho(n)), and the degree is a(2*l+1) = A055034(2*l+1) = phi(2*l+1)/2, l >= 1, with Euler's totient phi=A000010 and a(1)=1. See also A232631-A232633.
%C A023022 (End)
%C A023022 Also for n > 2: number of fractions A182972(k)/A182973(k) such that A182972(k) + A182973(k) = n, A182972(n) and A182973(n) provide an enumeration of positive rationals < 1 arranged by increasing sum of numerator and denominator then by increasing numerator. - _Reinhard Zumkeller_, Jul 30 2014
%C A023022 Number of distinct rectangles with relatively prime length and width such that L + W = n, W <= L. For a(17)=8; the rectangles are 1 X 16, 2 X 15, 3 X 14, 4 X 13, 5 X 12, 6 X 11, 7 X 10, 8 X 9. - _Wesley Ivan Hurt_, Nov 12 2017
%C A023022 After including a(1) = 1, the number of elements of any reduced residue system mod* n used by Brändli and Beyne is a(n). See the examples below. - _Wolfdieter Lang_, Apr 22 2020
%C A023022 a(n) is the number of ABC triples with n = c. - _Felix Huber_, Oct 12 2023
%D A023022 G. Pólya and G. Szegő, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part Eight, Chap. 1, Sect. 6, Problems 60&61.
%D A023022 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%H A023022 T. D. Noe, <a href="/A023022/b023022.txt">Table of n, a(n) for n = 2..10000</a>
%H A023022 Gerold Brändli and Tim Beyne, <a href="https://arxiv.org/abs/1504.02757">Modified Congruence Modulo n with Half the Amount of Residues</a>, arXiv:1504.02757 [math.NT], 2016.
%H A023022 K. S. Brown, <a href="http://www.mathpages.com/home/kmath168.htm">The Half-Totient Tree</a>
%H A023022 Tianxin Cai, Zhongyan Shen, and Mengjun Hu, <a href="http://www.oaj.pku.edu.cn/sxjz/EN/10.11845/sxjz.20130409b">On the Parity of the Generalized Euler Function</a>, Advances in Mathematics (China), 2013, 42(4): 505-510.
%H A023022 Daniele A. Gewurz and Francesca Merola, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Gewurz/gewurz5.html">Sequences realized as Parker vectors of oligomorphic permutation groups</a>, J. Integer Seqs., Vol. 6, 2003.
%H A023022 Sameen Ahmed Khan, <a href="https://doi.org/10.13189/ms.2021.090605">Trigonometric Ratios Using Algebraic Methods</a>, Mathematics and Statistics (2021) Vol. 9, No. 6, 899-907.
%H A023022 Wolfdieter Lang, <a href="https://arxiv.org/abs/2008.04300">On the Equivalence of Three Complete Cyclic Systems of Integers</a>, arXiv:2008.04300 [math.NT], 2020.
%H A023022 Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, <a href="https://doi.org/10.7546/nntdm.2024.30.3.516-529">The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences</a>, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 518.
%H A023022 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%H A023022 Pinthira Tangsupphathawat, Takao Komatsu, and Vichian Laohakosol, <a href="https://www.emis.de/journals/JIS/VOL21/Laohakosol/lao8.html">Minimal Polynomials of Algebraic Cosine Values, II</a>, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
%H A023022 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PolygonTrianglePicking.html">Polygon Triangle Picking</a>
%H A023022 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/TrigonometryAngles.html">Trigonometry Angles</a>
%H A023022 Canze Zhu and Qunying Liao, <a href="https://arxiv.org/abs/2105.10870">A recursion formula for the generalized Euler function phi_e(n)</a>, arXiv:2105.10870 [math.NT], 2021.
%F A023022 a(n) = phi(n)/2 for n >= 3.
%F A023022 a(n) = (1/n)*Sum_{k=1..n-1, gcd(n, k)=1} k = A023896(n)/n for n>2. - _Reinhard Zumkeller_, Aug 20 2005
%F A023022 G.f.: x*(x - 1)/2 + (1/2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - _Ilya Gutkovskiy_, Apr 13 2017
%F A023022 a(n) = Sum_{d|n} moebius(n/d)*floor(d/2). - _Michel Marcus_, May 25 2021
%e A023022 a(15)=4 because there are 4 partitions of 15 into two parts that are relatively prime: 14 + 1, 13 + 2, 11 + 4, 8 + 7. - _Geoffrey Critzer_, Jan 25 2015
%e A023022 The smallest nonnegative reduced residue system mod*(n) for n = 1 is {0}, hence a(1) = 1; for n = 9 it is {1, 2, 4}, because 5 == 4 (mod* 9) since -5 == 4 (mod 9), 7 == 2 (mod* 9) and 8 == 1 (mod* 9). Hence a(9) = phi(9)/2 = 3. See the comment on Brändli and Beyne above. - _Wolfdieter Lang_, Apr 22 2020
%p A023022 A023022 := proc(n)
%p A023022     if n =2 then
%p A023022         1;
%p A023022     else
%p A023022         numtheory[phi](n)/2 ;
%p A023022     end if;
%p A023022 end proc:
%p A023022 seq(A023022(n),n=2..60) ; # _R. J. Mathar_, Sep 19 2017
%t A023022 Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by _Vincenzo Librandi_, Aug 19 2018 *)
%o A023022 (PARI) a(n)=if(n<=2,1,eulerphi(n)/2);
%o A023022 /* for printing minimal polynomials of cos(2*Pi/n) */
%o A023022 default(realprecision,110);
%o A023022 for(n=1,33,print(n,": ",algdep(cos(2*Pi/n),a(n))));
%o A023022 (Haskell)
%o A023022 a023022 n = length [(u, v) | u <- [1 .. div n 2],
%o A023022                              let v = n - u, gcd u v == 1]
%o A023022 -- _Reinhard Zumkeller_, Jul 30 2014
%o A023022 (Python)
%o A023022 from sympy.ntheory import totient
%o A023022 def a(n): return 1 if n<3 else totient(n)/2 # _Indranil Ghosh_, Mar 30 2017
%o A023022 (Magma) [1] cat [EulerPhi(n)/ 2: n in [3..100]]; // _Vincenzo Librandi_, Aug 19 2018
%Y A023022 Cf. A000010, A055684, A046657, A049806, A049703, A062956.
%Y A023022 Cf. A181875, A181876, A181877, A183918.
%Y A023022 Cf. A023896.
%Y A023022 Cf. A182972, A182973, A245497, A245718.
%K A023022 nonn,easy
%O A023022 2,4
%A A023022 _N. J. A. Sloane_
%E A023022 This was in the 1973 "Handbook", but then was dropped from the database. Resubmitted by _David W. Wilson_
%E A023022 Entry revised by _N. J. A. Sloane_, Jun 10 2012
%E A023022 Polynomials edited with the consent of _Artur Jasinski_ by _Wolfdieter Lang_, Jan 08 2011
%E A023022 Name clarified by _Geoffrey Critzer_, Jan 25 2015