A091369 -id:A091369 - cp's OEIS frontend

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

Labos Elemer, Sep 06 2001

nonn

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

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)

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

a063985 n = length [()| x <- [1..n], y <- [x..n], gcd x y > 1]
-- Reinhard Zumkeller, Jan 21 2013

// 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

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 *)

{ a=0; for (n=1, 1000, write("b063985.txt", n, " ", a+=n - eulerphi(n)) ) } \\ Harry J. Smith, Sep 04 2009

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

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

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

Corrected by Robert G. Wilson v, Dec 13 2006

A015613 a(n) = Sum_{i=1..n} phi(i) * (ceiling(n/i) - floor(n/i)).

Original entry on oeis.org

0, 0, 1, 2, 5, 6, 11, 14, 19, 22, 31, 34, 45, 50, 57, 64, 79, 84, 101, 108, 119, 128, 149, 156, 175, 186, 203, 214, 241, 248, 277, 292, 311, 326, 349, 360, 395, 412, 435, 450, 489, 500, 541, 560, 583, 604, 649, 664, 705, 724, 755, 778, 829, 846, 885, 908, 943

Offset: 1

Joseph L. Pe, Oct 24 2002

nonn

a(n) is half the number of fractions reduced to lowest terms with numerator and denominator in {2, 3, ..., n}. a(5) = 5 = (1/2) * |{2/3, 2/5, 3/2, 3/4, 3/5, 4/3, 4/5, 5/2, 5/3, 5/4}|. - Stefano Spezia, Aug 11 2019

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A000005, A000010, A000217, A002088, A049820, A091369.

a:= proc(n) option remember; `if`(n=0, 0,
       numtheory[phi](n)-1+a(n-1))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 11 2019

f[n_] := Module[{s, i}, s = 0; For[i = 1, i < n, i++, If[Mod[n, i] != 0, s = s + EulerPhi[i]]]; s]; Table[f[i], {i, 1, 100}]
Table[Sum[EulerPhi[i](Ceiling[n/i]-Floor[n/i]),{i,n}],{n,60}] (* Harvey P. Dale, Feb 06 2025 *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A015613(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)*(2*(A015613(k1)+k1)-1)
        j, k1 = j2, n//j2
    return (n*(n-3)-c+j)//2 # Chai Wah Wu, Mar 25 2021

a(n) = sum of phi(e) where e ranges over all nondivisors of n that are between 1 and n. - Joseph L. Pe, Oct 24 2002
a(n) = A002088(n) - n.
a(n) = A091369(n) - A000217(n). - Alois P. Heinz, Aug 11 2019

Edited by Vladeta Jovovic, Mar 23 2003

cp's OEIS Frontend

A063985 Partial sums of cototient sequence A051953.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Java

Mathematica

PARI

Python

Python

Formula

Extensions

A015613 a(n) = Sum_{i=1..n} phi(i) * (ceiling(n/i) - floor(n/i)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions