A002088 -id:A002088 - cp's OEIS frontend

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

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

A372619 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals downwards, where T(n,k) = 1/(phi(k)) * Sum_{j=1..n} phi(k*j).

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 2, 5, 6, 1, 3, 5, 9, 10, 1, 2, 5, 7, 13, 12, 1, 3, 4, 9, 11, 17, 18, 1, 2, 6, 6, 13, 14, 23, 22, 1, 3, 4, 10, 11, 17, 20, 31, 28, 1, 2, 5, 6, 14, 13, 23, 24, 37, 32, 1, 3, 5, 9, 10, 20, 19, 31, 33, 45, 42, 1, 2, 5, 7, 13, 12, 26, 23, 37, 37, 55, 46

Offset: 1

Seiichi Manyama, May 07 2024

			Square array T(n,k) begins:
   1,  1,  1,  1,  1,  1,  1,  1,  1,  1, ...
   2,  3,  2,  3,  2,  3,  2,  3,  2,  3, ...
   4,  5,  5,  5,  4,  6,  4,  5,  5,  5, ...
   6,  9,  7,  9,  6, 10,  6,  9,  7,  9, ...
  10, 13, 11, 13, 11, 14, 10, 13, 11, 14, ...
  12, 17, 14, 17, 13, 20, 12, 17, 14, 18, ...
  18, 23, 20, 23, 19, 26, 19, 23, 20, 24, ...

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Columns k=1..10 give: A002088, A049690, A372621, A049690, A372622, A372637, A372638, A049690, A372621, A372639.
Main diagonal gives A070639.
Cf. A000010, A372606.
Cf. A078615, A322360.

T[n_, k_] := Sum[EulerPhi[k*j], {j, 1, n}] / EulerPhi[k]; Table[T[k, n-k+1], {n, 1, 12}, {k, 1, n}] // Flatten (* Amiram Eldar, May 09 2024 *)

T(n, k) = sum(j=1, n, eulerphi(k*j))/eulerphi(k);

T(n,k) ~ (3/Pi^2) * c(k) * n^2, where c(k) = A078615(k)/A322360(k) is the multiplicative function defined by c(p^e) = p^2/(p^2-1). - Amiram Eldar, May 09 2024

A171503 Number of 2 X 2 integer matrices with entries from {0,1,...,n} having determinant 1.

Original entry on oeis.org

0, 3, 7, 15, 23, 39, 47, 71, 87, 111, 127, 167, 183, 231, 255, 287, 319, 383, 407, 479, 511, 559, 599, 687, 719, 799, 847, 919, 967, 1079, 1111, 1231, 1295, 1375, 1439, 1535, 1583, 1727, 1799, 1895, 1959, 2119, 2167, 2335, 2415, 2511, 2599

Offset: 0

Jacob A. Siehler, Dec 10 2009

nonn

Number of distinct solutions to k*x+h=0, where |h|<=n and k=1,2,...,n. - Giovanni Resta, Jan 08 2013.

Number of reduced rational numbers r/s with |r|<=n and 0Juan M. Marquez, Apr 13 2015

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Cf. A062801, A000010, A018805. Differences are A002246.

See A326354 for an essentially identical sequence.

with(numtheory):
a:= proc(n) option remember;
       `if`(n<2, [0, 3][n+1], a(n-1) + 4*phi(n))
    end:
seq(a(n), n=0..60);

a[n_]:=Count[Det/@(Partition[ #,2]&/@Tuples[Range[0,n],4]),1]
(* Second program: *)
a[0] = 0; a[1] = 3; a[n_] := a[n] = a[n-1] + 4*EulerPhi[n];
Table[a[n], {n, 0, 60}] (* Jean-François Alcover, Jun 16 2018 *)

a(n)=(n>0)+2*sum(k=1, n, moebius(k)*(n\k)^2) \\ Charles R Greathouse IV, Apr 20 2015

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

Recursion: a(n) = a(n - 1) + 4*phi(n) for n > 1, with phi being Euler's totient function. - Juan M. Marquez, Jan 19 2010

a(n) = 4 * A002088(n) - 1 for n >= 1. - Robert Israel, Jun 01 2014

Edited by Alois P. Heinz, Jan 19 2011

A319087 a(n) = Sum_{k=1..n} k^2*phi(k), where phi is the Euler totient function A000010.

Original entry on oeis.org

1, 5, 23, 55, 155, 227, 521, 777, 1263, 1663, 2873, 3449, 5477, 6653, 8453, 10501, 15125, 17069, 23567, 26767, 32059, 36899, 48537, 53145, 65645, 73757, 86879, 96287, 119835, 127035, 155865, 172249, 194029, 212525, 241925, 257477, 306761, 332753, 369257

Offset: 1

Vaclav Kotesovec, Sep 10 2018

nonn

Comment from N. J. A. Sloane, Mar 22 2020: (Start)
Theorem: Sum_{ 1<=i<=n, 1<=j<=n, gcd(i,j)=1 } i*j = a(n).
Proof: From the Apostol reference we know that:
Sum_{ 1<=i<=n, gcd(i,n)=1 } i = n*phi(n)/2 (see A023896).
We use induction on n. The result is true for n=1.
Then a(n) - a(n-1) = 2*Sum_{ i=1..n-1, gcd(i,n)=1 } n*i = n^2*phi(n). QED (End)

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 48, problem 16, the function phi_1(n).

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Cf. A000010, A002088, A011755, A023896, A053191.

Accumulate[Table[k^2*EulerPhi[k], {k, 1, 50}]]

a(n) = sum(k=1, n, k^2*eulerphi(k)); \\ Michel Marcus, Sep 12 2018

a(n) ~ 3*n^4 / (2*Pi^2).

A015634 Number of ordered quadruples of integers from [ 1..n ] with no global factor.

Original entry on oeis.org

1, 4, 13, 29, 63, 106, 189, 289, 444, 626, 911, 1203, 1657, 2130, 2766, 3462, 4430, 5359, 6688, 7992, 9670, 11405, 13704, 15840, 18730, 21548, 25037, 28521, 33015, 37067, 42522, 47690, 53940, 60108, 67760, 74748, 83886, 92433, 102629, 112469, 124809, 135763, 149952

Offset: 1

Olivier Gérard

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Column k=4 of A177976.
Partial sums of A117108.
Cf. A000332, A002088, A013662, A015631, A015650.

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*Binomial[# + 2, 3] &], {k, 1, n}]; Array[a, 45] (* Amiram Eldar, Jun 07 2025 *)

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+2, 3))); \\ Seiichi Manyama, Jun 12 2021

a(n) = binomial(n+3, 4)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^4)/(1-x)) \\ Seiichi Manyama, Jun 12 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A015634(n):
    if n == 0:
        return 0
    c, j = 1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A015634(k1)
        j, k1 = j2, n//j2
    return n*(n+1)*(n+2)*(n+3)//24-c+j-n # Chai Wah Wu, Apr 18 2021

G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^4. - Ilya Gutkovskiy, Feb 14 2020
a(n) = n*(n+1)*(n+2)*(n+3)/24 - Sum_{j=2..n} a(floor(n/j)) = A000332(n+3) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Apr 18 2021
a(n) ~ n^4 / (24*zeta(4)). - Amiram Eldar, Jun 08 2025

A099957 a(n) = Sum_{k=0..n-1} phi(2k+1).

Original entry on oeis.org

1, 3, 7, 13, 19, 29, 41, 49, 65, 83, 95, 117, 137, 155, 183, 213, 233, 257, 293, 317, 357, 399, 423, 469, 511, 543, 595, 635, 671, 729, 789, 825, 873, 939, 983, 1053, 1125, 1165, 1225, 1303, 1357, 1439, 1503, 1559, 1647, 1719, 1779, 1851, 1947

Offset: 1

Hugo Pfoertner, Nov 13 2004

nonn

The n-th term is the number of notes of the (2n-1)-limit tonality diamond. This is a term from music theory and means the scale consisting of the rational numbers r, 1 <= r < 2, such that the odd part of both the numerator and the denominator of r, when reduced to lowest terms, is less than or equal to the fixed odd number 2n-1. - Gene Ward Smith, Mar 27 2006
(1/4)*Number of distinct angular positions under which an observer positioned at the center of a square of a square lattice can see the (2n) X (2n) points symmetrically surrounding his position.
(1/8)*number of distinct angular positions under which an observer positioned at a lattice point of a square lattice can see the (2n+1)X(2n+1) points symmetrically surrounding his position gives A002088.
(1/2)*number of distinct angular positions under which an observer positioned at the center of an edge of a square lattice can see the (2n)X(2n-1) points symmetrically surrounding his position gives A099958.

Seiichi Manyama, Table of n, a(n) for n = 1..10000
Lv Chuan, On the Mean Value of an Arithmetical Function, in Zhang Wenpeng (ed.), Research on Smarandache Problems in Number Theory (collected papers), 2004, pp. 89-92.
Wikipedia, Tonality diamond.

Bisection of A274401.
Partial sums of A037225.
Cf. A000010, A002088, A099958, A049687, A049690.

Accumulate[EulerPhi[2*Range[0,50]+1]] (* Harvey P. Dale, Aug 20 2021 *)

apply( {A099957(n)=sum(k=1,n, eulerphi(2*k-1))}, [1..55]) \\ M. F. Hasler, Apr 03 2023

a(n+1) - a(n) = phi(2n+1) (A037225).
a(n) = (8/Pi^2)*n^2 + O(n^(3/2+eps)) (Lemma 1 in Lv Chuan, 2004). - Amiram Eldar, Aug 02 2022, corrected by M. F. Hasler, Mar 26 2023
a(n) = A002088(2*n-1) - A049690(n-1). - Chai Wah Wu, Aug 04 2024

A177976 Square array T(n,k) read by antidiagonals up. Cumulative column sums of A177975.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 8, 4, 1, 1, 10, 15, 13, 5, 1, 1, 12, 29, 29, 19, 6, 1, 1, 18, 42, 63, 49, 26, 7, 1, 1, 22, 69, 106, 118, 76, 34, 8, 1, 1, 28, 95, 189, 225, 201, 111, 43, 9, 1, 1, 32, 134, 289, 434, 427, 320, 155, 53, 10, 1, 1, 42, 172, 444, 729, 888, 748, 484, 209, 64, 11, 1

Offset: 1

Mats Granvik, May 16 2010

Each row is described by both a binomial expression and a closed form polynomial. The closed form polynomials given in A177977 extends this table to the left. For example the 0th column is A002321 and the -1st column is A092149.

Also number of ordered k-tuples of integers from [ 1..n ] with no global factor. - Seiichi Manyama, Jun 12 2021

			Table begins:
  1..1...1....1.....1.....1......1......1.......1.......1.......1
  1..2...3....4.....5.....6......7......8.......9......10......11
  1..4...8...13....19....26.....34.....43......53......64......76
  1..6..15...29....49....76....111....155.....209.....274.....351
  1.10..29...63...118...201....320....484.....703.....988....1351
  1.12..42..106...225...427....748...1233....1937....2926....4278
  1.18..69..189...434...888...1671...2948....4939....7930...12285
  1.22..95..289...729..1624...3303...6260...11209...19150...31447
  1.28.134..444..1209..2890...6278..12659...24034...43405...75139
  1.32.172..626..1850..4761..11067..23762...47841...91301..166506
  1.42.237..911..2850..7763..19074..43209...91598..183678..351261
  1.46.287.1203..4059.11829..30911..74129..165737..349426..700699
  1.58.377.1657..5878.18016..49474.124516..291706..643355.1347344
  1.64.452.2130..8044.26117..75676.200313..492185.1135761.2483392
  1.72.552.2766.11020.37599.114199.316228..811416.1952182.4443582
  1.80.652.3462.14566.52311.166747.483340.1295295.3248246.7692894

Seiichi Manyama, Antidiagonals n = 1..140, flattened

Column k=1..5 gives A000012, A002088, A015631, A015634, A015650.

Cf. A177975, A177977, A344527, A345229.

T(n, k) = sum(j=1, n, sumdiv(j, d, moebius(j/d)*binomial(d+k-2, d-1))); \\ Seiichi Manyama, Jun 12 2021

T(n, k) = binomial(n+k-1, k)-sum(j=2, n, T(n\j, k)); \\ Seiichi Manyama, Jun 12 2021

From Seiichi Manyama, Jun 12 2021: (Start)
G.f. of column k: (1/(1 - x)) * Sum_{j>=1} mu(j) * x^j/(1 - x^j)^k.
T(n,k) = Sum_{j=1..n} Sum_{d|j} mu(j/d) * binomial(d+k-2,d-1).
T(n,k) = binomial(n+k-1,k) - Sum_{j=2..n} T(floor(n/j),k).  (End)

A306988 a(n) = Sum_{k=1..n} binomial(n,k)*phi(k), where phi is the Euler totient function.

Original entry on oeis.org

1, 3, 8, 20, 49, 117, 272, 620, 1395, 3107, 6852, 14964, 32395, 69647, 149002, 317712, 675749, 1433769, 3033444, 6396320, 13437913, 28130869, 58708304, 122239396, 254141275, 527946013, 1096312050, 2275897660, 4722500707, 9791471587, 20277706762, 41932520528

Offset: 1

Vaclav Kotesovec, Mar 18 2019

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 1..3280
Vaclav Kotesovec, Plot of a(n)/(n*2^n) for n = 1..5000
Eric Weisstein's World of Mathematics, Totient Function.
Wikipedia, Euler's totient function.

Cf. A000010, A002088, A101509, A160399, A185003.

Partial sums of A131045.

Table[Sum[Binomial[n, k]*EulerPhi[k], {k, 1, n}], {n, 1, 40}]

a(n) ~ 3 * n * 2^n / Pi^2.

A015650 Number of ordered 5-tuples of integers from [ 1..n ] with no global factor.

Original entry on oeis.org

1, 5, 19, 49, 118, 225, 434, 729, 1209, 1850, 2850, 4059, 5878, 8044, 11020, 14566, 19410, 24789, 32103, 40213, 50615, 62260, 77209, 93099, 113504, 135431, 162341, 191396, 227355, 264463, 310838, 359322, 417212, 478408, 551944, 626971, 718360, 812311, 922407, 1036667

Offset: 1

Olivier Gérard

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Column k=5 of A177976.
Partial sums of A117109.
Cf. A000389, A002088, A013663, A015631, A015634.

a[n_] := Sum[DivisorSum[k, MoebiusMu[k/#]*Binomial[# + 3, 4] &], {k, 1, n}]; Array[a, 40] (* Amiram Eldar, Jun 07 2025 *)

a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+3, 4))); \\ Seiichi Manyama, Jun 12 2021

a(n) = binomial(n+4, 5)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021

my(N=40, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^5)/(1-x)) \\ Seiichi Manyama, Jun 12 2021

from functools import lru_cache
@lru_cache(maxsize=None)
def A015650(n):
    if n == 0:
        return 0
    c, j = n+1, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*A015650(k1)
        j, k1 = j2, n//j2
    return n*(n+1)*(n+2)*(n+3)*(n+4)//120-c+j # Chai Wah Wu, Apr 18 2021

G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^5. - Ilya Gutkovskiy, Feb 14 2020
a(n) = n*(n+1)*(n+2)*(n+3)*(n+4)/120 - Sum_{j=2..n} a(floor(n/j)) = A000389(n+4) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Apr 18 2021
a(n) ~ n^5 / (120*zeta(5)). - Amiram Eldar, Jun 08 2025

A063986 Numbers k that divide Sum_{j=1..k} A051953(j) where A051953(j) = j - Phi(j). Arithmetic mean of first k cototient values is an integer.

Original entry on oeis.org

1, 4, 5, 24, 25, 249, 600, 617, 12272, 13763, 21332, 25228, 783665, 15748051, 41846733, 195853251, 2488541984, 14399065016, 21119309213, 22430204140, 43787603128, 157825075944, 206651865067, 271605149320, 374049315076, 650288309748

Offset: 1

Labos Elemer, Sep 06 2001

nonn

The odd terms of A048290 and A063986 are the same. - Jud McCranie, Jun 26 2005

a(27) > 10^12. - Donovan Johnson, Dec 09 2011

			k=5: (1 + 1 + 2 + 2 + 4)/5 = 2.

Cf. A051953, A000010, A002088, A048920, A000217, A050226.

s = 0; Do[s = s + n - EulerPhi[n]; If[ IntegerQ[s/n], Print[n]], {n, 1, 10^7} ]

More terms from Dean Hickerson, Sep 07 2001
One more term from Robert G. Wilson v, Sep 07 2001
a(16) and a(17) from Jud McCranie, Jun 22 2005
a(18)-a(21) from Donovan Johnson, May 11 2010
a(22)-a(26) from Donovan Johnson, Dec 09 2011

cp's OEIS Frontend

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

A372619 Square array T(n,k), n >= 1, k >= 1, read by antidiagonals downwards, where T(n,k) = 1/(phi(k)) * Sum_{j=1..n} phi(k*j).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A171503 Number of 2 X 2 integer matrices with entries from {0,1,...,n} having determinant 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A319087 a(n) = Sum_{k=1..n} k^2*phi(k), where phi is the Euler totient function A000010.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A015634 Number of ordered quadruples of integers from [ 1..n ] with no global factor.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Python

Formula

A099957 a(n) = Sum_{k=0..n-1} phi(2k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A177976 Square array T(n,k) read by antidiagonals up. Cumulative column sums of A177975.

Views

Author

Keywords