login
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.
2
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,4
COMMENTS
a(1) = 0.
1 <= a(n) <= (n^2-n)/2 for all n>1.
a(n) = (n^2-n)/2, if n is a power of 2.
a(n) = 1, if n is a prime number.
LINKS
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.
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)<p(i+1).
PROG
(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
CROSSREFS
Cf. A006022.
Sequence in context: A348982 A350677 A046618 * A216605 A342635 A107348
KEYWORD
nonn
AUTHOR
Jonathan Blanchette, Oct 30 2019
EXTENSIONS
More terms from Antti Karttunen, Apr 12 2020
STATUS
approved