A160804 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) = the minimum number, for any permutation K, of partial sums S that are coprime to n.

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 2, 1, 1, 0, 2, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0, 2, 0, 2, 0, 1, 0, 1, 0, 2, 1, 2, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 2, 0, 1, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0

Offset

1,21

Links

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

Example

The divisors of 12 are 1, 2, 3, 4, 6 and 12. If the permutation K is, for example, (12,6,3,1,2,4), then the partial sums are: 12 = 12, 12+6 = 18, 12+6+3 = 21, 12+6+3+1 = 22, 12+6+3+1+2 = 24, and 12+6+3+1+2+4 = 28. None of these sums are coprime to 12, proving that the minimum number of partial sums coprime to 12 = a(12) = 0.

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(d = divisors(n), cmin = #d, c1); forperm(d, v, c1 = c(v, n); if(c1 < cmin, cmin = c1)); cmin; } \\ Amiram Eldar, Jul 09 2023

Crossrefs

Cf. A000005, A151613.

Sequence in context: A355744 A179010 A292262 * A085854 A216188 A117145

Adjacent sequences: A160801 A160802 A160803 * A160805 A160806 A160807

Keyword

nonn

Author

Leroy Quet, May 26 2009

Extensions

Extended thru a(59) by Ray Chandler, Jun 15 2009

a(60)-a(95) from Amiram Eldar, Jul 09 2023

Status

approved