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
LINKS
FORMULA
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
KEYWORD
nonn
AUTHOR
Antti Karttunen, May 29 2019
STATUS
approved