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