|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|