

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



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


LINKS

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


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


CROSSREFS

Cf. A000005, A160804.
Sequence in context: A336500 A328401 A207666 * A329612 A305980 A329601
Adjacent sequences: A151610 A151611 A151612 * A151614 A151615 A151616


KEYWORD

nonn,more


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


STATUS

approved



