A049703 -id:A049703 - 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).

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

N. J. A. Sloane

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

			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

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

T. D. Noe, Table of n, a(n) for n = 2..10000
Gerold Brändli and Tim Beyne, Modified Congruence Modulo n with Half the Amount of Residues, arXiv:1504.02757 [math.NT], 2016.
K. S. Brown, The Half-Totient Tree
Tianxin Cai, Zhongyan Shen, and Mengjun Hu, On the Parity of the Generalized Euler Function, Advances in Mathematics (China), 2013, 42(4): 505-510.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Sameen Ahmed Khan, Trigonometric Ratios Using Algebraic Methods, Mathematics and Statistics (2021) Vol. 9, No. 6, 899-907.
Wolfdieter Lang, On the Equivalence of Three Complete Cyclic Systems of Integers, arXiv:2008.04300 [math.NT], 2020.
Jorma K. Merikoski, Pentti Haukkanen, and Timo Tossavainen, The congruence x^n = -a^n (mod m): Solvability and related OEIS sequences, Notes. Num. Theor. Disc. Math. (2024) Vol. 30, No. 3, 516-529. See p. 518.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Pinthira Tangsupphathawat, Takao Komatsu, and Vichian Laohakosol, Minimal Polynomials of Algebraic Cosine Values, II, J. Int. Seq., Vol. 21 (2018), Article 18.9.5.
Eric Weisstein's World of Mathematics, Polygon Triangle Picking
Eric Weisstein's World of Mathematics, Trigonometry Angles
Canze Zhu and Qunying Liao, A recursion formula for the generalized Euler function phi_e(n), arXiv:2105.10870 [math.NT], 2021.

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

a023022 n = length [(u, v) | u <- [1 .. div n 2],
                             let v = n - u, gcd u v == 1]
-- Reinhard Zumkeller, Jul 30 2014

[1] cat [EulerPhi(n)/ 2: n in [3..100]]; // Vincenzo Librandi, Aug 19 2018

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

Join[{1}, Table[EulerPhi[n]/2, {n, 3, 100}]] (* adapted by Vincenzo Librandi, Aug 19 2018 *)

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

from sympy.ntheory import totient
def a(n): return 1 if n<3 else totient(n)/2 # Indranil Ghosh, Mar 30 2017

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

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

A005598 a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).

Original entry on oeis.org

1, 2, 4, 8, 14, 24, 36, 54, 76, 104, 136, 178, 224, 282, 346, 418, 498, 594, 696, 816, 944, 1084, 1234, 1406, 1586, 1786, 1998, 2228, 2470, 2740, 3018, 3326, 3650, 3994, 4354, 4738, 5134, 5566, 6016, 6490, 6980, 7510, 8052, 8636, 9240, 9868, 10518, 11214

Offset: 0

N. J. A. Sloane

Number of possible interleaving orders for n consecutive distinct values from two arithmetic progressions. ABABBBA is impossible, for example, because "ABA" implies that the spacing between B's must be greater than 1/2 the spacing between A's. But "ABBBA" implies that the B-spacing must be less than 1/2 the A-spacing. - Allan C. Wechsler, Mar 16 2005. Since the interchange of A's and B's gives essentially the same order pattern, all terms will be even for n>0.
The SemialgebraicComponents procedure in the Algebra`AlgebraicInequalities` package of Mathematica may be used to determine whether a particular pattern is possible. - John W. Layman, Mar 30 2005
Also, "digital lines": number of straight binary strings of length n [Dorst]. This was the original source for this sequence.
Also, the number of finite Sturmian words of length n. The considered orders are exactly the balanced words, which have been proved to be the factors of Sturmian sequences. An explicit formula was exhibited by Mignosi in 1991. Berstel and Pocchiola gave a geometric proof of this, using Euler's function for counting partitions of a unit cube. - Damien Jamet (jamet(AT)lirmm.fr), Apr 01 2005
The first difference of a(n) is the number of 'special' words, prefix of two Sturmian words of length n+1; see A002088. The second difference of a(n) is the number of palindromic 'bispecial' words, prefix and suffix of two Sturmian words of length n+1; see A000010. - Fred Lunnon, Sep 05 2010
Conjectured to be the number of regions in a Farey fan of order n. See A360042 for further details. - Scott R. Shannon, Jan 24 2023

			a(4) = 14 because of the 16 possible four-letter words from an alphabet of two letters, only AABB and BBAA are not possible interleaving orders for two arithmetic progressions.
For n=7, the pattern BAAAABA gives a possible ordering for the two arithmetic progressions {A, A+a, A+2a, A+3a,...} and {B, B+b, B+2b, B+3b,...} if the system of inequalities {a>0, b>0, A<B, B < A+a, A+4a<B+b, B+b < A+5a, A+5a<B+2b} has a solution. (Note: A<B is included to preclude a fifth A-term from lying between the two B-terms; similarly, A+5a<B+2b is included to preclude a second B-term from lying between the final two A-terms.) The SemialgebraicComponents procedure gives the solution {A,a,B,b}={0,1,1/8,4}; thus BAAAABA is one of the 54 possible orders of length 7. - _John W. Layman_, Mar 30 2005

L. Dorst and A. W. M. Smeulders, Discrete straight line segments: parameters, primitives and properties. Vision geometry (Hoboken, NJ, 1989), 45-62, Contemp. Math., 119, Amer. Math. Soc., Providence, RI, 1991.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
C. A. Berenstein and D. Lavine, A Geometric Approach to Subpixel Registration Accuracy, CVGIP 40, 1987, 334-360.
C. A. Berenstein and D. Lavine, On the Number of Digital Straight Line Segments, IEEE PAMI, vol.10, no.6, 1988, 880-887
J. Berstel and M. Pocchiola, A geometric proof of the enumeration formula for Sturmian words, Internat. J. Algeb. Comput., 3(3):349-355, 1993.
Michelangelo Bucci, Alessandro De Luca, Amy Glen and Luca Q. Zamboni, A connection between palindromic and factor complexity using return words, arXiv:0802.1332 [math.CO], 2008.
Aldo de Luca and Stefano Varricchio, Finiteness and regularity in semigroups and formal languages, Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 1999. x+240 pp. ISBN: 3-540-63771-0 MR1696498 (2000g:68001). See p. 25.
L. Dorst, Discrete Straight Line Segments: Parameters, Primitives and Properties, Ph. D. Dissertation, Delft Univ. Technology, 1986. See p. 85.
L. Dorst and A. W. M. Smeulders, Discrete Representation of Straight Lines, IEEE PAMI-6, no.4, 1984, pp. 450-463.
F. Mignosi, On the Number of Factors of Sturmian Words, Theor. Comput. Sci. 82(1): 71-84 (1991)

Cf. A000010, A002088, A011755, A049695, A049703, A103116.

a005598 n = 1 + sum (zipWith (*) [n, n - 1 .. 1] a000010_list)
-- Reinhard Zumkeller, Apr 14 2013

A005598:= func< n | n eq 0 select 1 else 1 +(&+[(n-j+1)*EulerPhi(j): j in [1..n]]) >;
[A005598(n): n in [0..60]]; // G. C. Greubel, Dec 07 2022

f:= m -> add((m-i+1)*phi(i),i=1..m)+1; (Jamet)

Accumulate@Accumulate@EulerPhi@Range[0,100]+1 (* Vladimir Joseph Stephan Orlovsky, Apr 21 2011 *)
Nest[Accumulate[#]&,EulerPhi[Range[0,50]],2]+1 (* Harvey P. Dale, Feb 07 2015 *)

a(n) = 1 + sum(i=1, n, (n-i+1)*eulerphi(i)); \\ Michel Marcus, Aug 04 2016

@CachedFunction
def A005598(n): return 1 + sum( (n-j+1)*euler_phi(j) for j in range(1,n+1) )
[A005598(n) for n in range(61)] # G. C. Greubel, Dec 07 2022

a(n) = 2*A049703(n) for n >= 1.
a(n) = Sum_{i=0..n} A049695(i,n-i). - Clark Kimberling
Asymptotically, a(n) behaves like n^3/Pi^2. - Leo Dorst (leo(AT)science.uva.nl), Apr 02 2007
G.f.: 1/(1 - x) + (1/(1 - x)^2)*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 16 2017
a(n) = 1 + (n+1)*A002088(n) - A011755(n). - G. C. Greubel, Dec 07 2022

Extended by John W. Layman, Mar 30 2005
More terms from Emeric Deutsch, Feb 04 2006
Entry revised by N. J. A. Sloane, Apr 04 2007
Minor English revisions by Jeffrey Shallit, Aug 04 2016

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A005598 a(n) = 1 + Sum_{i=1..n} (n-i+1)*phi(i).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

SageMath

Formula

Extensions

A049695 Array T read by diagonals; T(i,j) is the number of nonnegative slopes of lines determined by 2 lattice points in [ 0,i ] X [ 0,j ] if i > 0; T(0,j)=1 if j > 0; T(0,0)=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions