A328898 Sum of p-ary comparisons units required to rank a sequence in parallel when the sequence is partitioned into heaps equal to the prime factors p of the initial sequence length n.
0, 1, 1, 6, 1, 11, 1, 28, 12, 27, 1, 58, 1, 51, 28, 120, 1, 105, 1, 154, 52, 123, 1, 260, 30, 171, 117, 298, 1, 281, 1, 496, 124, 291, 54, 534, 1, 363, 172, 708, 1, 545, 1, 730, 309, 531, 1, 1096, 56, 685, 292, 1018, 1, 963, 126, 1380, 364, 843, 1, 1462, 1, 963, 597, 2016, 174, 1337, 1, 1738, 532, 1333, 1, 2364, 1, 1371, 715, 2170, 128, 1865
Offset: 1
Keywords
Links
- Antti Karttunen, Table of n, a(n) for n = 1..32768
- Jonathan Blanchette and Robert Laganière, A Curious Link Between Prime Numbers, the Maundy Cake Problem and Parallel Sorting, arXiv:1910.11749 [cs.DS], 2019.
Crossrefs
Cf. A006022.
Programs
-
PARI
a(n) = my(f=factor(n)); n^2*sum(i=1, #f~, (1/f[i,1]) * (1/(prod(j=1, i, f[j,1]^f[j,2]))) * (f[i,1]^f[i,2]-1)/(f[i,1]-1)); \\ Michel Marcus, Oct 31 2019
Formula
a(n) = n^2*Sum_{i=1..m} 1/(f(i)^2*f(i-1)*f(i-2)*...*f(1)) where f(i) is the i-th prime factor of n with repetition and m is the number of prime factors.
a(n) = n^2*Sum_{p(i)}(1/p(i) * 1/(Product_{j=1..i} p(j)^k(j)) * (p(i)^k(i)-1)/(p(i)-1)) where p(i) is the i-th unique prime factor of n with multiplicity k(i) and p(i)
Extensions
More terms from Antti Karttunen, Apr 12 2020
Comments