|
|
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)
|
|
80
|
|
|
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
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
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)
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
|
|
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
|
|
|
FORMULA
|
a(n) = phi(n)/2 for n >= 3.
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
|
|
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
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
|
|
MAPLE
|
if n =2 then
1;
else
numtheory[phi](n)/2 ;
end if;
end proc:
|
|
MATHEMATICA
|
Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by Vincenzo Librandi, Aug 19 2018 *)
|
|
PROG
|
(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))));
(Haskell)
a023022 n = length [(u, v) | u <- [1 .. div n 2],
let v = n - u, gcd u v == 1]
(Python)
from sympy.ntheory import totient
def a(n): return 1 if n<3 else totient(n)/2 # Indranil Ghosh, Mar 30 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|