A030058 -id:A030058 - cp's OEIS frontend

A030057 Least number that is not a sum of distinct divisors of n.

2, 4, 2, 8, 2, 13, 2, 16, 2, 4, 2, 29, 2, 4, 2, 32, 2, 40, 2, 43, 2, 4, 2, 61, 2, 4, 2, 57, 2, 73, 2, 64, 2, 4, 2, 92, 2, 4, 2, 91, 2, 97, 2, 8, 2, 4, 2, 125, 2, 4, 2, 8, 2, 121, 2, 121, 2, 4, 2, 169, 2, 4, 2, 128, 2, 145, 2, 8, 2, 4, 2, 196, 2, 4, 2, 8, 2, 169, 2, 187, 2, 4, 2, 225, 2, 4, 2, 181

Offset: 1

David W. Wilson

a(n) = 2 if and only if n is odd. a(2^n) = 2^(n+1). - Emeric Deutsch, Aug 07 2005
a(n) > n if and only if n belongs to A005153, and then a(n) = sigma(n) + 1. - Michel Marcus, Oct 18 2013
The most frequent values are 2 (50%), 4 (16.7%), 8 (5.7%), 13 (3.2%), 16 (2.4%), 29 (1.3%), 32 (1%), 40, 43, 61, ... - M. F. Hasler, Apr 06 2014
The indices of records occur at the highly abundant numbers, excluding 3 and 10, if Jaycob Coleman's conjecture at A002093 that all these numbers are practical numbers (A005153) is true. - Amiram Eldar, Jun 13 2020

			a(10)=4 because 4 is the least positive integer that is not a sum of distinct divisors (namely 1,2,5 and 10) of 10.

David Wasserman and T. D. Noe, Table of n, a(n) for n = 1..10000 (first 1000 terms from David Wasserman)

Cf. A002093, A005153, A093896, A119347.
Distinct elements form A030058.
Cf. A027750.

a030057 n = head $ filter ((== 0) . p (a027750_row n)) [1..] where
   p _      0 = 1
   p []     _ = 0
   p (k:ks) x = if x < k then 0 else p ks (x - k) + p ks x
-- Reinhard Zumkeller, Feb 27 2012

with(combinat): with(numtheory): for n from 1 to 100 do div:=powerset(divisors(n)): b[n]:=sort({seq(sum(div[i][j],j=1..nops(div[i])),i=1..nops(div))}) od: for n from 1 to 100 do B[n]:={seq(k,k=0..1+sigma(n))} minus b[n] od: seq(B[n][1],n=1..100); # Emeric Deutsch, Aug 07 2005

a[n_] :=  First[ Complement[ Range[ DivisorSigma[1, n] + 1], Total /@ Subsets[ Divisors[n]]]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, Jan 02 2012 *)

from sympy import divisors
def A030057(n):
    c = {0}
    for d in divisors(n,generator=True):
        c |=  {a+d for a in c}
    k = 1
    while k in c:
        k += 1
    return k # Chai Wah Wu, Jul 05 2023

Edited by N. J. A. Sloane, May 05 2007

A308605 Number of distinct subset sums of the subsets of the set of divisors of n. Here 0 (as the sum of an empty subset) is included in the count.

Original entry on oeis.org

2, 4, 4, 8, 4, 13, 4, 16, 8, 16, 4, 29, 4, 16, 16, 32, 4, 40, 4, 43, 16, 16, 4, 61, 8, 16, 16, 57, 4, 73, 4, 64, 16, 16, 16, 92, 4, 16, 16, 91, 4, 97, 4, 64, 56, 16, 4, 125, 8, 64, 16, 64, 4, 121, 16, 121, 16, 16, 4, 169, 4, 16, 60, 128, 16, 145, 4, 64, 16, 143, 4, 196, 4, 16, 64, 64, 16, 169, 4, 187, 32, 16, 4, 225

Offset: 1

Ivan N. Ianakiev, Jun 10 2019

nonn

Conjecture: When the terms are sorted and the duplicates deleted a supersequence of A030058 is obtained. Note that A030058 is a result of the same operation applied to A030057.

a(p^k) = 2^(k+1) if p is prime, and a(n) = 2n+1 if n is an even perfect number. - David Radcliffe, Dec 22 2022

			The subsets of the set of divisors of 6 are {{},{1},{2},{3},{6},{1,2},{1,3},{1,6},{2,3},{2,6},{3,6},{1,2,3},{1,2,6},{1,3,6},{2,3,6},{1,2,3,6}}, with the following sums {0,1,2,3,6,3,4,7,5,8,9,6,9,10,11,12}, of which 13 are distinct. Therefore, a(6)=13.

Antti Karttunen, Table of n, a(n) for n = 1..10000

One more than A119347.

Cf. A030057, A030058, A083207 (positions of odd terms), A179527 (parity of terms).

A308605 := proc(n)
    # set of the divisors
    dvs := numtheory[divisors](n) ;
    # set of all the subsets of the divisors
    pdivs := combinat[powerset](dvs) ;
    # the set of the sums in subsets of divisors
    dvss := {} ;
    # loop over all subsets of divisors
    for s in pdivs do
        # compute sum over entries of the subset
        sps := add(d,d=s) ;
        # add sum to the realized set of sums
        dvss := dvss union {sps} ;
    end do:
    # count number of distinct entries (distinct sums)
    nops(dvss) ;
end proc:
seq(A308605(n),n=1..20) ; # R. J. Mathar, Dec 20 2022

f[n_]:=Length[Union[Total/@Subsets[Divisors[n]]]]; f/@Range[100]

A308605(n) = { my(c=[0]); fordiv(n,d, c = Set(concat(c,vector(#c,i,c[i]+d)))); (#c); }; \\ (after Chai Wah Wu's Python-code in A119347, but see also above) - Antti Karttunen, Nov 29 2024

A308605(n) = { my(p=1); fordiv(n, d, p *= (1 + 'x^d)); sum(i=0,poldegree(p),(0Antti Karttunen, Nov 29 2024

from sympy import divisors
def a308605(n):
    s = set([0])
    for d in divisors(n):
        s = s.union(set(x + d for x in s))
    return len(s) # David Radcliffe, Dec 22 2022

a(n) = 1 + A119347(n). - Rémy Sigrist, Jun 10 2019

Definition clarified and more terms added by Antti Karttunen, Nov 29 2024

cp's OEIS Frontend

A030057 Least number that is not a sum of distinct divisors of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Python

Extensions