login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A143270
a(n) = n*A002088(n).
4
1, 4, 12, 24, 50, 72, 126, 176, 252, 320, 462, 552, 754, 896, 1080, 1280, 1632, 1836, 2280, 2560, 2940, 3300, 3956, 4320, 5000, 5512, 6210, 6776, 7830, 8340, 9548, 10368, 11352, 12240, 13440, 14256, 15984, 17100, 18486, 19600, 21730, 22764, 25112
OFFSET
1,2
COMMENTS
Also number of reduced fractions with denominators <= n and values between 1/n and n (inclusive). [Reinhard Zumkeller, Jan 15 2009]
LINKS
FORMULA
a(n) = n*A002088(n), where A002088(n) = partial sums of phi(n).
Equals row sums of triangle A143269.
a(n) = SUM(SUM(0^(GCD(i,j)-1): 1<=j<=i*n): 1<=i<=n). [Reinhard Zumkeller, Jan 15 2009]
EXAMPLE
a(4) = 24 = n*A002088(n) = 4*6.
a(4) = 24 = sum of row 4 terms of triangle A143269: (4 + 4 + 8 + 8).
a(3) = #{1/3,1/2,2/3,1,4/3,3/2,5/3,2,7/3,5/2,8/3,3} = 12. [Reinhard Zumkeller, Jan 15 2009]
MATHEMATICA
Module[{nn=50, ps}, ps=Accumulate[EulerPhi[Range[nn]]]; Times@@@Thread[{Range[nn], ps}]] (* Harvey P. Dale, Jun 04 2023 *)
PROG
(Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def A143270(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)*(2*A143270(k1)//k1-1)
j, k1 = j2, n//j2
return n*(n*(n-1)-c+j)//2 # Chai Wah Wu, Mar 25 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Gary W. Adamson, Aug 03 2008
EXTENSIONS
More terms from Reinhard Zumkeller, Jan 15 2009
STATUS
approved