cp's OEIS Frontend

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

%I A330503 #22 Mar 30 2021 01:42:32
%S A330503 2,6,16,30,60,84,144,198,280,352,504,598,812,960,1152,1360,1728,1938,
%T A330503 2400,2688,3080,3450,4128,4500,5200,5724,6440,7018,8100,8618,9856,
%U A330503 10692,11696,12600,13824,14652,16416,17550,18960,20090,22260,23306,25696,27180,28888
%N A330503 Number of Sós permutations of {0,1,...,n}.
%H A330503 S. Bockting-Conrad, Y. Kashina, T. K. Petersen, and B. E. Tenner, <a href="https://arxiv.org/abs/2007.01132">Sós permutations</a>, arXiv:2007.01132 [math.CO], 2020.
%F A330503 a(n) = (n+1) * Sum_{k=1..n} phi(k), where phi(k) is Euler's totient function.
%F A330503 a(n) = (n+1) * A002088(n).
%e A330503 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}.
%t A330503 MapIndexed[(First[#2] + 1) #1 &, Accumulate@ Array[EulerPhi, 45]] (* _Michael De Vlieger_, Dec 16 2019 *)
%o A330503 (PARI) a(n)={(n+1)*sum(k=1, n, eulerphi(k))} \\ _Andrew Howroyd_, Dec 20 2019
%o A330503 (Python)
%o A330503 from functools import lru_cache
%o A330503 @lru_cache(maxsize=None)
%o A330503 def A330503(n):
%o A330503     if n == 0:
%o A330503         return 0
%o A330503     c, j = 0, 2
%o A330503     k1 = n//j
%o A330503     while k1 > 1:
%o A330503         j2 = n//k1 + 1
%o A330503         c += (j2-j)*(2*A330503(k1)//(k1+1)-1)
%o A330503         j, k1 = j2, n//j2
%o A330503     return (n+1)*(n*(n-1)-c+j)//2 # _Chai Wah Wu_, Mar 29 2021
%Y A330503 Cf. A002088.
%K A330503 easy,nonn
%O A330503 1,1
%A A330503 _Bridget Tenner_, Dec 16 2019
%E A330503 More terms from _Michael De Vlieger_, Dec 16 2019