login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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).
(Formerly N0058)
44
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,4

COMMENTS

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

Moebius transform of floor(n/2). - Paul Barry, Mar 20 2005

Also number of different kinds of regular n-gons, one convex, the others self-intersecting. - Reinhard Zumkeller, Aug 20 2005

From Artur Jasinski, Oct 28 2008: (Start)

Degrees of minimal polynomials of cos(2*Pi/n). The first few are

1: x - 1

2: x + 1

3: 2*x + 1

4: x

5: 4*x^2 + 2*x - 1

6: 2*x - 1

7: 8*x^3 + 4*x^2 - 4*x - 1

8: 2*x^2 - 1

9: 8*x^3 - 6*x + 1

10: 4*x^2 - 2*x - 1

11: 32*x^5 + 16*x^4 - 32*x^3 - 12*x^2 + 6*x + 1

These polynomials have solvable Galois groups, so their roots can be expressed by radicals. (End)

a(n) is the number of rationals p/q in the interval [0,1] such that p + q = n. - Geoffrey Critzer, Oct 10 2011.

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]

From Wolfdieter Lang, Dec 19 2013: (Start)

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.

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.

(End)

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

REFERENCES

G. Polya and G. Szego, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part Eight, Chap. 1, Sect. 6, Problems 60&61.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

LINKS

T. D. Noe, Table of n, a(n) for n=2..10000

K. S. Brown, The Half-Totient Tree

Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.

Eric Weisstein's World of Mathematics, Polygon Triangle Picking

Eric Weisstein's World of Mathematics, Trigonometry Angles

FORMULA

a(n) = phi(n)/2 for n >= 3.

a(n) = Sum(k/n: 1<=k<n and GCD(n, k)=1) = A023896(n)/n for n>2. - Reinhard Zumkeller, Aug 20 2005

EXAMPLE

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

MAPLE

P:=proc(q) local a, k, n; for n from 2 to q do a:=0;

for k from 1 to trunc(n/2) do if gcd(k, n-k)=1 then a:=a+1; fi; od;

print(a); od; end: P(10^3); # Paolo P. Lava, Apr 13 2016

MATHEMATICA

Table[ EulerPhi[n]/2, {n, 3, 50}]

PROG

(PARI) a(n)=if(n<=2, 1, eulerphi(n)/2);

(PARI) /* for printing minimal polynomials of cos(2*Pi/n) */

default(realprecision, 110);

for(n=1, 33, print(n, ": ", algdep(cos(2*Pi/n), a(n))));

(Haskell)

a023022 n = length [(u, v) | u <- [1 .. div n 2],

                             let v = n - u, gcd u v == 1]

-- Reinhard Zumkeller, Jul 30 2014

CROSSREFS

Cf. A000010, A055684, A046657, A049806, A049703, A062956.

Cf. A181875, A181876, A181877, A183918.

Cf. A023896.

Cf. A182972, A182973, A245718.

Sequence in context: A253630 A104481 A078709 * A177501 A100677 A188637

Adjacent sequences:  A023019 A023020 A023021 * A023023 A023024 A023025

KEYWORD

nonn

AUTHOR

N. J. A. Sloane. This was in the 1973 "Handbook", but then was dropped from the database. Resubmitted by David W. Wilson.

EXTENSIONS

Entry revised by N. J. A. Sloane, Jun 10 2012

Polynomials edited with the consent of Artur Jasinski by Wolfdieter Lang, Jan 08 2011

Name clarified by Geoffrey Critzer, Jan 25 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 21 14:50 EST 2017. Contains 281109 sequences.