The On-Line Encyclopedia of Integer Sequences (OEIS)

A318670 revision #15

A318670

Number of subsets of divisors of n whose least common multiple is n and the sum does not exceed n. For n > 1, 1 is excluded from the set of divisors.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 5, 1, 2, 2, 1, 1, 6, 1, 6, 2, 2, 1, 17, 1, 2, 1, 7, 1, 34, 1, 1, 2, 2, 2, 44, 1, 2, 2, 23, 1, 36, 1, 7, 7, 2, 1, 65, 1, 7, 2, 7, 1, 21, 2, 25, 2, 2, 1, 471, 1, 2, 7, 1, 2, 39, 1, 7, 2, 44, 1, 355, 1, 2, 7, 7, 2, 39, 1, 89, 1, 2, 1, 531, 2, 2, 2, 27, 1, 559, 2, 7, 2, 2, 2, 257, 1, 7, 7, 61, 1, 39, 1, 28, 46

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

COMMENTS

These count the "starter sets" employed by a simple backtracking algorithm that computes A317624. See the PARI-program dated Sep 08-10 2018 under that entry.

LINKS

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

Index entries for sequences related to lcm's

FORMULA

a(n) <= A069626(n).

For all n >= 1:

a(A000961(n)) = 1.

a(A006881(n)) = 2.

EXAMPLE

For n = 45, there exists the following subsets of its divisors larger than one (3, 5, 9, 15, 45) that satisfy the condition that the least common multiple of the members is 45, and the sum does not exceed 45: (45), (3, 9, 15), (3, 5, 9, 15), (3, 5, 9), (5, 9), (9, 15) and (5, 9, 15), altogether seven subsets, thus a(45) = 7.

PROG

(PARI)

A318670(n) = if(1==n, 1, my(ds=(divisors(n)[2..numdiv(n)]), subsets = select(v -> ((vecsum(v)<=n)&&(n==lcm(v))), powerset(ds))); length(subsets)); \\ A memory-hog implementation.

powerset(v) = { my(siz=2^length(v), pv=vector(siz)); for(i=0, siz-1, pv[i+1] = choosebybits(v, i)); pv; };

choosebybits(v, m) = { my(s=vector(hammingweight(m)), i=j=1); while(m>0, if(m%2, s[j] = v[i]; j++); i++; m >>= 1); s; }; \\ Antti Karttunen, Sep 08 2018

(PARI)

\\ A better program:

strong_divisors_reversed(n) = vecsort(select(x -> (x>1), divisors(n)), , 4);

A318670aux(orgn, n, parts, from=1, ss=List([])) = { my(k = #parts, s=0, newss); if(lcm(Vec(ss))==orgn, s++); for(i=from, k, if(parts[i]<=n, newss = List(ss); listput(newss, parts[i]); s += A318670aux(orgn, n-parts[i], parts, i+1, newss))); (s) };

A318670(n) = if(1==n, n, A318670aux(n, n, strong_divisors_reversed(n))); \\ Antti Karttunen, Sep 08 2018

CROSSREFS

Cf. A069626, A317624.

Sequence in context: A351945 A351943 A114717 * A323409 A080388 A330742

Adjacent sequences: A318667 A318668 A318669 * A318671 A318672 A318673

KEYWORD

nonn

AUTHOR

Antti Karttunen and David A. Corneth, Sep 08 2018

STATUS

editing