A327642 Number of partitions of n into divisors of n that are at most sqrt(n).

1, 1, 1, 1, 3, 1, 4, 1, 5, 4, 6, 1, 19, 1, 8, 6, 25, 1, 37, 1, 36, 8, 12, 1, 169, 6, 14, 10, 64, 1, 247, 1, 81, 12, 18, 8, 1072, 1, 20, 14, 405, 1, 512, 1, 144, 82, 24, 1, 2825, 8, 146, 18, 196, 1, 1000, 12, 743, 20, 30, 1, 19858, 1, 32, 112, 969, 14, 1728, 1, 324, 24, 1105

Offset

0,5

Comments

a(n) > n if n is in A058080 Union {0}, and, a(n) <= n if n is in A007964; indeed, a(n) = n only for n = 1. - Bernard Schott, Sep 22 2019

Links

David A. Corneth, Table of n, a(n) for n = 0..9999 (first 5001 terms from Robert Israel)

Formula

a(n) = [x^n] Product_{d|n, d <= sqrt(n)} 1 / (1 - x^d).

a(p) = 1, where p is prime.

a(p*q) = q+1 if p <= q are primes. - Robert Israel, Sep 22 2019

Example

The divisors of 6 are 1, 2, 3, 6 and sqrt(6) = 2.449..., so the possible partitions are 1+1+1+1+1+1 = 1+1+1+1+2 = 1+1+2+2 = 2+2+2; thus a(6) = 4. - Bernard Schott, Sep 22 2019

Maple

f:= proc(n) local x, t, S;
    S:= 1;
    for t in numtheory:-divisors(n) do
      if t^2 <= n then
        S:= series(S/(1-x^t), x, n+1);
      fi
    od;
    coeff(S, x, n);
end proc:
map(f, [$0..100]); # Robert Israel, Sep 22 2019

Mathematica

a[n_] := SeriesCoefficient[Product[1/(1 - Boole[d <= Sqrt[n]] x^d), {d, Divisors[n]}], {x, 0, n}]; Table[a[n], {n, 0, 70}]

Prog

(Magma) [1] cat [#RestrictedPartitions(n, {d:d in Divisors(n)| d le Sqrt(n)}):n in [1..70]]; // Marius A. Burtea, Sep 20 2019

Crossrefs

Cf. A018818, A210442, A211110, A293813.

Sequence in context: A221185 A242746 A363258 * A358919 A354617 A324242

Adjacent sequences: A327639 A327640 A327641 * A327643 A327644 A327645

Keyword

nonn,easy

Author

Ilya Gutkovskiy, Sep 20 2019

Status

approved