| Displaying 1-6 of 6 results found.
page
1
Number of ordered quadruples (a,b,c,d) with gcd(a,b,c,d)=1 (1 <= {a,b,c,d} <= n).
+10
15
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
FORMULA
a(n) = Sum_{k=1..n} mu(k)*floor(n/k)^4.
a(n) is asymptotic to c*n^4 with c=0.92393....
PROG
(PARI) a(n)=sum(k=1, n, moebius(k)*floor(n/k)^4)
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
j, k1 = j2, n//j2
Number of ordered triples of integers from [ 1..n ] with no global factor.
+10
12
1, 3, 8, 15, 29, 42, 69, 95, 134, 172, 237, 287, 377, 452, 552, 652, 804, 915, 1104, 1252, 1450, 1635, 1910, 2106, 2416, 2674, 3007, 3301, 3735, 4027, 4522, 4914, 5404, 5844, 6432, 6870, 7572, 8121, 8805, 9389, 10249, 10831, 11776, 12506
COMMENTS
Number of integer-sided triangles with at least two sides <= n and sides relatively prime. - Henry Bottomley, Sep 29 2006
FORMULA
Partial sums of the Moebius transform of the triangular numbers ( A007438). - Steve Butler, Apr 18 2006 G.f.: (1/(1 - x)) * Sum_{k>=1} mu(k) * x^k / (1 - x^k)^3. - Ilya Gutkovskiy, Feb 14 2020 a(n) = n*(n+1)*(n+2)/6 - Sum_{j=2..n} a(floor(n/j)) = A000292(n) - Sum_{j=2..n} a(floor(n/j)). - Chai Wah Wu, Mar 30 2021
EXAMPLE
a(4) = 15 because the 15 triples in question are in lexicographic order: [1,1,1], [1,1,2], [1,1,3], [1,1,4], [1,2,2], [1,2,3], [1,2,4], [1,3,3], [1,3,4], [1,4,4], [2,2,3], [2,3,3], [2,3,4], [3,3,4] and [3,4,4]. - Wolfdieter Lang, Apr 04 2013 The a(4) = 15 triangles with at least two sides <= 4 and sides relatively prime (see Henry Bottomley's comment above) are: [1,1,1], [1,2,2], [2,2,3], [1,3,3], [2,3,3], [2,3,4], [3,3,4], [3,3,5], [1,4,4], [2,4,5], [3,4,4], [3,4,5], [3,4,6], [4,4,5], [4,4,7]. - Alois P. Heinz, Feb 14 2020
MAPLE
with(numtheory):
b:= proc(n) option remember;
add(mobius(n/d)*d*(d+1)/2, d=divisors(n))
end:
a:= proc(n) option remember;
b(n) + `if`(n=1, 0, a(n-1))
end:
MATHEMATICA
a[1] = 1; a[n_] := a[n] = Sum[MoebiusMu[n/d]*d*(d+1)/2, {d, Divisors[n]}] + a[n-1]; Table[a[n], {n, 1, 60}] (* Jean-François Alcover, Jan 20 2014, after Maple *) Accumulate[Table[Sum[MoebiusMu[n/d]*d*(d + 1)/2, {d, Divisors[n]}], {n, 1, 50}]] (* Vaclav Kotesovec, Jan 31 2019 *)
PROG
(Magma) [n eq 1 select 1 else Self(n-1)+ &+[MoebiusMu(n div d) *d*(d+1)/2:d in Divisors(n)]:n in [1..50]]; // Marius A. Burtea, Feb 14 2020 (Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = 1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
j, k1 = j2, n//j2
(PARI) a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+1, 2))); \\ Seiichi Manyama, Jun 12 2021 (PARI) a(n) = binomial(n+2, 3)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021 (PARI) my(N=66, x='x+O('x^N)); Vec(sum(k=1, N, moebius(k)*x^k/(1-x^k)^3)/(1-x)) \\ Seiichi Manyama, Jun 12 2021
Moebius transform of tetrahedral numbers.
+10
7
1, 3, 9, 16, 34, 43, 83, 100, 155, 182, 285, 292, 454, 473, 636, 696, 968, 929, 1329, 1304, 1678, 1735, 2299, 2136, 2890, 2818, 3489, 3484, 4494, 4052, 5455, 5168, 6250, 6168, 7652, 6988, 9138, 8547, 10196, 9840, 12340, 10954, 14189, 13140, 15380
COMMENTS
Partial sums of a(n) give A015634(n). See also A059358, A116963 (applied to shifted version of tetrahedral numbers), inverse Moebius transform of tetrahedral numbers. - Jonathan Vos Post, Apr 20 2006
FORMULA
a(n) = |{(x,y,z) : 1 <= x <= y <= z <= n, gcd(x,y,z,n) = 1}|.
EXAMPLE
a(2)=3 because of the triples (1,1,1), (1,1,2), (1,2,2).
PROG
(PARI) a(n) = sumdiv(n, d, binomial(d+2, 3)*moebius(n/d)); \\ Michel Marcus, Nov 04 2018
Square array T(n,k) read by antidiagonals up. Cumulative column sums of A177975.
+10
7
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
COMMENTS
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
FORMULA
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)
EXAMPLE
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
PROG
(PARI) T(n, k) = sum(j=1, n, sumdiv(j, d, moebius(j/d)*binomial(d+k-2, d-1))); \\ Seiichi Manyama, Jun 12 2021 (PARI) T(n, k) = binomial(n+k-1, k)-sum(j=2, n, T(n\j, k)); \\ Seiichi Manyama, Jun 12 2021
Number of ordered 5-tuples of integers from [ 1..n ] with no global factor.
+10
6
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
FORMULA
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
PROG
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
if n == 0:
return 0
c, j = n+1, 2
k1 = n//j
while k1 > 1:
j2 = n//k1 + 1
j, k1 = j2, n//j2
return n*(n+1)*(n+2)*(n+3)*(n+4)//120-c+j # Chai Wah Wu, Apr 18 2021 (PARI) a(n) = sum(k=1, n, sumdiv(k, d, moebius(k/d)*binomial(d+3, 4))); \\ Seiichi Manyama, Jun 12 2021 (PARI) a(n) = binomial(n+4, 5)-sum(k=2, n, a(n\k)); \\ Seiichi Manyama, Jun 12 2021 (PARI) 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
Triangle read by rows. Polynomials based on sums of Moebius transforms.
+10
2
1, 1, 0, 1, 3, -2, 1, 6, 5, -6, 1, 10, 35, 26, -48, 1, 15, 85, 165, -26, -120, 1, 21, 175, 735, 1264, -36, -1440, 1, 28, 322, 1960, 5929, 8092, -1212, -10080, 1, 36, 546, 4536, 22449, 60564, 57644, -24816, -80640, 1, 45, 870, 9450, 63273, 254205, 572480
COMMENTS
These polynomials were found by entering the rows of A177976 in Wolfram Alpha. The lower left half equals part of the Stirling numbers of the first kind given in table A094638. To evaluate, enter a value for n and divide row sums with factorial numbers as shown in the example section. n=-1 gives A092149, n=0 gives the Mertens function A002321, n=1 gives A000012, n=2 gives A002088, n=3 gives A015631, and n=4 gives A015634.
EXAMPLE
Triangle begins and the polynomials are:
(1*n^0)/1
(1*n^1 +0*n^0)/1
(1*n^2 +3*n^1 -2*n^0)/2
(1*n^3 +6*n^2 +5*n^1 -6*n^0)/6
(1*n^4 +10*n^3 +35*n^2 +26*n^1 -48*n^0)/24
(1*n^5 +15*n^4 +85*n^3 +165*n^2 -26*n^1 -120*n^0)/120
(1*n^6 +21*n^5 +175*n^4 +735*n^3 +1264*n^2 -36*n^1 -1440*n^0)/720
EXTENSIONS
Typo in sequence (erroneous comma) corrected by N. J. A. Sloane, May 22 2010
Search completed in 0.008 seconds
|