A102309 -id:A102309 - cp's OEIS frontend

A100448 Number of triples (i,j,k) with 1 <= i <= j < k <= n and gcd{i,j,k} = 1.

0, 1, 4, 9, 19, 30, 51, 73, 106, 140, 195, 241, 319, 388, 480, 572, 708, 813, 984, 1124, 1310, 1485, 1738, 1926, 2216, 2462, 2777, 3059, 3465, 3749, 4214, 4590, 5060, 5484, 6048, 6474, 7140, 7671, 8331, 8899, 9719, 10289, 11192, 11902, 12754, 13535, 14616

Offset: 1

N. J. A. Sloane, Nov 21 2004

Probably the partial sums of A102309. - Ralf Stephan, Jan 03 2005

R. J. Mathar, Table of n, a(n) for n = 1..10000

Cf. A015616, A015631, A027430, A071778, A018805.

f:=proc(n) local i,j,k,t1,t2,t3; t1:=0; for i from 1 to n do for j from i to n do t2:=gcd(i,j); for k from j+1 to n do t3:=gcd(t2,k); if t3 = 1 then t1:=t1+1; fi; od: od: od: t1; end;

f[n_] := Length[ Union[ Flatten[ Table[ If[ GCD[i, j, k] == 1, {i, j, k}], {i, n}, {j, i, n}, {k, j + 1, n}], 2]]]; Table[ If[n > 3, f[n] - 1, f[n]], {n, 47}] (* Robert G. Wilson v, Dec 14 2004 *)

from functools import lru_cache
@lru_cache(maxsize=None)
def A100448(n):
    if n == 0:
        return 0
    c, j = 2, 2
    k1 = n//j
    while k1 > 1:
        j2 = n//k1 + 1
        c += (j2-j)*(6*A100448(k1)+1)
        j, k1 = j2, n//j2
    return (n*(n**2-1)-c+j)//6 # Chai Wah Wu, Mar 29 2021

a(n) = (A071778(n)-1)/6. - Vladeta Jovovic, Nov 30 2004

a(n) = (1/6)*(-1 + Sum_{k=1..n} moebius(k)*floor(n/k)^3). - Ralf Stephan, Jan 03 2005

More terms from Robert G. Wilson v, Dec 14 2004

Edited by N. J. A. Sloane, Sep 06 2008 at the suggestion of R. J. Mathar

A123706 Matrix inverse of triangle A010766, where A010766(n,k) = [n/k], for n>=k>=1.

Original entry on oeis.org

1, -2, 1, -1, -1, 1, 1, -1, -1, 1, -1, 0, 0, -1, 1, 2, 0, -1, 0, -1, 1, -1, 0, 0, 0, 0, -1, 1, 0, 0, 1, -1, 0, 0, -1, 1, 0, 1, -1, 0, 0, 0, 0, -1, 1, 2, -1, 0, 1, -1, 0, 0, 0, -1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, -1, 1, 1, -1, 1, -1, 0, 0, 0, 0, -1, 1, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 1, 2, -1, 0, 0, 0, 1, -1, 0, 0, 0, 0, 0, -1, 1, 1, 1, -1, 1, -1, 0, 0, 0

Offset: 1

Paul D. Hanna, Oct 09 2006

Unsigned elements consist of only 0's, 1's and 2's.

			Triangle begins:
1;
-2, 1;
-1,-1, 1;
1,-1,-1, 1;
-1, 0, 0,-1, 1;
2, 0,-1, 0,-1, 1;
-1, 0, 0, 0, 0,-1, 1;
0, 0, 1,-1, 0, 0,-1, 1;
0, 1,-1, 0, 0, 0, 0,-1, 1;
2,-1, 0, 1,-1, 0, 0, 0,-1, 1;
-1, 0, 0, 0, 0, 0, 0, 0, 0,-1, 1;
-1, 1, 1,-1, 1,-1, 0, 0, 0, 0,-1, 1;
-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,-1, 1;
2,-1, 0, 0, 0, 1,-1, 0, 0, 0, 0, 0,-1, 1;
1, 1,-1, 1,-1, 0, 0, 0, 0, 0, 0, 0, 0,-1, 1; ...

Enrique Pérez Herrero, Rows n = 1..100 of triangle, flattened

Cf. A102309, A085411; A123707, A123708, A123709.

t[n_, k_] := If[Divisible[n, k], MoebiusMu[n/k], 0] - If[Divisible[n, k+1], MoebiusMu[n/(k+1)], 0]; Table[t[n, k], {n, 1, 15}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 29 2013, after Enrique Pérez Herrero *)

T(n,k)=(matrix(n,n,r,c,r\c)^-1)[n,k]  \\ simplified by M. F. Hasler, Feb 12 2012

T(n,1) = +2 when n = 2*p where p is an odd prime.
T(n,1) = -2 when n is an even squarefree number with an odd number of prime divisors.
A123709(n) = number of nonzero terms in row n = 2^(m+1) - 1 when n is an odd number with exactly m distinct prime factors.
Sum_{k=1..n} T(n,k) = moebius(n).
Sum_{k=1..n} T(n,k)*k = 0 for n>1.
Sum_{k=1..n} T(n,k)*k^2 = 2*phi(n) for n>1 where phi(n)=A000010(n).
Sum_{k=1..n} T(n,k)*k^3 = 6*A102309(n) for n>1 where A102309(n)=Sum[d|n, moebius(d)*C(n/d,2) ].
Sum_{k=1..n} T(n,k)*k*2^(k-1) = A085411(n) = Sum_{d|n} mu(n/d)*(d+1)*2^(d-2) = total number of parts in all compositions of n into relatively prime parts.
T(n,k) = mu(n/k)-mu(n/(k+1)), where mu(n/k) is A008683(n/k) if k|n and 0 otherwise. - Enrique Pérez Herrero, Feb 21 2012

A020921 Triangle read by rows: T(m,n) = number of solutions to 1 <= a(1) < a(2) < ... < a(m) <= n, where gcd( a(1), a(2), ..., a(m), n) = 1.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 0, 2, 3, 1, 0, 2, 5, 4, 1, 0, 4, 10, 10, 5, 1, 0, 2, 11, 19, 15, 6, 1, 0, 6, 21, 35, 35, 21, 7, 1, 0, 4, 22, 52, 69, 56, 28, 8, 1, 0, 6, 33, 83, 126, 126, 84, 36, 9, 1, 0, 4, 34, 110, 205, 251, 210, 120, 45, 10, 1, 0, 10, 55, 165, 330, 462, 462, 330, 165, 55, 11

Offset: 0

Michael Somos, Nov 17 2002

			From _R. J. Mathar_, Feb 12 2007: (Start)
Triangle begins
  1
  1 1
  0 1  1
  0 2  3   1
  0 2  5   4   1
  0 4 10  10   5   1
  0 2 11  19  15   6   1
  0 6 21  35  35  21   7   1
  0 4 22  52  69  56  28   8  1
  0 6 33  83 126 126  84  36  9  1
  0 4 34 110 205 251 210 120 45 10 1
The inverse of the triangle is
   1
  -1    1
   1   -1    1
  -1    1   -3    1
   1   -1    7   -4    1
  -1    1  -15   10   -5    1
   1   -1   31  -19   15   -6    1
  -1    1  -63   28  -35   21   -7    1
   1   -1  127  -28   71  -56   28   -8    1
  -1    1 -255    1 -135  126  -84   36   -9    1
   1   -1  511   80  255 -251  210 -120   45  -10    1
with row sums 1,0,1,-2,4,-9,22,-55,135,-319,721,...(cf. A038200).
(End)

Temba Shonhiwa, A Generalization of the Euler and Jordan Totient Functions, Fib. Quart., 37 (1999), 67-76.

(Left-hand) columns include A000010, A102309. Row sums are essentially A027375.

Cf. A327029.

A020921 := proc(n,k) option remember ; local divs ; if n <= 0 then 1 ; elif k > n then 0 ; else divs := numtheory[divisors](n) ; add(numtheory[mobius](op(i,divs))*binomial(n/op(i,divs),k),i=1..nops(divs)) ; fi ; end: nmax := 10 ; for row from 0 to nmax do for col from 0 to row do printf("%d,",A020921(row,col)) ; od ; od ; # R. J. Mathar, Feb 12 2007

nmax = 11; t[n_, k_] := Total[ MoebiusMu[#]*Binomial[n/#, k] & /@ Divisors[n]]; t[0, 0] = 1; Flatten[ Table[t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Oct 20 2011, after PARI *)

{T(n, k) = if( n<=0, k==0 && n==0, sumdiv(n, d, moebius(d) * binomial(n/d, k)))}

# uses[DivisorTriangle from A327029]
DivisorTriangle(moebius, binomial, 13) # Peter Luschny, Aug 24 2019

A326419 a(n) is the number of distinct Horadam sequences of period n.

Original entry on oeis.org

1, 1, 3, 5, 10, 11, 21, 22, 33, 34, 55, 46, 78, 69, 92, 92, 136, 105, 171, 140, 186, 175, 253, 188, 290, 246, 315, 282, 406, 284, 465, 376, 470, 424, 564, 426, 666, 531, 660, 568, 820, 570, 903, 710, 852, 781, 1081, 760, 1155, 890, 1136, 996, 1378, 963, 1420, 1140

Offset: 1

Michel Marcus, Sep 30 2019

nonn

Robert Israel, Table of n, a(n) for n = 1..10000
Ovidiu D. Bagdasar and Peter J. Larcombe, On the Number of Complex Horadam Sequences with a Fixed Period, Fib. Q. 51(4), 2013, 339-347.

Cf. A102309.

N:= 200: # for a(1)..a(N)
V:= Vector(N,n -> numtheory:-phi(n)*(numtheory:-phi(n)-1)/2):
for k1 from 1 to N do
  p1:= numtheory:-phi(k1);
  for k2 from k1+1 to N do
     n:= ilcm(k1,k2);
     if n <= N then V[n]:= V[n] + p1*numtheory:-phi(k2) fi;
  od:
od:
V[1]:= 1:
convert(V,list); # Robert Israel, Dec 06 2020

a(n) = if (n==1, 1, eulerphi(n)*(eulerphi(n)-1)/2 + sum(k2=1, n, sum(k1=1, k2-1, if (lcm(k1, k2)==n, eulerphi(k1)*eulerphi(k2)))));

from math import comb
from sympy import mobius, divisors
def A326419(n): return sum(mobius(d)*comb(n//d,2) for d in divisors(n,generator=True)) if n>1 else 1 # Chai Wah Wu, May 09 2025

a(n) = Sum_{k1= 2. See link.

A344596 a(n) = Sum_{k=1..n} mu(k) * (floor(n/k)^3 - floor((n-1)/k)^3).

Original entry on oeis.org

1, 6, 18, 30, 60, 66, 126, 132, 198, 204, 330, 276, 468, 414, 552, 552, 816, 630, 1026, 840, 1116, 1050, 1518, 1128, 1740, 1476, 1890, 1692, 2436, 1704, 2790, 2256, 2820, 2544, 3384, 2556, 3996, 3186, 3960, 3408, 4920, 3420, 5418, 4260, 5112, 4686, 6486, 4560, 6930, 5340, 6816

Offset: 1

Seiichi Manyama, May 24 2021

nonn

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

Essentially 6*A102309 and 6*A326419.

Cf. A000578, A071778, A140434, A344597.

a[n_] := Sum[MoebiusMu[k] * First @ Differences @ (Quotient[{n - 1, n}, k]^3), {k, 1, n}]; Array[a, 50] (* Amiram Eldar, May 24 2021 *)

a(n) = sum(k=1, n, moebius(k)*((n\k)^3-((n-1)\k)^3));

a(n) = if(n<2, n, 3*sumdiv(n, d, moebius(n/d)*(d-1)*d));

my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k*(1+4*x^k+x^(2*k))/(1-x^k)^3))

my(N=66, x='x+O('x^N)); Vec(x+6*sum(k=1, N, moebius(k)*x^(2*k)/(1-x^k)^3))

from sympy import mobius, divisors
def A344596(n): return 3*sum(mobius(n//d)*d*(d-1) for d in divisors(n,generator=True)) if n>1 else 1 # Chai Wah Wu, May 09 2025

Sum_{k=1..n} a(k) * floor(n/k) = n^3.
Sum_{k=1..n} a(k) = A071778(n).
a(n) = 3 * Sum_{d|n} mu(n/d) * (d-1) * d for n > 1.
G.f.: Sum_{k >= 1} mu(k) * x^k * (1 + 4*x^k + x^(2*k))/(1 - x^k)^3.
G.f.: x + 6 * Sum_{k>=1} mu(k) * x^(2*k)/(1 - x^k)^3.
a(2^k) = 3*2^(k-2)*(3*2^k-2) for k>0. - Chai Wah Wu, May 10 2025

A346760 a(n) = Sum_{d|n} mu(n/d) * binomial(d,3).

Original entry on oeis.org

0, 0, 1, 4, 10, 19, 35, 52, 83, 110, 165, 196, 286, 329, 444, 504, 680, 713, 969, 1016, 1294, 1375, 1771, 1752, 2290, 2314, 2841, 2908, 3654, 3476, 4495, 4400, 5290, 5304, 6500, 6124, 7770, 7467, 8852, 8688, 10660, 9802, 12341, 11700, 13652, 13409, 16215, 14768, 18389, 17190

Offset: 1

Ilya Gutkovskiy, Aug 02 2021

nonn

3rd column of A020921.

Cf. A000010, A000292, A007434, A059376, A102309, A117108, A346761.

Table[Sum[MoebiusMu[n/d] Binomial[d, 3], {d, Divisors[n]}], {n, 1, 50}]
nmax = 50; CoefficientList[Series[Sum[MoebiusMu[k] x^(3 k)/(1 - x^k)^4, {k, 1, nmax}], {x, 0, nmax}], x] // Rest

a(n) = sumdiv(n, d, moebius(n/d)*binomial(d, 3)); \\ Michel Marcus, Aug 03 2021

G.f.: Sum_{k>=1} mu(k) * x^(3*k) / (1 - x^k)^4.

a(n) = (A059376(n) - 3 * A007434(n) + 2 * A000010(n)) / 6.

A346761 a(n) = Sum_{d|n} mu(n/d) * binomial(d,4).

Original entry on oeis.org

0, 0, 0, 1, 5, 15, 35, 69, 126, 205, 330, 479, 715, 966, 1360, 1750, 2380, 2919, 3876, 4634, 5950, 6985, 8855, 10062, 12645, 14235, 17424, 19473, 23751, 25820, 31465, 34140, 40590, 43996, 52320, 55365, 66045, 69939, 81536, 86476, 101270, 104964, 123410, 128435, 147504

Offset: 1

Ilya Gutkovskiy, Aug 02 2021

nonn

4th column of A020921.

Cf. A000010, A000332, A007434, A059376, A059377, A102309, A117109, A346760.

Table[Sum[MoebiusMu[n/d] Binomial[d, 4], {d, Divisors[n]}], {n, 1, 45}]
nmax = 45; CoefficientList[Series[Sum[MoebiusMu[k] x^(4 k)/(1 - x^k)^5, {k, 1, nmax}], {x, 0, nmax}], x] // Rest

G.f.: Sum_{k>=1} mu(k) * x^(4*k) / (1 - x^k)^5.

a(n) = (A059377(n) - 6 * A059376(n) + 11 * A007434(n) - 6 * A000010(n)) / 24.

cp's OEIS Frontend

A100448 Number of triples (i,j,k) with 1 <= i <= j < k <= n and gcd{i,j,k} = 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

A123706 Matrix inverse of triangle A010766, where A010766(n,k) = [n/k], for n>=k>=1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A020921 Triangle read by rows: T(m,n) = number of solutions to 1 <= a(1) < a(2) < ... < a(m) <= n, where gcd( a(1), a(2), ..., a(m), n) = 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Sage

A326419 a(n) is the number of distinct Horadam sequences of period n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

A344596 a(n) = Sum_{k=1..n} mu(k) * (floor(n/k)^3 - floor((n-1)/k)^3).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Python

Formula

A346760 a(n) = Sum_{d|n} mu(n/d) * binomial(d,3).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

Formula

A346761 a(n) = Sum_{d|n} mu(n/d) * binomial(d,4).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula