cp's OEIS Frontend

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.

%I A325967 #25 Jun 11 2019 00:13:01
%S A325967 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,
%T A325967 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,
%U A325967 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
%N 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.
%C A325967 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.
%C A325967 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, ...
%C A325967 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
%H A325967 Antti Karttunen, <a href="/A325967/b325967.txt">Table of n, a(n) for n = 1..65537</a>
%H A325967 <a href="/index/Si#SIGMAN">Index entries for sequences related to sigma(n)</a>
%F A325967 a(n) = A000203(n) - A325968(n) = A001065(n) - A325969(n).
%F A325967 For all n, a(A000396(n)) = A000396(n)-1.
%F A325967 For all n, a(n) >= A325817(n).
%e A325967 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.
%o A325967 (PARI)
%o A325967 \\ Probably not the most optimal algorithm, but at least faster than the implementation using sumbybits (below):
%o A325967 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));
%o A325967 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));
%o A325967 (PARI)
%o A325967 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); };
%o A325967 sumbybits(v,b) = { my(s=0,i=1); while(b>0,s += (b%2)*v[i]; i++; b >>= 1); (s); };
%Y A325967 Cf. A000203, A000396, A009194, A014567 (positions of zeros), A325807, A325817, A325968, A325969.
%K A325967 nonn
%O A325967 1,6
%A A325967 _Antti Karttunen_, May 29 2019