cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

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).

Original entry on oeis.org

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
Offset: 2

Views

Author

N. J. A. Sloane

Keywords

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
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
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
a(n) is the number of ABC triples with n = c. - Felix Huber, Oct 12 2023

Examples

			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
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

References

  • 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.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

Links

Crossrefs

Cf. A000010, A055684, A046657, A049806, A049703, A062956.
Cf. A181875, A181876, A181877, A183918.
Cf. A023896.
Cf. A182972, A182973, A245497, A245718.

Programs

  • Haskell
    a023022 n = length [(u, v) | u <- [1 .. div n 2],
                             let v = n - u, gcd u v == 1]
-- Reinhard Zumkeller, Jul 30 2014
  • Magma
    [1] cat [EulerPhi(n)/ 2: n in [3..100]]; // Vincenzo Librandi, Aug 19 2018
  • Maple
    A023022 := proc(n)
    if n =2 then
        1;
    else
        numtheory[phi](n)/2 ;
    end if;
end proc:
seq(A023022(n),n=2..60) ; # R. J. Mathar, Sep 19 2017
  • Mathematica
    Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by Vincenzo Librandi, Aug 19 2018 *)
  • PARI
    a(n)=if(n<=2,1,eulerphi(n)/2);
/* 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))));
  • Python
    from sympy.ntheory import totient
def a(n): return 1 if n<3 else totient(n)/2 # Indranil Ghosh, Mar 30 2017

Formula

a(n) = phi(n)/2 for n >= 3.
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
G.f.: x*(x - 1)/2 + (1/2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Apr 13 2017
a(n) = Sum_{d|n} moebius(n/d)*floor(d/2). - Michel Marcus, May 25 2021

Extensions

This was in the 1973 "Handbook", but then was dropped from the database. Resubmitted by David W. Wilson
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

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.