A173493 Number of distinct squares that can be partitioned into distinct divisors of n.

1, 1, 2, 2, 1, 3, 1, 3, 3, 2, 1, 5, 1, 3, 4, 5, 1, 6, 1, 6, 3, 3, 1, 7, 2, 2, 4, 7, 1, 8, 1, 7, 3, 2, 2, 9, 1, 1, 3, 9, 1, 9, 1, 7, 7, 3, 1, 11, 2, 5, 2, 4, 1, 10, 2, 10, 2, 1, 1, 12, 1, 2, 7, 11, 1, 12, 1, 4, 2, 11, 1, 13, 1, 1, 9, 7, 1, 12, 1, 13, 6, 1, 1, 14, 1, 1, 2, 13, 1, 15, 1, 6, 2, 3, 3, 15, 1, 8

Offset: 1

Author

Reinhard Zumkeller, Feb 20 2010

Keywords

• nonn

Comments

The partitions of the squares are generally not unique, see examples.

Examples

			divisors(9) = {1, 3, 9}: a(9) = #{1, 3+1, 9} = 3.
divisors(10) = {1, 2, 5, 10}: a(10) = #{1, 10+5+1} = 2.
divisors(12) = {1,2,3,4,6,12}: a(12) = #{1,4,9,16,25} = 5:
  2^2 = 4 = 3 + 1,
  3^2 = 6 + 3 = 6 + 2 + 1 = 4 + 3 + 2,
  4^2 = 12 + 4 = 12 + 3 + 1 = 6 + 4 + 3 + 2 + 1,
  5^2 = 12 + 6 + 4 + 3 = 12 + 6 + 4 + 2 + 1.
divisors(42)={1,2,3,6,7,14,21,42}: a(42)=#{k^2: 1<=k<=9}=9:
  2^2 = 3+1,
  3^2 = 7+2 = 6+3 = 6+2+1,
  4^2 = 14+2 = 7+6+3 = 7+6+2+1,
  5^2 = 21 + 3 + 1 = 14 + 7 + 3 + 1 = 14 + 6 + 3 + 2,
  6^2 = 21 + 14 + 1 = 21 + 7 + 6 + 2,
  7^2 = 42 + 7 = 42 + 6 + 1 = 21 + 14 + 7 + 6 + 1,
  8^2 = 42 + 21 + 1 = 42 + 14 + 7 + 1 = 42 + 14 + 6 + 2,
  9^2 = 42 + 21 + 14 + 3 + 1 = 42 + 21 + 7 + 6 + 3 + 2.
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..250 from Reinhard Zumkeller)

Crossrefs

Cf. A000203, A006532, A033630, A072243, A078705, A173494.

Programs

Mathematica

a[n_] := Module[{d = Divisors[n], sum, sq, x}, sum = Plus @@ d; sq = Range[Floor[Sqrt[sum]]]^2; Count[CoefficientList[Product[1 + x^i, {i, d}], x][[1 + sq]], ?(# > 0&)]]; Array[a, 100] (* _Amiram Eldar, Apr 16 2025 *)

Formula

a(n) <= A078705(n).

a(A173494(n)) = 1.