%I #61 Jul 26 2022 12:43:32
%S 0,1,2,4,5,9,10,14,17,23,24,32,33,41,48,56,57,69,70,82,91,103,104,120,
%T 125,139,148,164,165,187,188,204,217,235,246,270,271,291,306,330,331,
%U 361,362,386,407,431,432,464,471,501,520,548,549,585,600,632,653,683
%N Partial sums of cototient sequence A051953.
%C 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
%C 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
%H Harry J. Smith, <a href="/A063985/b063985.txt">Table of n, a(n) for n = 1..1000</a>
%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%F 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).
%F a(n) = n^2 - A091369(n). - _Enrique PĂ©rez Herrero_, Feb 25 2012
%F 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
%F a(n) = (1/2 - 3/Pi^2)*n^2 + O(n*log(n)). - _Amiram Eldar_, Jul 26 2022
%t f[n_] := n(n + 1)/2 - Sum[ EulerPhi@i, {i, n}]; Array[f, 58] (* _Robert G. Wilson v_ *)
%t Accumulate[Table[n-EulerPhi[n],{n,1,60}]] (* _Harvey P. Dale_, Aug 19 2015 *)
%o (PARI) { a=0; for (n=1, 1000, write("b063985.txt", n, " ", a+=n - eulerphi(n)) ) } \\ _Harry J. Smith_, Sep 04 2009
%o (Haskell)
%o a063985 n = length [()| x <- [1..n], y <- [x..n], gcd x y > 1]
%o -- _Reinhard Zumkeller_, Jan 21 2013
%o (Python)
%o from sympy.ntheory import totient
%o def a(n): return sum(x - totient(x) for x in range(1,n + 1))
%o [a(n) for n in range(1, 51)] # _Indranil Ghosh_, Mar 18 2017
%o (Python)
%o from functools import lru_cache
%o @lru_cache(maxsize=None)
%o def A063985(n): # based on second formula in A018805
%o if n == 0:
%o return 0
%o c, j = 0, 2
%o k1 = n//j
%o while k1 > 1:
%o j2 = n//k1 + 1
%o c += (j2-j)*(k1*(k1+1)-2*A063985(k1)-1)
%o j, k1 = j2, n//j2
%o return (2*n+c-j)//2 # _Chai Wah Wu_, Mar 24 2021
%o (Java)
%o // Save the file as A063985.java to compile and run
%o import java.util.stream.IntStream;
%o import java.util.*;
%o public class A063985 {
%o public static int getInvisiblePoints(int n) {
%o Set<Float> slopes = new HashSet<Float>();
%o IntStream.rangeClosed(1, n).forEach(i ->
%o {IntStream.rangeClosed(1, n).forEach(j ->
%o slopes.add(Float.valueOf((float)i/(float)j))); });
%o return (n * n - slopes.size() + n - 1) / 2;
%o }
%o public static void main(String args[]) throws Exception {
%o IntStream.rangeClosed(1, 30).forEach(i ->
%o System.out.println(getInvisiblePoints(i)));
%o }
%o } // _Kiran Ananthpur Bacche_, May 25 2022
%Y Cf. A000010, A000217, A002088, A048290, A051953.
%K nonn
%O 1,3
%A _Labos Elemer_, Sep 06 2001
%E Corrected by _Robert G. Wilson v_, Dec 13 2006