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,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

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.

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

Adjacent sequences: A328895 A328896 A328897 * A328899 A328900 A328901

Keyword

nonn

Author

Jonathan Blanchette, Oct 30 2019

Extensions

More terms from Antti Karttunen, Apr 12 2020

Status

approved