A330503 Number of Sós permutations of {0,1,...,n}.

2, 6, 16, 30, 60, 84, 144, 198, 280, 352, 504, 598, 812, 960, 1152, 1360, 1728, 1938, 2400, 2688, 3080, 3450, 4128, 4500, 5200, 5724, 6440, 7018, 8100, 8618, 9856, 10692, 11696, 12600, 13824, 14652, 16416, 17550, 18960, 20090, 22260, 23306, 25696, 27180, 28888

Offset: 1

Author

Bridget Tenner, Dec 16 2019

Keywords

• easy
• nonn

Examples

			For n = 3, the a(3) = 16 Farey functions of {0,1,2,3} are {0123, 3012, 2301, 1230, 0312, 2031, 1203, 3120, 0213, 3021, 1302, 2130, 0321, 1032, 2103, 3210}.
		

Links

• S. Bockting-Conrad, Y. Kashina, T. K. Petersen, and B. E. Tenner, Sós permutations, arXiv:2007.01132 [math.CO], 2020.

Crossrefs

Cf. A002088.

Programs

Mathematica

MapIndexed[(First[#2] + 1) #1 &, Accumulate@ Array[EulerPhi, 45]] (* Michael De Vlieger, Dec 16 2019 *)

PARI

a(n)={(n+1)*sum(k=1, n, eulerphi(k))} \\ Andrew Howroyd, Dec 20 2019

Python

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

Formula

a(n) = (n+1) * Sum_{k=1..n} phi(k), where phi(k) is Euler's totient function.

a(n) = (n+1) * A002088(n).

Extensions

More terms from Michael De Vlieger, Dec 16 2019