|
%I N0058 #138 Oct 16 2023 03:33:27
%S 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 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 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 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 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 Moebius transform of floor(n/2). - _Paul Barry_, Mar 20 2005
%C Also number of different kinds of regular n-gons, one convex, the others self-intersecting. - _Reinhard Zumkeller_, Aug 20 2005
%C From _Artur Jasinski_, Oct 28 2008: (Start)
%C Degrees of minimal polynomials of cos(2*Pi/n). The first few are
%C 1: x - 1
%C 2: x + 1
%C 3: 2*x + 1
%C 4: x
%C 5: 4*x^2 + 2*x - 1
%C 6: 2*x - 1
%C 7: 8*x^3 + 4*x^2 - 4*x - 1
%C 8: 2*x^2 - 1
%C 9: 8*x^3 - 6*x + 1
%C 10: 4*x^2 - 2*x - 1
%C 11: 32*x^5 + 16*x^4 - 32*x^3 - 12*x^2 + 6*x + 1
%C These polynomials have solvable Galois groups, so their roots can be expressed by radicals. (End)
%C 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 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 From _Wolfdieter Lang_, Dec 19 2013: (Start)
%C 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 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 (End)
%C 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 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 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 a(n) is the number of ABC triples with n = c. - _Felix Huber_, Oct 12 2023
%D 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 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%H T. D. Noe, <a href="/A023022/b023022.txt">Table of n, a(n) for n = 2..10000</a>
%H 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 K. S. Brown, <a href="http://www.mathpages.com/home/kmath168.htm">The Half-Totient Tree</a>
%H 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 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 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 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 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PolygonTrianglePicking.html">Polygon Triangle Picking</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TrigonometryAngles.html">Trigonometry Angles</a>
%H 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 a(n) = phi(n)/2 for n >= 3.
%F 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 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 a(n) = Sum_{d|n} moebius(n/d)*floor(d/2). - _Michel Marcus_, May 25 2021
%e 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 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 := proc(n)
%p if n =2 then
%p 1;
%p else
%p numtheory[phi](n)/2 ;
%p end if;
%p end proc:
%p seq(A023022(n),n=2..60) ; # _R. J. Mathar_, Sep 19 2017
%t Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by _Vincenzo Librandi_, Aug 19 2018 *)
%o (PARI) a(n)=if(n<=2,1,eulerphi(n)/2);
%o /* for printing minimal polynomials of cos(2*Pi/n) */
%o default(realprecision,110);
%o for(n=1,33,print(n,": ",algdep(cos(2*Pi/n),a(n))));
%o (Haskell)
%o a023022 n = length [(u, v) | u <- [1 .. div n 2],
%o let v = n - u, gcd u v == 1]
%o -- _Reinhard Zumkeller_, Jul 30 2014
%o (Python)
%o from sympy.ntheory import totient
%o def a(n): return 1 if n<3 else totient(n)/2 # _Indranil Ghosh_, Mar 30 2017
%o (Magma) [1] cat [EulerPhi(n)/ 2: n in [3..100]]; // _Vincenzo Librandi_, Aug 19 2018
%Y Cf. A000010, A055684, A046657, A049806, A049703, A062956.
%Y Cf. A181875, A181876, A181877, A183918.
%Y Cf. A023896.
%Y Cf. A182972, A182973, A245497, A245718.
%K nonn,easy
%O 2,4
%A _N. J. A. Sloane_. This was in the 1973 "Handbook", but then was dropped from the database. Resubmitted by _David W. Wilson_.
%E Entry revised by _N. J. A. Sloane_, Jun 10 2012
%E Polynomials edited with the consent of _Artur Jasinski_ by _Wolfdieter Lang_, Jan 08 2011
%E Name clarified by _Geoffrey Critzer_, Jan 25 2015
|
