login
A325967
a(n) is the minimum sum of all such subsets of divisors of n for which n-s and (sigma(n)-s)-n are relatively prime, where s is the sum of the subset.
7
0, 0, 0, 0, 0, 5, 0, 0, 0, 1, 0, 1, 0, 1, 4, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 3, 0, 27, 0, 1, 0, 0, 4, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 4, 3, 0, 1, 0, 0, 4, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 4, 1, 0, 1, 0, 1, 0, 3, 0, 1, 0, 1, 0, 1, 0, 1, 0, 3, 4, 1, 0, 1, 8, 1, 0, 1, 6, 5, 0, 0, 4, 0, 0, 1, 0, 1, 4
OFFSET
1,6
COMMENTS
Partition the divisors of n in all possible ways into such complementary subsets x and y for which gcd(n-Sum(x), n-Sum(y)) = 1. a(n) is the minimal value of min(Sum(x), Sum(y)) attained over all such pairs of subsets x and y.
Records 0, 5, 27, 495, 8127, 8289, 10359, 11049, 13809, 15189, 15879, ... occur at 1, 6, 28, 496, 8128, 33148, 41428, 44188, 55228, 60748, 63508, ...
Equivalently, the least k expressible as a sum of distinct divisors of n such that gcd(n-k,A033879(n)) = 1, with the convention that gcd(k,0) = k. - Charlie Neder, Jun 09 2019
FORMULA
a(n) = A000203(n) - A325968(n) = A001065(n) - A325969(n).
For all n, a(A000396(n)) = A000396(n)-1.
For all n, a(n) >= A325817(n).
EXAMPLE
For n=15, its divisors are [1, 3, 5, 15]. If we take an empty set [] and its complement [1, 3, 5, 15], their sums are 0 and 24, but gcd(15-0, 24-15) = gcd(15, 9) = 3 > 1. If we take subsets [1] and [3, 5, 15], then their sums are 1 and 23, but gcd(15-1, 23-15) = gcd(14,8) = 2 > 1. If we take subsets [3] and [1, 5, 15], their sums are 3 and 21, but gcd(15-3, 21-15) = gcd(12, 6) = 6 > 1. Only when we take the subset with a next larger sum, [1, 3] and its complement [5, 15], we get such sums 4 and 20 for which gcd(15-4, 20-15) = gcd(11, 5) = 1. Thus a(15) = 4, the size of the subset with lesser sum.
PROG
(PARI)
\\ Probably not the most optimal algorithm, but at least faster than the implementation using sumbybits (below):
A325967aux(n, ds, s, ms, divs, from=1) = if(1==gcd((s-ds)-n, n-ds), return(ds), for(i=from, #divs, if(ds+divs[i] >= ms, return(ms), ms = min(ms, A325967aux(n, ds+divs[i], s, ms, divs, i+1)))); (ms));
A325967(n) = if(1==gcd(n, sigma(n)), 0, my(divs = List(divisors(n)), s=sigma(n), ms=2*s); fordiv(n, d, if(d>=ms, return(ms), listpop(divs, 1); ms = min(ms, A325967aux(n, d, s, ms, divs)))); (ms));
(PARI)
A325967(n) = { my(divs=divisors(n), s=sigma(n), r, ms=-1); for(b=0, (2^(length(divs)))-1, r=sumbybits(divs, b); if(1==gcd(n-(s-r), n-r), if(ms<0||r<ms, ms=r))); (ms); };
sumbybits(v, b) = { my(s=0, i=1); while(b>0, s += (b%2)*v[i]; i++; b >>= 1); (s); };
CROSSREFS
Cf. A000203, A000396, A009194, A014567 (positions of zeros), A325807, A325817, A325968, A325969.
Sequence in context: A090750 A324656 A325817 * A229656 A216722 A368865
KEYWORD
nonn
AUTHOR
Antti Karttunen, May 29 2019
STATUS
approved