A002088 -id:A002088 - cp's OEIS frontend

A046657 a(n) = A002088(n)/2.

1, 2, 3, 5, 6, 9, 11, 14, 16, 21, 23, 29, 32, 36, 40, 48, 51, 60, 64, 70, 75, 86, 90, 100, 106, 115, 121, 135, 139, 154, 162, 172, 180, 192, 198, 216, 225, 237, 245, 265, 271, 292, 302, 314, 325, 348, 356, 377, 387, 403, 415, 441, 450, 470, 482

Offset: 2

N. J. A. Sloane

nonn

a(n) = |{(x,y) : 1 <= x <= y <= n, x + y <= n, 1 = gcd(x,y)}| = |{(x,y) : 1 <= x <= y <= n, x + y > n, 1 = gcd(x,y)}|. - Steve Butler, Mar 31 2006

Brousseau proved that if the starting numbers of a generalized Fibonacci sequence are <= n (for n > 1) then the number of such sequences with relatively prime successive terms is a(n). - Amiram Eldar, Mar 31 2017

Giovanni Resta, Table of n, a(n) for n = 2..10000
Alfred Brousseau, A Note on the Number of Fibonacci Sequences, The Fibonacci Quarterly, Vol. 10, No. 6 (1972), pp. 657-658.

Cf. A002088.

Partial sums of A023022.

List([2..60],n->Sum([1..n],k->Phi(k)/2)); # Muniru A Asiru, Mar 05 2018

a:=n->sum(numtheory[phi](k),k=1..n): seq(a(n)/2, n=2..60); # Muniru A Asiru, Mar 05 2018

Rest@ Accumulate[EulerPhi@ Range@ 56]/2 (* Michael De Vlieger, Apr 02 2017 *)

a(n) = sum(k=1, n, eulerphi(k))/2; \\ Michel Marcus, Apr 01 2017

from functools import lru_cache
@lru_cache(maxsize=None)
def A046657(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(4*A046657(k1)-1)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//4 # Chai Wah Wu, Mar 25 2021

a(n) = 1/2 + Sum_{iJoseph Wheat, Feb 22 2018

A064018 a(n) = A002088(10^n) = Sum_{k <= 10^n} phi(k), sum of the Euler totients phi = A000010.

Original entry on oeis.org

1, 32, 3044, 304192, 30397486, 3039650754, 303963552392, 30396356427242, 3039635516365908, 303963551173008414, 30396355092886216366, 3039635509283386211140, 303963550927059804025910, 30396355092702898919527444, 3039635509270144893910357854, 303963550927013509478708835152

Offset: 0

Robert G. Wilson v, Sep 07 2001

nonn

Asymptotically, A002088(n) ~ 0.30396355...*n^2 = (3/Pi^2)*n^2, see A104141 and A002088. - Michael B. Porter, Mar 08 2013 [corrected by M. F. Hasler, Apr 18 2015]

			a(1) = phi(1) + ... + phi(10) = 1 + 1 + 2 + 2 + 4 + 2 + 6 + 4 + 6 + 4 = 32.

Lucas A. Brown, Table of n, a(n) for n = 0..19 (terms 0..18 from Hiroaki Yamanouchi)
Lucas A. Brown, Python program.
Lucas Augustus Brown, Computation of the Totient Summatory Function, arXiv:2506.07386 [math.NT], 2025.
Eric Weisstein's World of Mathematics, Totient Summatory Function.
Wikipedia, Totient summatory function.

Cf. A000010, A002088, A104141.

s = 0; k = 1; Do[ While[ k <= 10^n, s = s + EulerPhi[ k ]; k++ ]; Print[ s ], {n, 0, 8} ]

# See LINKS. - Lucas A. Brown, Jun 08 2025

a(n) = Sum_{k <= 10^n} A000010(k).

More terms from Robert G. Wilson v, Sep 07 2001
a(10)-a(11) from Donovan Johnson, Feb 06 2010
a(12) from Donovan Johnson, Feb 07 2012
a(13)-a(14) from Hiroaki Yamanouchi, Jul 06 2014
a(15) from Asif Ahmed, Apr 16 2015
Name edited by Michel Marcus and M. F. Hasler, Apr 16 and Apr 18 2015

A143270 a(n) = n*A002088(n).

Original entry on oeis.org

1, 4, 12, 24, 50, 72, 126, 176, 252, 320, 462, 552, 754, 896, 1080, 1280, 1632, 1836, 2280, 2560, 2940, 3300, 3956, 4320, 5000, 5512, 6210, 6776, 7830, 8340, 9548, 10368, 11352, 12240, 13440, 14256, 15984, 17100, 18486, 19600, 21730, 22764, 25112

Offset: 1

Gary W. Adamson, Aug 03 2008

nonn

Also number of reduced fractions with denominators <= n and values between 1/n and n (inclusive). - Reinhard Zumkeller, Jan 15 2009

			a(4) = 24 = n*A002088(n) = 4*6.
a(4) = 24 = sum of row 4 terms of triangle A143269: (4 + 4 + 8 + 8).
a(3) = #{1/3,1/2,2/3,1,4/3,3/2,5/3,2,7/3,5/2,8/3,3} = 12. - _Reinhard Zumkeller_, Jan 15 2009

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Cf. A000010, A002088, A143269.

Module[{nn=50,ps},ps=Accumulate[EulerPhi[Range[nn]]];Times@@@Thread[{Range[nn],ps}]] (* Harvey P. Dale, Jun 04 2023 *)

list(nmax) = {my(s = vector(nmax, k, eulerphi(k))); for(k = 2, nmax, s[k] += s[k-1]); for(k = 1, nmax, s[k] = k*s[k]); s} \\ Amiram Eldar, Jun 01 2025

from functools import lru_cache
@lru_cache(maxsize=None)
def A143270(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A143270(k1)//k1-1)
        j, k1 = j2, n//j2
    return n*(n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 25 2021

a(n) = n*A002088(n), where A002088(n) = partial sums of phi(n).
Equals row sums of triangle A143269.
a(n) = Sum_{i=1..n} Sum_{j=1..i*n} 0^(gcd(i,j)-1). - Reinhard Zumkeller, Jan 15 2009
a(n) = (3/Pi^2) * n^3 + O(n^2*log(n)). - Amiram Eldar, Jun 01 2025

More terms from Reinhard Zumkeller, Jan 15 2009

A262669 Consider the Farey sequence of order n, F_n, and that the average distance between any two adjacent pairs in F_n is 1/A002088(n). Then a(n) is the number of adjacent pairs whose difference is less than the average.

Original entry on oeis.org

0, 0, 0, 2, 2, 2, 4, 6, 8, 8, 12, 14, 18, 18, 20, 26, 28, 32, 32, 40, 42, 46, 48, 58, 58, 66, 76, 78, 84, 88, 94, 100, 106, 114, 120, 126, 128, 142, 150, 162, 166, 178, 178, 194, 200, 206, 214, 230, 236, 246, 250, 266, 274, 292, 296, 312, 322, 338, 344, 360, 360, 388, 400, 408, 416, 436

Offset: 0

Robert G. Wilson v, Sep 26 2015

nonn

Because the Farey fractions are symmetrical about 1/2, a(n) is always even.
Conjecture: this is a monotonic sequence. For n = 0, 1, 3, 4, 8, 12, 17, 23, 41 & 59, a(n) = a(n+1).
If instead the question is when the difference is equal to the average, then the sequence becomes 0, 1, 2, 0, 2, 2, 2, 0, 0, 2, 0, 2, 0, 0, 0, 2, 2, 0, 2, 2, 0, 2, 0, 0, 2, 2, ..., . A262670.
Conjecture: Twice the number of pairs less than the average (2*A262669) plus the number of pairs which equal the average (A262670) never exceed the number of pairs which are greater than the average for n greater than 245.
   f( 1000) =   100972,
   f( 2000) =   403750,
   f( 3000) =   908068,
   f( 4000) =  1614072,
   f( 5000) =  2522376,
   f( 6000) =  3631762,
   f( 7000) =  4943332,
   f( 8000) =  6456904,
   f( 9000) =  8171296,
   f(10000) = 10088132.

			a(5) = 2. F_5 = {0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1} and the first forward difference is {1/5, 1/20, 1/12, 1/15, 1/10, 1/10, 1/15, 1/12, 1/20, 1/5}. The average distance is 1/10 since A002088(5) = 10 which is also the number of adjacent pairs, a/b & c/d.

Albert H. Beiler, Recreations in the Theory of Numbers, The Queen of Mathematics Entertains, Chapter XVI, "Farey Tails", Dover Books, NY, 1966, pgs 168-172.

Robert G. Wilson v, Table of n, a(n) for n = 0..5000
Cut the Knot, Farey Series.
The University of Surrey, Math Dept., Fractions in the Farey Series and the Stern-Brocot Tree.
Eric Weisstein's World of Mathematics, Farey Sequence.
Wikipedia, Farey Sequence.

Cf. A002088, A005728, A006843, A262670.

f[n_] := Block[{diff = Differences@ Union@ Flatten@ Table[a/b, {b, n}, {a, 0, b}], ave = 1/Sum[ EulerPhi[ m], {m, n}]}, {Length@ Select[diff, ave < # &], Length@ Select[diff, ave == # &], Length@ Select[diff, ave > # &]}]; Array[ f[#][[1]] &, 65, 0]

a(n) = (n/Pi)^2 + O(n/3*(log(n))^(2/3)*(log(log(n)))^(4/3)), (A. Walfisz 1963).

A262670 Consider the Farey sequence of order n, F_n, and that the average distance between any two adjacent pairs in F_n is 1/A002088(n). Then a(n) is the number of adjacent pairs whose difference is the average.

Original entry on oeis.org

0, 1, 2, 0, 2, 2, 2, 0, 0, 2, 0, 2, 0, 0, 0, 2, 2, 0, 2, 2, 0, 2, 0, 0, 2, 2, 0, 2, 0, 2, 0, 2, 0, 0, 0, 0, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 2, 2, 0, 2, 2, 2, 0, 2, 2, 2, 0, 0, 0, 0, 4, 0, 0, 0, 6, 0, 0, 2, 4, 2, 0, 2, 0, 0, 2, 2, 0, 0, 2, 0, 0, 0, 0, 2, 0, 0, 2, 0, 2, 0, 2, 2, 2, 2, 0, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0

Offset: 0

Robert G. Wilson v, Nov 09 2015

nonn

Because the Farey fractions are symmetrical about 1/2 for n > 1, a(n) is always even.
First occurrence of k by index, or -1 if no such occurrence exists: 0, 1, 2, -1, 60, -1, 64, -1, 207, -1, 1047, -1, 1084, -1, ..., .
Where 0 occurs: 0, 3, 7, 8, 10, 12, 13, 14, 17, 20, 22, 23, 26, 28, 30, 32, 33, ..., ;
Where 2 occurs: 2, 4, 5, 6, 9, 11, 15, 16, 18, 19, 21, 24, 25, 27, 29, 31, 36, 37, 38, ..., ;
Where 4 occurs: 60, 68, 120, 129, 148, 158, 159, 168, 180, 216, 225, 231, 239, 241, 249, ..., ;
Where 6 occurs: 65, 227, 401, 403, 492, 600, 616, 780, 861, 862, 865, 967, 1019, 1054, ..., ;
Where 8 occurs: 208, 1210, 1367, 1803, 1804, 1841, 1866, 2397, 2864, 3281, 3443, 3724, ..., ;
Where 10 occurs: 1048, 1094, 1632, 1949, 2269, 2571, 2710, 3365, 3555, 3558, 3613, 3939, ..., ;
Where 12 occurs: 1085, 1358, 2541, 3251, 4411, ..., ;
Where 18 occurs: 4830, ..., ;
For the first 5001 terms: 3315 zeros, 1 one, 1138 twos, 414 fours, 96 sixes, 19 eights, 12 tens, 5 twelves and 1 eighteen.

			a(5) = 2. F_5 = {0, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1} and the first forward difference is {1/5, 1/20, 1/12, 1/15, 1/10, 1/10, 1/15, 1/12, 1/20, 1/5}. The average distance is 1/10 since A002088(5) = 10 which is also the number of adjacent pairs, a/b & c/d.

Albert H. Beiler, Recreations in the Theory of Numbers, The Queen of Mathematics Entertains, Chapter XVI, "Farey Tails", Dover Books, NY, 1966, pgs 168-172.

Cut the Knot, Farey Series.
The University of Surrey, Math Dept., Fractions in the Farey Series and the Stern-Brocot Tree.
Eric Weisstein's World of Mathematics, Farey Sequence.
Wikipedia, Farey Sequence.

Cf. A002088, A005728, A006843, A262669.

f[n_] := Block[{diff = Differences@ Union@ Flatten@ Table[a/b, {b, n}, {a, 0, b}], ave = 1/Sum[ EulerPhi[ m], {m, n}]}, {Length@ Select[diff, ave < # &], Length@ Select[diff, ave == # &], Length@ Select[diff, ave > # &]}]; Array[f, 65]

A285022 Numbers n such that A002088(n) < 3n^2/Pi^2.

Original entry on oeis.org

820, 1276, 1926, 2080, 2640, 3160, 3186, 3250, 4446, 4720, 4930, 5370, 6006, 6546, 7386, 7450, 7476, 9066, 9276, 10626, 10836, 13146, 13300, 15640, 15666, 16056, 16060, 16446, 17020, 17466, 17550, 17766, 18040, 18910, 19176, 19230, 19416, 20736, 21000, 21246

Offset: 1

Amiram Eldar, Apr 08 2017

nonn

James Joseph Sylvester conjectured in 1883 that A002088(n) > 3n^2/Pi^2 for all n.
M. L. N. Sarma found the first counterexample, 820, in 1936.
Paul Erdős and Harold N. Shapiro proved in 1951 that A002088(n)- 3n^2/Pi^2 changes signs at infinitely many values of n, thus this sequence is infinite.
R. A. MacLeod proved in 1987 that A002088(n)/n^2 - 3/Pi^2 has a minimum at the second term, 1276.

			A002088(820) = 204376, 3*820^2/(Pi^2) = 204385.091643... > 204376, thus 820 is in this sequence.

Sukumar Das Adhikari, The Average Behaviour of the Number of Solutions of a Diophantine Equation and an Averaging Technique, Number Theory: Diophantine, Computational, and Algebraic Aspects: Proceedings of the International Conference Held in Eger, Hungary, July 29-August 2, 1996. Walter de Gruyter, 1998.
Władysław Narkiewicz, Rational Number Theory in the 20th Century, Springer London, 2012, p. 215.
M. L. N. Sarma, On the Error Term in a Certain Sum, Proceedings of the Indian Academy of Sciences, Section A, Vol. 3, No. 1 (1936), pp. 338-338.

Amiram Eldar and Giovanni Resta, Table of n, a(n) for n = 1..10000 (first 97 terms from Amiram Eldar)
Paul Erdős and Harold N. Shapiro, On the Changes of Sign of a Certain Error Function, Canadian Journal of Mathematics, Vol. 3 (1951), pp. 375-385.
R. A. MacLeod, The Minimum of Phi(x)/x^2, Journal of the London Mathematical Society, Vol. 1, No. 1 (1967), pp. 652-660.
James Joseph Sylvester, Note sur le théoreme de Legendre citée dans une note insérée dans les Comptes rendus, Comptes rendus hebdomadaires des seances de l'Academie des sciences, Vol. 46 (1883), pp. 463-465.
James Joseph Sylvester, On the Number of Fractions Contained in any "Farey series" of which the Limiting Number is Given, Philosophical Magazine, Series 5, Vol. 15, No. 94 (1883), pp. 251-257.

Cf. A000010, A002088.

F:= ListTools:-PartialSums(map(numtheory:-phi, [$1..30000])):
select(t -> is(F[t] < 3*t^2/Pi^2), [$1..30000]); # Robert Israel, Apr 21 2017

s = 0; k = 1; lst = {}; While[k < 50001, s = s + EulerPhi@k; If[s*Pi^2 < 3 k^2, AppendTo[lst, k]]; k++]; lst

A143231 a(n) = A000010(n) * A002088(n).

Original entry on oeis.org

1, 2, 8, 12, 40, 24, 108, 88, 168, 128, 420, 184, 696, 384, 576, 640, 1536, 612, 2160, 1024, 1680, 1500, 3784, 1440, 4000, 2544, 4140, 2904, 7560, 2224, 9240, 5184, 6880, 5760, 9216, 4752, 15552, 8100, 11376, 7840, 21200, 6504, 24528, 12080, 15072, 14300

Offset: 1

Gary W. Adamson, Jul 31 2008

nonn

			a(5) = 40 = A000010(5) * A002088(5) = 4 * 10.
a(5) = 40 = sum of row 5 terms of triangle A143230: (4 + 4 + 8 + 8 + 16).

Nathaniel Johnston, Table of n, a(n) for n = 1..2500

Cf. A000010, A002088, A143230.

A143231:= func< n | EulerPhi(n)*(&+[EulerPhi(k): k in [1..n]]) >;
[A143231(n): n in [1..50]]; // G. C. Greubel, Sep 10 2024

with(numtheory):
a := proc(n) return phi(n)*add(phi(k),k=1..n): end:
seq(a(n),n=1..46); # Nathaniel Johnston, Jun 26 2011

a[n_]:= a[n]= EulerPhi[n]*Sum[EulerPhi[k], {k,n}];
Table[a[n], {n,50}] (* G. C. Greubel, Sep 10 2024 *)

a(n)=sum(k=1, n, eulerphi(k))*eulerphi(n) \\ Charles R Greathouse IV, Feb 21 2013

def A143231(n): return euler_phi(n)*sum(euler_phi(k) for k in range(1,n+1))
[A143231(n) for n in range(1,51)] # G. C. Greubel, Sep 10 2024

a(n) = A000010(n) * A002088(n).

a(n) = Sum_{k=1..n} A143230(n,k) (row sums of A143230).

Terms after a(14) from Nathaniel Johnston, Jun 26 2011

A038576 CONTINUANT transform of {phi(n)}, 1, 1, 2, 2, 4, 2, .. (A002088).

Original entry on oeis.org

1, 2, 5, 12, 53, 118, 761, 3162, 19733, 82094, 840673, 3444786, 42178105, 256513416, 2094285433, 17010796880, 274267035513, 1662613009958, 30201301214757, 243273022728014, 2949477573950925, 29738048762237264, 657186550343170733, 5287230451507603128

Offset: 1

N. J. A. Sloane, Jun 11 2002

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..200
N. J. A. Sloane, Transforms

Cf. A002088.

with(numtheory):
a:= proc(n) option remember; `if`(n<0, 0,
      `if`(n=0, 1, phi(n) *a(n-1) +a(n-2)))
    end:
seq(a(n), n=1..30);  # Alois P. Heinz, Aug 17 2013

A098199 Continued fraction expansion for Pi^4/36, the limiting value of A024916(n)/A002088(n).

Original entry on oeis.org

2, 1, 2, 2, 1, 1, 46, 459, 2, 3, 1, 2, 2, 1, 1, 8, 18, 1, 1, 1, 1, 6, 5, 6, 14, 1, 2, 1, 1, 140, 1, 2, 1, 1, 2, 1, 9, 16, 1, 2, 1, 1, 1, 15, 1, 3, 55, 1, 1, 12, 1, 1, 5, 4, 6, 13, 2, 2, 7, 2, 32, 1, 1, 6, 1, 1, 54, 1, 1, 1, 21, 1, 2, 1, 3, 4, 5, 15, 1, 6, 1, 2, 5, 1, 1, 7, 1, 834, 2, 1, 4, 8, 3, 2, 3, 1, 5

Offset: 0

Labos Elemer, Sep 21 2004

Amiram Eldar, Table of n, a(n) for n = 0..10000

Cf. A024916, A002088, A098198 (decimal expansion).

Mathematica
```
ContinuedFraction[(Pi^4)/36, 256]
```

contfrac(Pi^4/36) \\ Amiram Eldar, Mar 08 2025

Offset changed by Andrew Howroyd, Aug 04 2024

A140466 a(n) = 4*A002088(n).

Original entry on oeis.org

0, 4, 8, 16, 24, 40, 48, 72, 88, 112, 128, 168, 184, 232, 256, 288, 320, 384, 408, 480, 512, 560, 600, 688, 720, 800, 848, 920, 968, 1080, 1112, 1232, 1296, 1376, 1440, 1536, 1584, 1728, 1800, 1896, 1960, 2120, 2168, 2336, 2416, 2512, 2600, 2784, 2848, 3016, 3096

Offset: 0

Ed Pegg Jr, Jun 29 2008

nonn

Number of distinct slopes in an n X n grid.

Al Zimmermann, Table of n, a(n) for n = 0..49999
Achim Flammenkamp, Cube 3

Cf. A002088.

from functools import lru_cache
@lru_cache(maxsize=None)
def A140466(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 0, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(A140466(k1)//2-1)
        j, k1 = j2, n//j2
    return 2*(n*(n-1)-c+j) # Chai Wah Wu, Mar 25 2021

cp's OEIS Frontend

A046657 a(n) = A002088(n)/2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Python

Formula

A064018 a(n) = A002088(10^n) = Sum_{k <= 10^n} phi(k), sum of the Euler totients phi = A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A143270 a(n) = n*A002088(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A262669 Consider the Farey sequence of order n, F_n, and that the average distance between any two adjacent pairs in F_n is 1/A002088(n). Then a(n) is the number of adjacent pairs whose difference is less than the average.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A262670 Consider the Farey sequence of order n, F_n, and that the average distance between any two adjacent pairs in F_n is 1/A002088(n). Then a(n) is the number of adjacent pairs whose difference is the average.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

A285022 Numbers n such that A002088(n) < 3n^2/Pi^2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

A143231 a(n) = A000010(n) * A002088(n).

Views

Author