|
%I #23 Jul 09 2023 03:17:20
%S 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,
%T 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,
%U 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
%N 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.
%F From _Charlie Neder_, Jan 17 2019: (Start)
%F a(p) = 2 for prime p.
%F a(2^k) = k+1.
%F If n is even, then a(n) <= A000005(n) - floor(A001227(n)/2). (End)
%e 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.
%o (PARI) c(perm, n) = {my(s=0, k=0); for(i = 1, #perm, s += perm[i]; if(gcd(s, n) == 1, k++)); k;}
%o 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
%Y Cf. A000005, A001227, A160804.
%K nonn
%O 1,2
%A _Leroy Quet_, May 26 2009
%E Extended thru a(59) by _Ray Chandler_, Jun 15 2009
%E a(60)-a(77) from _Charlie Neder_, Jan 17 2019
%E a(78)-a(95) from _Amiram Eldar_, Jul 09 2023
|
