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

Author

David W. Wilson

Keywords

• nonn
• nice
• look

Comments

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

Examples

			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.
		

Links

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

Crossrefs

Cf. A002093, A005153, A093896, A119347.

Distinct elements form A030058.

Cf. A027750.

Programs

Haskell

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

Maple

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

Mathematica

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 *)

Python

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

Extensions

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