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-3 of 3 results.

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

Original entry on oeis.org

0, 1, 3, 5, 9, 11, 17, 21, 27, 31, 41, 45, 57, 63, 71, 79, 95, 101, 119, 127, 139, 149, 171, 179, 199, 211, 229, 241, 269, 277, 307, 323, 343, 359, 383, 395, 431, 449, 473, 489, 529, 541, 583, 603, 627, 649, 695, 711, 753, 773, 805, 829, 881, 899, 939, 963
Offset: 1

Views

Author

Olivier Gérard

Keywords

Comments

Number of elements in the set {(x,y): 1 <= x < y <= n, 1=gcd(x,y)}. - Michael Somos, Jun 13 1999
Number of fractions in (Haros)-Farey series of order n.
The asymptotic limit for the sequence is a(n) ~ 3*n^2/Pi^2. - Martin Renner, Dec 12 2011
2*a(n) is the number of proper fractions reduced to lowest terms with numerator and denominator less than or equal to n in absolute value. - Stefano Spezia, Aug 09 2019

Examples

			x^2 + 3*x^3 + 5*x^4 + 9*x^5 + 11*x^6 + 17*x^7 + 21*x^8 +27*x^9 + ...

References

  • Albert H. Beiler, Recreations in the theory of numbers, New York, Dover, (2nd ed.) 1966, pp. 170-171.

Links

Crossrefs

Cf. A000010, A002088, A018805, A185670.
Column k=2 of triangle A186974.

Programs

  • GAP
    List([1..60],n->Sum([1..n],i->Phi(i)))-1; # Muniru A Asiru, Jul 31 2018
  • Haskell
    a015614 = (subtract 1) . a002088  -- Reinhard Zumkeller, Jul 29 2012
  • Magma
    [-1+&+[EulerPhi(i): i in [1..n]]:n in [1..56]]; // Marius A. Burtea, Aug 09 2019
  • Maple
    with(numtheory): a:=n->add(phi(i),i=1..n): seq(a(n)-1,n=1..60); # Muniru A Asiru, Jul 31 2018
  • Mathematica
    Table[Sum[EulerPhi[m],{m,1,n}]-1,{n,1,56}] (* Geoffrey Critzer, May 16 2014 *)
Table[Length[FareySequence[n]]-2,{n,60}] (* Harvey P. Dale, Jan 30 2025 *)
  • PARI
    {a(n) = if( n<1, 0, sum(k=1,n,eulerphi(k), -1))} /* Michael Somos, Sep 06 2013 */
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A015614(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*A015614(k1)+1)
        j, k1 = j2, n//j2
    return (n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 24 2021

Formula

a(n) = -1 + A002088(n).
a(n) = (A018805(n) - 1)/2. - Reinhard Zumkeller, Apr 08 2006
For n > 1: A214803(a(n)) = A165900(n-1). - Reinhard Zumkeller, Jul 29 2012
a(n) = A018805(n) - A002088(n). - Reinhard Zumkeller, Jan 21 2013
G.f.: (1/(1 - x)) * (-x + Sum_{k>=1} mu(k) * x^k / (1 - x^k)^2). - Ilya Gutkovskiy, Feb 14 2020
a(n) = A000217(n-1) - A185670(n). - Hossein Mahmoodi, Jan 20 2022

Extensions

More terms from Reinhard Zumkeller, Apr 08 2006

A063985 Partial sums of cototient sequence A051953.

Original entry on oeis.org

0, 1, 2, 4, 5, 9, 10, 14, 17, 23, 24, 32, 33, 41, 48, 56, 57, 69, 70, 82, 91, 103, 104, 120, 125, 139, 148, 164, 165, 187, 188, 204, 217, 235, 246, 270, 271, 291, 306, 330, 331, 361, 362, 386, 407, 431, 432, 464, 471, 501, 520, 548, 549, 585, 600, 632, 653, 683
Offset: 1

Views

Author

Labos Elemer, Sep 06 2001

Keywords

Comments

Number of elements in the set {(x,y): 1 <= x <= y <= n, 1 = gcd(x,y)}; a(n) = A000217(n) - A002088(n) = A100613(n) - A185670(n). - Reinhard Zumkeller, Jan 21 2013
8*a(n) is the number of dots not in direct reach via a straight line from the center of a 2*n+1 X 2*n+1 array of dots. - Kiran Ananthpur Bacche, May 25 2022

Links

Crossrefs

Cf. A000010, A000217, A002088, A048290, A051953.

Programs

  • Haskell
    a063985 n = length [()| x <- [1..n], y <- [x..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013
  • Java
    // Save the file as A063985.java to compile and run
import java.util.stream.IntStream;
import java.util.*;
public class A063985 {
  public static int getInvisiblePoints(int n) {
    Set slopes = new HashSet();
    IntStream.rangeClosed(1, n).forEach(i ->
      {IntStream.rangeClosed(1, n).forEach(j ->
        slopes.add(Float.valueOf((float)i/(float)j))); });
    return (n * n - slopes.size() + n - 1) / 2;
  }
  public static void main(String args[]) throws Exception {
    IntStream.rangeClosed(1, 30).forEach(i ->
      System.out.println(getInvisiblePoints(i)));
  }
} // Kiran Ananthpur Bacche, May 25 2022
  • Mathematica
    f[n_] := n(n + 1)/2 - Sum[ EulerPhi@i, {i, n}]; Array[f, 58] (* Robert G. Wilson v *)
Accumulate[Table[n-EulerPhi[n],{n,1,60}]] (* Harvey P. Dale, Aug 19 2015 *)
  • PARI
    { a=0; for (n=1, 1000, write("b063985.txt", n, " ", a+=n - eulerphi(n)) ) } \\ Harry J. Smith, Sep 04 2009
  • Python
    from sympy.ntheory import totient
def a(n): return sum(x - totient(x) for x in range(1,n + 1))
[a(n) for n in range(1, 51)] # Indranil Ghosh, Mar 18 2017
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A063985(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)*(k1*(k1+1)-2*A063985(k1)-1)
        j, k1 = j2, n//j2
    return (2*n+c-j)//2 # Chai Wah Wu, Mar 24 2021

Formula

a(n) = Sum_{x=1..n} (x - phi(x)) = Sum(x) - Sum(phi(x)) = A000217(n) - A002088(n), phi(n) = A000010(n), cototient(n) = A051953(n).
a(n) = n^2 - A091369(n). - Enrique Pérez Herrero, Feb 25 2012
G.f.: x/(1 - x)^3 - (1/(1 - x))*Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 18 2017
a(n) = (1/2 - 3/Pi^2)*n^2 + O(n*log(n)). - Amiram Eldar, Jul 26 2022

Extensions

Corrected by Robert G. Wilson v, Dec 13 2006

A100613 Number of elements in the set {(x,y): 1 <= x,y <= n, gcd(x,y) > 1}.

Original entry on oeis.org

0, 1, 2, 5, 6, 13, 14, 21, 26, 37, 38, 53, 54, 69, 82, 97, 98, 121, 122, 145, 162, 185, 186, 217, 226, 253, 270, 301, 302, 345, 346, 377, 402, 437, 458, 505, 506, 545, 574, 621, 622, 681, 682, 729, 770, 817, 818, 881, 894, 953, 990, 1045, 1046, 1117, 1146, 1209
Offset: 1

Views

Author

Douglas Stones (dssto1(AT)student.monash.edu.au), Dec 02 2004

Keywords

Links

Crossrefs

Cf. A018805, A000290, A185670, A063985, A242114, A229099.

Programs

  • Haskell
    a100613 n = length [()| x <- [1..n], y <- [1..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013
  • Mathematica
    f[n_] := Table[ #^2 &[m], {m, 1, n + 1}] - FoldList[Plus, 1, 2 Array[EulerPhi, n, 2]] (* Gregg K. Whisler, Jun 25 2008 *)
  • PARI
    a(n) = sum(i=1, n, sum(j=1, n, gcd(i,j)>1)); \\ Michel Marcus, Jan 30 2017
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A100613(n): # based on second formula in A018805
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(k1**2-A100613(k1))
        j, k1 = j2, n//j2
    return n+c-j # Chai Wah Wu, Mar 24 2021

Formula

a(n) = A000290(n) - A018805(n) = A185670(n) + A063985(n). - Reinhard Zumkeller, Jan 21 2013
a(n) = Sum_{k = 2..n} A242114(n,k). - Reinhard Zumkeller, May 04 2014
a(n) ~ kn^2, where k = 1 - 6/Pi^2 = 0.39207... (A229099). - Charles R Greathouse IV, Mar 29 2024
Showing 1-3 of 3 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.