A256012 Number of partitions of n into distinct parts that are not squarefree.

1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 2, 1, 0, 0, 2, 1, 1, 0, 3, 2, 1, 0, 4, 3, 1, 2, 5, 4, 2, 2, 6, 5, 3, 2, 9, 7, 4, 4, 11, 8, 5, 5, 13, 13, 7, 7, 17, 17, 9, 9, 22, 20, 15, 12, 27, 26, 19, 15, 33, 33, 23, 23, 41, 41, 30, 29, 49, 51, 39, 35, 65, 63, 50, 47, 79

Offset

0,13

Comments

Conjecture: a(n) > 0 for n > 23.

This was proved by an autonomous AI agent, see the Tsoukalas paper and the Lean file. The proof uses the fact that a positive count is equivalent to nonemptiness to reduce the problem to exhibiting one valid partition, then case-splits on n mod 4, giving explicit witnesses {n}, {9, n-9}, {18, n-18}, or {27, n-27}. Each part is nonsquarefree because it is divisible by 4 or 9 (Summary by Opus 4.7). - Ralf Stephan, May 26 2026

Links

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Google Deepmind, AlphaProof Nexus: A256012 Lean file

George Tsoukalas et al., Advancing Mathematics Research with AI-Driven Formal Proof Search, arXiv:2605.22763 [cs.AI], 2026.

Formula

G.f.: Product_{k>=1} (1 + x^k)/(1 + mu(k)^2*x^k), where mu(k) is the Moebius function (A008683). - Ilya Gutkovskiy, Dec 30 2016

Example

First nonsquarefree numbers: 4,8,9,12,16,18,20,24,25,27,28, ...  hence
a(20) = #{20, 16+4, 12+8} = 3;
a(21) = #{12+9, 9+8+4} = 2;
a(22) = #{18+4} = 1;
a(23) = #{ } = 0;
a(24) = #{24, 20+4, 16+8, 12+8+4} = 4;
a(25) = #{25, 16+9, 12+9+4} = 3.

Maple

with(numtheory):
b:= proc(n, i) option remember;
      `if`(i*(i+1)/2<n, 0, `if`(n=0, 1, b(n, i-1)+
      `if`(i>n or issqrfree(i), 0, b(n-i, i-1))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..100);  # Alois P. Heinz, Jun 02 2015

Mathematica

b[n_, i_] := b[n, i] = If[i*(i+1)/2<n, 0, If[n==0, 1, b[n, i-1] + If[i>n || SquareFreeQ[i], 0, b[n-i, i-1]]]]; a[n_] := b[n, n]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Oct 22 2015, after Alois P. Heinz *)

Prog

(Haskell)
a256012 = p a013929_list where
   p _      0 = 1
   p (k:ks) m = if m < k then 0 else p ks (m - k) + p ks m

Crossrefs

Cf. A013929, A114374, A087188.

Sequence in context: A249808 A258453 A025874 * A332040 A263251 A318370

Adjacent sequences: A256009 A256010 A256011 * A256013 A256014 A256015

Keyword

nonn

Author

Reinhard Zumkeller, Jun 01 2015

Status

approved