A064018 -id:A064018 - cp's OEIS frontend

A342586 a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.

1, 63, 6087, 608383, 60794971, 6079301507, 607927104783, 60792712854483, 6079271032731815, 607927102346016827, 60792710185772432731, 6079271018566772422279, 607927101854119608051819, 60792710185405797839054887, 6079271018540289787820715707, 607927101854027018957417670303

Offset: 0

Karl-Heinz Hofmann, Mar 16 2021

nonn

Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54. (See link below.)

Joachim von zur Gathen and Jürgen Gerhard, Extract from "3.4. (Non-)Uniqueness of the gcd" chapter, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.
Hugo Pfoertner, Illustration of a(2)=6087.

a(n) = 2*A064018(n) - 1. - Hugo Pfoertner, Mar 16 2021
a(n) = A018805(10^n). - Michel Marcus, Mar 16 2021
Cf. A000010, A059956 (6/Pi^2), A342632, A342841, A343193, A343282.
Related counts of k-tuples:
pairs: A018805, A342632, A342586;
triples: A071778, A342935, A342841;
quadruples: A082540, A343527, A343193;
5-tuples: A343282;
6-tuples: A343978, A344038. - N. J. A. Sloane, Jun 13 2021

a342586(n)=my(s, m=10^n); forfactored(k=1,m,s+=eulerphi(k)); s*2-1 \\ Bruce Garner, Mar 29 2021

a342586(n)=my(s, m=10^n); forsquarefree(k=1,m,s+=moebius(k)*(m\k[1])^2); s \\ Bruce Garner, Mar 29 2021

import math
for n in range (0,10):
     counter = 0
     for x in range (1, pow(10,n)+1):
        for y in range(1, pow(10,n)+1):
            if math.gcd(y,x) ==  1:
                counter += 1
     print(n, counter)

from functools import lru_cache
@lru_cache(maxsize=None)
def A018805(n):
  if n == 1: return 1
  return n*n - sum(A018805(n//j) for j in range(2, n//2+1)) - (n+1)//2
print([A018805(10**n) for n in range(8)]) # Michael S. Branicky, Mar 18 2021

Lim_{n->infinity} a(n)/10^(2*n) = 6/Pi^2 = 1/zeta(2).

a(10) from Michael S. Branicky, Mar 18 2021
More terms using A064018 from Hugo Pfoertner, Mar 18 2021
Edited by N. J. A. Sloane, Jun 13 2021

A342632 Number of ordered pairs (x, y) with gcd(x, y) = 1 and 1 <= {x, y} <= 2^n.

Original entry on oeis.org

1, 3, 11, 43, 159, 647, 2519, 10043, 39895, 159703, 637927, 2551171, 10200039, 40803219, 163198675, 652774767, 2611029851, 10444211447, 41776529287, 167106121619, 668423198491, 2673693100831, 10694768891659, 42779072149475, 171116268699455, 684465093334979, 2737860308070095

Offset: 0

Karl-Heinz Hofmann, Mar 17 2021

nonn

			Only fractions with gcd(numerator, denominator) = 1 are counted. E.g.,
  1/2 counts, but 2/4, 3/6, 4/8 ... do not, because they reduce to 1/2;
  1/1 counts, but 2/2, 3/3, 4/4 ... do not, because they reduce to 1/1.
.
For n=0, the size of the grid is 1 X 1:
.
    | 1
  --+--
  1 | o      Sum:  1
.
For n=1, the size of the grid is 2 X 2:
.
    | 1 2
  --+----
  1 | o o          2
  2 | o .          1
                  --
             Sum:  3
.
For n=2, the size of the grid is 4 X 4:
.
    | 1 2 3 4
  --+--------
  1 | o o o o      4
  2 | o . o .      2
  3 | o o . o      3
  4 | o . o .      2
                  --
             Sum: 11
.
For n=3, the size of the grid is 8 X 8:
.
    | 1 2 3 4 5 6 7 8
  --+----------------
  1 | o o o o o o o o     8
  2 | o . o . o . o .     4
  3 | o o . o o . o o     6
  4 | o . o . o . o .     4
  5 | o o o o . o o o     7
  6 | o . . . o . o .     3
  7 | o o o o o o . o     7
  8 | o . o . o . o .     4
                         --
                    Sum: 43

Chai Wah Wu, Table of n, a(n) for n = 0..45
Joachim von zur Gathen and Jürgen Gerhard, Extract from "3.4. (Non-)Uniqueness of the gcd" chapter, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.

a(n) = A018805(2^n).

Cf. A000010, A002088, A059956 (6/Pi^2), A064018, A342586.

for(n=0,24,my(j=2^n);print1(2*sum(k=1,j,eulerphi(k))-1,", ")) \\ Hugo Pfoertner, Mar 17 2021

import math
for n in range (0, 21):
     counter = 0
     for x in range (1, pow(2, n)+1):
        for y in range(1, pow(2, n)+1):
            if math.gcd(y, x) ==  1:
                counter += 1
     print(n, counter)

from sympy import sieve
def A342632(n): return 2*sum(t for t in sieve.totientrange(1,2**n+1)) - 1 # Chai Wah Wu, Mar 23 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A018805(n):
  if n == 1: return 1
  return n*n - sum(A018805(n//j) for j in range(2, n//2+1)) - (n+1)//2
print([A018805(2**n) for n in range(25)]) # Michael S. Branicky, Mar 23 2021

Lim_{n->infinity} a(n)/2^(2*n) = 6/Pi^2 = 1/zeta(2).

Edited by N. J. A. Sloane, Jun 13 2021

A358936 Numbers k such that for some r we have phi(1) + ... + phi(k - 1) = phi(k + 1) + ... + phi(k + r), where phi(i) = A000010(i).

Original entry on oeis.org

3, 4, 6, 38, 40, 88, 244, 578, 581, 602, 1663, 2196, 10327, 17358, 28133, 36163, 42299, 123556, 149788, 234900, 350210, 366321, 620478, 694950, 869880, 905807, 934286, 1907010, 2005592, 5026297, 7675637, 11492764, 12844691, 14400214, 15444216, 18798939, 20300872

Offset: 1

Ctibor O. Zizka, Dec 07 2022

nonn

These numbers might be called "Euler totient function sequence balancing numbers", after the Behera and Panda link.

Numbers k such that A002088(k-1) + A002088(k) is a term of A002088.

			k = 3:
phi(1) + phi(2) = phi(4) = 2.
Thus the balancing number k = 3 is a term. The balancer r is 1.
k = 4:
phi(1) + phi(2) + phi(3) = phi(5) = 4.
Thus the balancing number k = 4 is a term. The balancer r is 1.
phi(i) = A000010(i).

Ctibor O. Zizka, Table of k < 10^9, Terms 38..45 from David A. Corneth.
A. Behera and G. K. Panda, On the square roots of triangular numbers, The Fibonacci Quarterly, 37.2 (1999), 98-105.

Cf. A000010, A001109, A002088, A064018.

With[{m = 30000},phi = EulerPhi[Range[m]]; s = Accumulate[phi]; Select[Range[2, m], MemberQ[s, 2*s[[#]] - phi[[#]]] &]] (* Amiram Eldar, Dec 07 2022 *)

upto(n) = {my(res = List(), lefttotal = 1, righttotal = 2, k = 2, nplusr = 3, sumf = 1, oldfk = 1); for(i = 1, n,  while(lefttotal > righttotal, nplusr++; righttotal+=f(nplusr) ); if(lefttotal == righttotal, listput(res, k)); lefttotal+=oldfk; k++; fk = f(k); righttotal-=fk; oldfk = fk ); res }
f(k) = eulerphi(k) \\ David A. Corneth, Dec 07 2022

from sympy import totient as phi
from itertools import count, islice
def f(n): # function we wish to "balance"
    return phi(n)
def agen(): # generator of terms
    s, sset, i = [0, f(1), f(1)+f(2)], set(), 3
    for k in count(2):
        target = s[k-1] + s[k]
        while s[-1] < target:
            fi = f(i); nexts = s[-1] + fi; i += 1
            s.append(nexts); sset.add(nexts)
        if target in sset: yield k
print(list(islice(agen(), 17))) # Michael S. Branicky, Dec 07 2022

a(8)-a(15) from Amiram Eldar, Dec 07 2022

a(16)-a(37) from Michael S. Branicky, Dec 07 2022

A064016 a(n) = Sum_{k <= 10^n} cototient(k), where cototient is A051953.

Original entry on oeis.org

0, 23, 2006, 196308, 19607514, 1960399246, 196036947608, 19603648572758, 1960364533634092, 196036449326991586, 19603644912113783634, 1960364490766613788860, 196036449073440195974090, 19603644907302101080472556, 1960364490729905106089642146, 196036449072986990521291164848

Offset: 0

Robert G. Wilson v, Sep 07 2001

nonn

It appears that lim_{n->infinity} (1/n^2) * Sum_{j=1..n} a(j) = 0.1960364... = (1/2 - 3/Pi^2).

Cf. A002088, A051953, A063985, A064018.

s = 0; k = 1; Do[ While[ k <= 10^n, s = s + k - EulerPhi[ k ]; k++ ]; Print[ s ], {n, 0, 8} ]

a(n) = 10^n*(10^n+1)/2 - A002088(10^n) = 10^n*(10^n+1)/2 - A064018(n). - Chai Wah Wu, Apr 18 2021

a(n) = A063985(10^n). - Michel Marcus, Apr 18 2021

a(9) from Jud McCranie, Jun 25 2005
a(10)-a(11) from Donovan Johnson, Feb 06 2010
a(12) from Donovan Johnson, Feb 07 2012
a(13)-a(15) using A064018 from Chai Wah Wu, Apr 18 2021

A189020 a(n) = Sum_{k=1..10^n} tau_4(k), where tau_4 is the number of ordered factorizations into 4 factors (A007426).

Original entry on oeis.org

1, 89, 3575, 93237, 1951526, 35270969, 578262093, 8840109380, 128217432396, 1784942188189, 24045237260214, 315312623543840, 4042957241191810, 50862246063060180, 629513636928477232, 7681900592647818929, 92587253467765253144, 1103781870246459696784, 13031388731053572679450, 152516435040764735691556, 1771079109308495896176156

Offset: 0

Andrew Lelechenko, Apr 15 2011

nonn

Using that tau_4 = tau_2 ** tau_2, where ** means Dirichlet convolution and tau_2 is (A000005), one can calculate a(n) faster than in O(10^n) operations - namely in O(10^(3n/4)) or even in O(10^(2n/3)). See links for details.

A. V. Lelechenko, The summation of the multiplicative functions (in Russian).

Cf. A057494 - partial sums up to 10^n of the divisors function tau_2 (A000005), A180361 - of the unitary divisors function tau_2* (A034444), A180365 - of the 3-divisors function tau_3 (A007425).

Also see A072692 for such sums of the sum of divisors function (A000203), A084237 for sums of Moebius function (A008683), A064018 for sums of Euler totient function (A000010).

a(n) = A061202(10^n) = Sum_{k=1..10^n} A007426(n).

a(16)-a(20) from Henri Lifchitz, Feb 05 2025

cp's OEIS Frontend

A342586 a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

PARI

Python

Python

Formula

Extensions

A342632 Number of ordered pairs (x, y) with gcd(x, y) = 1 and 1 <= {x, y} <= 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Python

Python

Python

Formula

Extensions

A358936 Numbers k such that for some r we have phi(1) + ... + phi(k - 1) = phi(k + 1) + ... + phi(k + r), where phi(i) = A000010(i).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Extensions

A064016 a(n) = Sum_{k <= 10^n} cototient(k), where cototient is A051953.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A189020 a(n) = Sum_{k=1..10^n} tau_4(k), where tau_4 is the number of ordered factorizations into 4 factors (A007426).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions