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

Author

Ilya Gutkovskiy, Sep 20 2019

Keywords

• nonn
• easy

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

Examples

			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
		

Links

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

Crossrefs

Cf. A018818, A210442, A211110, A293813.

Programs

Magma

[1] cat [#RestrictedPartitions(n,{d:d in Divisors(n)| d le Sqrt(n)}):n in [1..70]]; // Marius A. Burtea, Sep 20 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}]

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