cp's OEIS Frontend

A063985 Partial sums of cototient sequence A051953.

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