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.

Showing 1-5 of 5 results.

A005728 Number of fractions in Farey series of order n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, 43, 47, 59, 65, 73, 81, 97, 103, 121, 129, 141, 151, 173, 181, 201, 213, 231, 243, 271, 279, 309, 325, 345, 361, 385, 397, 433, 451, 475, 491, 531, 543, 585, 605, 629, 651, 697, 713, 755, 775, 807, 831, 883, 901, 941, 965
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Sometimes called Phi(n).
Leo Moser found an interesting way to generate this sequence, see Gardner.
a(n) is a prime number for nine consecutive values of n: n = 1, 2, 3, 4, 5, 6, 7, 8, 9. - Altug Alkan, Sep 26 2015
Named after the English geologist and writer John Farey, Sr. (1766-1826). - Amiram Eldar, Jun 17 2021

Examples

			a(5)=11 because the fractions are 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1.

References

  • Martin Gardner, The Last Recreations, 1997, chapter 12.
  • Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics, a foundation for computer science, Chapter 4.5 - Relative Primality, pages 118 - 120 and Chapter 9 - Asymptotics, Problem 6, pages 448 - 449, Addison-Wesley Publishing Co., Reading, Mass., 1989.
  • William Judson LeVeque, Topics in Number Theory, Addison-Wesley, Reading, MA, 2 vols., 1956, Vol. 1, p. 154.
  • Andrey O. Matveev, Farey Sequences, De Gruyter, 2017, Table 1.7.
  • Leo Moser, Solution to Problem P42, Canadian Mathematical Bulletin, Vol. 5, No. 3 (1962), pp. 312-313.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

For the Farey series see A006842/A006843.
Essentially the same as A049643.
Cf. A002088, A055197, A055201.

Programs

  • GAP
    List([0..60],n->Sum([1..n],i->Phi(i)))+1; # Muniru A Asiru, Jul 31 2018
  • Haskell
    a005728 n = a005728_list
a005728_list = scanl (+) 1 a000010_list
-- Reinhard Zumkeller, Aug 04 2012
  • Magma
    [1] cat [n le 1 select 2 else Self(n-1)+EulerPhi(n): n in [1..60]]; // Vincenzo Librandi, Sep 27 2015
  • Maple
    A005728 := proc(n)
    1+add(numtheory[phi](i),i=1..n) ;
end proc:
seq(A005728(n),n=0..80) ; # R. J. Mathar, Nov 29 2017
  • Mathematica
    Accumulate@ Array[ EulerPhi, 54, 0] + 1
f[n_] := 1 + Sum[ EulerPhi[m], {m, n}]; Array[f, 55, 0] (* or *)
f[n_] := (Sum[ MoebiusMu[m] Floor[n/m]^2, {m, n}] + 3)/2; f[0] = 1; Array[f, 55, 0] (* or *)
f[n_] := n (n + 3)/2 - Sum[f[Floor[n/m]], {m, 2, n}]; f[0] = 1; Array[f, 55, 0] (* Robert G. Wilson v, Sep 26 2015 *)
a[n_] := If[n == 0, 1, FareySequence[n] // Length];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 16 2022 *)
  • PARI
    a(n)=1+sum(k=1,n,eulerphi(k)) \\ Charles R Greathouse IV, Jun 03 2013
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A005728(n): # based on second formula in A018805
    if n == 0:
        return 1
    c, j = -2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(2*A005728(k1)-3)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

Formula

a(n) = 1 + Sum_{i=1..n} phi(i).
a(n) = n*(n+3)/2 - Sum_{k=2..n} a(floor(n/k)). - David W. Wilson, May 25 2002
a(n) = a(n-1) + phi(n) with a(0) = 1. - Arkadiusz Wesolowski, Oct 13 2012
a(n) = 1 + A002088(n). - Robert G. Wilson v, Sep 26 2015

A295820 Number of nonnegative solutions to (x,y) = 1 and x^2 + y^2 <= n.

Original entry on oeis.org

0, 2, 3, 3, 3, 5, 5, 5, 5, 5, 7, 7, 7, 9, 9, 9, 9, 11, 11, 11, 11, 11, 11, 11, 11, 13, 15, 15, 15, 17, 17, 17, 17, 17, 19, 19, 19, 21, 21, 21, 21, 23, 23, 23, 23, 23, 23, 23, 23, 23, 25, 25, 25, 27, 27, 27, 27, 27, 29, 29, 29, 31, 31, 31, 31, 35, 35, 35, 35, 35, 35
Offset: 0

Views

Author

Seiichi Manyama, Nov 28 2017

Keywords

Examples

			Solutions to (x,y) = 1 and x^2 + y^2 <= 17;
  *         (1,4)
  * *       (1,3), (2,3)
  *   *     (1,2), (3,2)
* * * * *   (0,1), (1,1), (2,1), (3,1), (4,1)
  *         (1,0)
            a(17) = 11.

Links

Crossrefs

Cf. A049643, A224212, A295819, A295849.

Programs

  • Mathematica
    a[n_] := Sum[Boole[GCD[i, j]==1 ], {i, 0, Sqrt[n]}, {j, 0, Sqrt[n-i^2]}];
Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Jul 05 2018, after Andrew Howroyd *)
  • PARI
    a(n) = {sum(i=0, sqrtint(n), sum(j=0, sqrtint(n-i^2), gcd(i, j) == 1))} \\ Andrew Howroyd, Dec 12 2017

Formula

a(n) = a(n-1) + A295819(n) for n > 0.

A049641 a(n) = Sum_{i=0..n} ((-1)^i)*T(i,n-i), array T as in A049639.

Original entry on oeis.org

0, 0, 2, 0, 3, 0, 5, 0, 7, 0, 11, 0, 13, 0, 19, 0, 23, 0, 29, 0, 33, 0, 43, 0, 47, 0, 59, 0, 65, 0, 73, 0, 81, 0, 97, 0, 103, 0, 121, 0, 129, 0, 141, 0, 151, 0, 173, 0, 181, 0, 201, 0, 213, 0, 231, 0, 243, 0, 271, 0, 279, 0, 309, 0, 325, 0, 345, 0, 361, 0, 385
Offset: 0

Views

Author

Clark Kimberling

Keywords

Links

Crossrefs

Cf. A005728, A049643.

Programs

  • Mathematica
    a[0 | 1, 0 | 1] = 0; a[0 | 1, ] = a[, 0 | 1] = 1; a[i_, j_]:= Module[{slopes, cnt}, slopes = Union@Flatten@Table[(k - j)/(h - i), {h, 0, i - 1}, {k, 0, j - 1}]; cnt[slope_] := Count[Flatten[Table[{h, k}, {h, 0, i - 1}, {k, 0, j - 1}], 1], {h_, k_} /; (k - j)/(h - i) == slope]; Count[cnt /@ slopes, c_ /; c >= 2] + 2]; Table[Sum[(-1)^k*a[k, n - k], {k, 0, n}], {n, 0, 25}] (* G. C. Greubel, Dec 07 2017 *)

Extensions

Terms a(42) onward added by G. C. Greubel, Dec 07 2017

A049632 a(n) = T(n,n), array T as in A049627.

Original entry on oeis.org

1, 4, 6, 10, 14, 22, 26, 38, 46, 58, 66, 86, 94, 118, 130, 146, 162, 194, 206, 242, 258, 282, 302, 346, 362, 402, 426, 462, 486, 542, 558, 618, 650, 690, 722, 770, 794, 866, 902, 950, 982, 1062, 1086, 1170, 1210, 1258, 1302, 1394, 1426, 1510, 1550, 1614, 1662
Offset: 0

Views

Author

Clark Kimberling

Keywords

Crossrefs

Cf. A049627, A049643, A005728.

Programs

  • PARI
    T(n,k) = (n+1)*(k+1) - sum(i=0, n, sum(j=0, k, gcd(i,j)>1)); \\ A049627
a(n) = T(n, n); \\ Michel Marcus, Aug 06 2021

Formula

a(n) = 2*A005728(n) if n>=1. - R. J. Mathar, Feb 05 2008

Extensions

More terms from Sean A. Irvine, Aug 05 2021

A255541 a(n) = 1+Sum_{k=1..2^n-1} A000010(k).

Original entry on oeis.org

1, 2, 5, 19, 73, 309, 1229, 4959, 19821, 79597, 318453, 1274563, 5097973, 20397515, 81591147, 326371001, 1305482159, 5222040189, 20888133573, 83552798667, 334211074959, 1336845501841, 5347382348679, 21389531880435, 85558125961121, 342232529890275, 1368930120480617, 5475720508827645, 21902882035220391, 87611528574186091, 350446114129452131, 1401784457568941917, 5607137830212707769
Offset: 0

Views

Author

Robert G. Wilson v, Feb 24 2015

Keywords

Comments

Number of fractions in Farey series of order 2^n-1.

Examples

			For each n, measure the size of the set of reduced fractions with a denominator less than 2^n:
a(0) = 1 since the set of reduced fractions with denominator less than 2^0 = 1 is {0}.
a(1) = 2 since the set of reduced fractions with denominator less than 2^1 = 2 is {0, 1}.
a(2) = 5 since the set of reduced fractions with denominator less than 2^2 = 4 is {0, 1/3, 1/2, 2/3, 1}.
a(3) = 19 since the set of reduced fractions with denominator less than 2^3 = 8 is {0, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1}.

Links

Crossrefs

Cf. A007305, A007306, A000010, A049643, A006842/A006843 (Farey fractions).

Programs

  • Mathematica
    k = s = 1; lst = {}; Do[While[k < 2^n, s = s + EulerPhi@ k; k++]; AppendTo[lst, s], {n, 0, 26}]; lst
a[n_] := 1 + (1/2) Sum[ MoebiusMu[k]*Floor[n/k]*Floor[1 + n/k], {k, n}]; Array[a, 27, 0]

Formula

a(n) ~ (2^n-1)^2 / Pi.
a(n) = 2+A015614(2^n-1).
a(n) = A005728 (2^n-1). - Michel Marcus, Feb 27 2015
a(n) = (3+A018805(2^n-1))/2. - Colin Linzer, Aug 06 2025
Showing 1-5 of 5 results.

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

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