A063985 Partial sums of cototient sequence A051953.

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

Author

Labos Elemer, Sep 06 2001

Keywords

• nonn

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

• Harry J. Smith, Table of n, a(n) for n = 1..1000
• N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

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