A151613 Consider a permutation K = (k(1),k(2),...,k(A000005(n))) of the positive divisors of n. Consider the partial sums S = Sum_{j=1..m} k(j), 1 <= m <= A000005(n). Then a(n) is the maximum number, for any permutation K, of partial sums S that are coprime to n.

1, 2, 2, 3, 2, 2, 2, 4, 3, 3, 2, 5, 2, 3, 3, 5, 2, 4, 2, 5, 4, 3, 2, 6, 3, 3, 4, 4, 2, 6, 2, 6, 3, 3, 4, 8, 2, 3, 4, 6, 2, 5, 2, 5, 5, 3, 2, 9, 3, 5, 3, 5, 2, 5, 4, 7, 4, 3, 2, 10, 2, 3, 6, 7, 4, 6, 2, 5, 3, 6, 2, 10, 2, 3, 6, 5, 4, 5, 2, 9, 5, 3, 2, 10, 4, 3, 3, 7, 2, 9, 3, 5, 4, 3, 3

Offset

1,2

Links

Table of n, a(n) for n=1..95.

Formula

From Charlie Neder, Jan 17 2019: (Start)

a(p) = 2 for prime p.

a(2^k) = k+1.

If n is even, then a(n) <= A000005(n) - floor(A001227(n)/2). (End)

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

Cf. A000005, A001227, A160804.

Sequence in context: A336500 A328401 A207666 * A329612 A305980 A329601

Adjacent sequences: A151610 A151611 A151612 * A151614 A151615 A151616

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