A071778
Number of ordered triples (a, b, c) with gcd(a, b, c) = 1 and 1 <= {a, b, c} <= n.
Original entry on oeis.org
1, 7, 25, 55, 115, 181, 307, 439, 637, 841, 1171, 1447, 1915, 2329, 2881, 3433, 4249, 4879, 5905, 6745, 7861, 8911, 10429, 11557, 13297, 14773, 16663, 18355, 20791, 22495, 25285, 27541, 30361, 32905, 36289, 38845, 42841, 46027, 49987, 53395
Offset: 1
Michael Malak (mmalak(AT)alum.mit.edu), Jun 04 2002
-
public class Triples { public static void main(String[] argv) { int i, j, k, a, m, n, d; boolean cf; try {a = Integer.parseInt(argv[0]);} catch (Exception e) {a = 10;}
for (m = 1; m <= a; m++) { n = 0; for (i = 1; i <= m; i++) for (j = 1; j <= m; j++) for (k = 1; k <= m; k++) { cf = false; for (d = 2; d <= m; d++) cf = cf || ((i % d == 0) && (j % d == 0) && (k % d == 0)); if (!cf) n++; } System.out.println(m + ": " + n); } } }
-
f:=proc(n) local i,j,k,t1,t2,t3; t1:=0; for i from 1 to n do for j from 1 to n do t2:=gcd(i,j); for k from 1 to n do t3:=gcd(t2,k); if t3 = 1 then t1:=t1+1; fi; od: od: od: t1; end;
-
a[n_] := Sum[MoebiusMu[k]*Quotient[n, k]^3, {k, 1, n}]; Array[a, 40] (* Jean-François Alcover, Apr 14 2014, after Benoit Cloitre *)
-
a(n)=sum(k=1,n,moebius(k)*(n\k)^3)
-
a(n)=my(s); forsquarefree(k=1,n, s+=moebius(k)*(n\k[1])^3); s \\ Charles R Greathouse IV, Jan 08 2018
-
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)/(1-x)) \\ Seiichi Manyama, May 22 2021
-
from functools import lru_cache
@lru_cache(maxsize=None)
def A071778(n):
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A071778(k1)
j, k1 = j2, n//j2
return n*(n**2-1)-c+j # Chai Wah Wu, Mar 29 2021
A082540
Number of ordered quadruples (a,b,c,d) with gcd(a,b,c,d)=1 (1 <= {a,b,c,d} <= n).
Original entry on oeis.org
1, 15, 79, 239, 607, 1199, 2303, 3823, 6223, 9279, 13919, 19183, 27007, 35743, 47519, 60735, 78719, 97103, 122447, 148527, 181839, 216959, 262543, 306863, 365343, 423855, 495855, 569055, 661679, 748527, 862047, 972191, 1104831, 1237247
Offset: 1
-
a(n)=sum(k=1,n,moebius(k)*floor(n/k)^4)
-
from functools import lru_cache
@lru_cache(maxsize=None)
def A082540(n):
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A082540(k1)
j, k1 = j2, n//j2
return n*(n**3-1)-c+j # Chai Wah Wu, Mar 29 2021
A082544
Number of ordered quintuples (a,b,c,d,e) with gcd(a,b,c,d,e)=1 (1<= {a,b,c,d,e} <= n).
Original entry on oeis.org
1, 31, 241, 991, 3091, 7501, 16531, 31711, 57781, 96601, 157651, 240031, 362491, 519961, 739201, 1012441, 1383721, 1822711, 2409241, 3091441, 3966301, 4974751, 6257461, 7680781, 9481681, 11474941, 13916191, 16610371, 19911151, 23435191
Offset: 1
-
a(n)=sum(k=1,n,moebius(k)*floor(n/k)^5)
-
from functools import lru_cache
@lru_cache(maxsize=None)
def A082544(n):
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A082544(k1)
j, k1 = j2, n//j2
return n*(n**4-1)-c+j # Chai Wah Wu, Mar 29 2021
A342586
a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.
Original entry on oeis.org
1, 63, 6087, 608383, 60794971, 6079301507, 607927104783, 60792712854483, 6079271032731815, 607927102346016827, 60792710185772432731, 6079271018566772422279, 607927101854119608051819, 60792710185405797839054887, 6079271018540289787820715707, 607927101854027018957417670303
Offset: 0
- Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54. (See link below.)
Related counts of k-tuples:
-
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
A342841
Number of ordered triples (x, y, z) with gcd(x, y, z) = 1 and 1 <= {x, y, z} <= 10^n.
Original entry on oeis.org
1, 841, 832693, 832046137, 831916552903, 831908477106883, 831907430687799769, 831907383078281024371, 831907373418800027750413, 831907372722449100147414487, 831907372589073124899487831735, 831907372581823023465031521920149, 831907372580768386561159867257319711
Offset: 0
For visualization, the set(x, y, z) is inscribed in a cube matrix.
"o" stands for a gcd = 1.
"." stands for a gcd > 1.
.
For n=1, the size of the cube matrix is 10 X 10 X 10:
.
/ : : : : : : : : : :
/ 100 Sum (z = 1)
z = 7 |/1 2 3 4 5 6 7 8 9 10 |
--+--------------------- 75 Sum (z = 2)
1 /| o o o o o o o o o o 10 |
2/ | o o o o o o o o o o 10 91 Sum (z = 3)
/ 10 |
z = 8 |/1 2 3 4 5 6 7 8 9 10 10 75 Sum (z = 4)
--+--------------------- 10 /
1 /| o o o o o o o o o o 10 10 96 Sum (z = 5)
2/ | o . o . o . o . o . 5 9 /
/ 10 10 67 Sum (z = 6)
z = 9 |/1 2 3 4 5 6 7 8 9 10 5 10 /
--+--------------------- 10 10 /
1 /| o o o o o o o o o o 10 5 --/
2/ | o o o o o o o o o o 10 10 99 Sum (z = 7)
/ 7 5 /
z = 10 |/1 2 3 4 5 6 7 8 9 10 10 10 /
--+--------------------- 10 5 /
1 | o o o o o o o o o o 10 7 --/
2 | o . o . o . o . o . 5 10 75 Sum (z = 8)
3 | o o o o o o o o o o 10 10 /
4 | o . o . o . o . o . 5 7 /
5 | o o o o . o o o o . 8 10 /
6 | o . o . o . o . o . 5 --/
7 | o o o o o o o o o o 10 91 Sum (z = 9)
8 | o . o . o . o . o . 5 /
9 | o o o o o o o o o o 10 /
10 | o . o . . . o . o . 4 /
--/
72 Sum (z = 10)
/
|
------
841 Cube Sum (z = 1..10)
- Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.
Related counts of k-tuples:
-
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):
for z in range(1, pow(10, n)+1):
if math.gcd(math.gcd(y, x),z) == 1:
counter += 1
print(n, counter)
A343193
Number of ordered quadruples (w, x, y, z) with gcd(w, x, y, z) = 1 and 1 <= {w, x, y, z} <= 10^n.
Original entry on oeis.org
1, 9279, 92434863, 923988964495, 9239427676877311, 92393887177379735327, 923938441006918271400831, 9239384074081430755652624559, 92393840333765561759423951663423, 923938402972369921481535120722882015
Offset: 0
(1,2,2,3) is counted, but (2,4,4,6) is not, because gcd = 2.
For n=1, the size of the division tesseract matrix is 10 X 10 X 10 X 10:
.
o------------x(w=10)------------o
/|. ./ |
/ |. ./ |
/ |. ./ |
/ |. ./ |
/ |. z(w=10) |
/ |. . / |
/ |. . / |
/ |. . / y(w=10)
o------------------------------.o |
|\ /|¯¯¯¯¯¯x(w=1)¯¯¯¯¯¯/. | |
| w / | /.| | |
| \ z(w=1)| /. | | |
| \ / |y(w=1) /. | | |
| \/-------------------/. | | |
| | | | | | w | sums
| | Cube at w = 1 | | | | ----+-----
| | 10 X 10 X 10 | _ _| |---------o 1 | 1000
| | contains | / | / 2 | 875
| | 1000 | / | / 3 | 973
| | completely | / | / 4 | 875
| | reduced fractions | / | / 5 | 992
| | |/ | / 6 | 849
| /------------------- \ | / 7 | 999
| / \ | / 8 | 875
| w w | / 9 | 973
| / \ | / 10 | 868
| / \ |/ ----+-----
o -------------------------------o sum for a(1) | 9279
- Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.
Related counts of k-tuples:
A344527
Square array T(n,k), n >= 1, k >= 1, read by antidiagonals, where T(n,k) is the number of ordered k-tuples (x_1, x_2, ..., x_k) with gcd(x_1, x_2, ..., x_k) = 1 (1 <= {x_1, x_2, ..., x_k} <= n).
Original entry on oeis.org
1, 1, 1, 1, 3, 1, 1, 7, 7, 1, 1, 15, 25, 11, 1, 1, 31, 79, 55, 19, 1, 1, 63, 241, 239, 115, 23, 1, 1, 127, 727, 991, 607, 181, 35, 1, 1, 255, 2185, 4031, 3091, 1199, 307, 43, 1, 1, 511, 6559, 16255, 15559, 7501, 2303, 439, 55, 1, 1, 1023, 19681, 65279, 77995, 45863, 16531, 3823, 637, 63, 1
Offset: 1
G.f. of column 3: (1/(1 - x)) * Sum_{i>=1} mu(i) * (x^i + 4*x^(2*i) + x^(3*i))/(1 - x^i)^3.
Square array begins:
1, 1, 1, 1, 1, 1, ...
1, 3, 7, 15, 31, 63, ...
1, 7, 25, 79, 241, 727, ...
1, 11, 55, 239, 991, 4031, ...
1, 19, 115, 607, 3091, 15559, ...
1, 23, 181, 1199, 7501, 45863, ...
-
T[n_, k_] := Sum[MoebiusMu[j] * Quotient[n, j]^k, {j, 1, n}]; Table[T[k, n - k + 1], {n, 1, 11}, {k, 1, n}] // Flatten (* Amiram Eldar, May 22 2021 *)
-
T(n, k) = sum(j=1, n, moebius(j)*(n\j)^k);
-
T(n, k) = n^k-sum(j=2, n, T(n\j, k));
-
from functools import lru_cache
from itertools import count, islice
@lru_cache(maxsize=None)
def A344527_T(n,k):
if n == 0:
return 0
c, j, k1 = 1, 2, n//2
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A344527_T(k1,k)
j, k1 = j2, n//j2
return n*(n**(k-1)-1)-c+j
def A344527_gen(): # generator of terms
return (A344527_T(k+1, n-k) for n in count(1) for k in range(n))
A344527_list = list(islice(A344527_gen(),30)) # Chai Wah Wu, Nov 02 2023
A343282
Number of ordered 5-tuples (v,w, x, y, z) with gcd(v, w, x, y, z) = 1 and 1 <= {v, w, x, y, z} <= 10^n.
Original entry on oeis.org
1, 96601, 9645718621, 964407482028001, 96438925911789115351, 9643875373658964992585011, 964387358678775616636890654841, 96438734235127451288511508421855851, 9643873406165059293451290072800801506621
Offset: 0
- Joachim von zur Gathen and Jürgen Gerhard, Modern Computer Algebra, Cambridge University Press, Second Edition 2003, pp. 53-54.
Related counts of k-tuples:
A344038
Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= 10^n).
Original entry on oeis.org
1, 983583, 983029267047, 982960635742968103, 982953384128772770413831, 982952672223441253533233827367, 982952600027678075050509511271466303, 982952593055042000417993486008754893529583, 982952592342881094406730790044111038427637071855
Offset: 0
Related counts of k-tuples:
-
a(n)={sum(k=1, 10^n+1, moebius(k)*(10^n\k)^6)} \\ Andrew Howroyd, May 08 2021
-
from labmath import mobius
def A344038(n): return sum(mobius(k)*(10**n//k)**6 for k in range(1, 10**n+1))
A332468
a(n) = Sum_{k=1..n} mu(k) * floor(n/k)^n.
Original entry on oeis.org
1, 3, 25, 239, 3091, 45863, 821227, 16711423, 387138661, 9990174303, 285262663291, 8913906888703, 302861978789371, 11111328334033327, 437889112287422401, 18446462446101903615, 827238009323454485641, 39346257879101283645743, 1978418304199236175597105
Offset: 1
-
[&+[MoebiusMu(k)*Floor(n/k)^n:k in [1..n]]:n in [1..20]]; // Marius A. Burtea, Feb 13 2020
-
Table[Sum[MoebiusMu[k] Floor[n/k]^n, {k, 1, n}], {n, 1, 19}]
b[n_, k_] := b[n, k] = n^k - Sum[b[Floor[n/j], k], {j, 2, n}]; a[n_] := b[n, n]; Table[a[n], {n, 1, 19}]
-
a(n)={sum(k=1, n, moebius(k) * floor(n/k)^n)} \\ Andrew Howroyd, Feb 13 2020
-
from functools import lru_cache
@lru_cache(maxsize=None)
def A344527_T(n,k):
if n == 0:
return 0
c, j, k1 = 1, 2, n//2
while k1 > 1:
j2 = n//k1 + 1
c += (j2-j)*A344527_T(k1,k)
j, k1 = j2, n//j2
return n*(n**(k-1)-1)-c+j
def A332468(n): return A344527_T(n,n) # Chai Wah Wu, Nov 02 2023
Showing 1-10 of 10 results.
