OFFSET
1,2
FORMULA
EXAMPLE
The divisors of 12 are 1, 2, 3, 4, 6 and 12. The sum of all these is 28, which is not coprime to 12. So possibly the largest number of partial sums that are coprime to 12 is 5 (but it definitely is not 6). Indeed, if the permutation K is, for example, (1,4,2,6,12,3), then the partial sums are: 1 = 1, 1+4 = 5, 1+4+2 = 7, 1+4+2+6 = 13, 1+4+2+6+12 = 25, and 1+4+2+6+12+3 = 28. Five of these sums (1,5,7,13,25) are coprime to 12, proving that the maximum number of partial sums coprime to 12 = a(12) = 5.
PROG
(PARI) c(perm, n) = {my(s=0, k=0); for(i = 1, #perm, s += perm[i]; if(gcd(s, n) == 1, k++)); k; }
a(n) = {my(cmax = 0, c1); forperm(divisors(n), v, c1 = c(v, n); if(c1 > cmax, cmax = c1)); cmax; } \\ Amiram Eldar, Jul 09 2023
CROSSREFS
KEYWORD
nonn
AUTHOR
Leroy Quet, May 26 2009
EXTENSIONS
Extended thru a(59) by Ray Chandler, Jun 15 2009
a(60)-a(77) from Charlie Neder, Jan 17 2019
a(78)-a(95) from Amiram Eldar, Jul 09 2023
STATUS
approved