cp's OEIS Frontend

A247935 Number of integer partitions of n whose distinct parts have no binary carries.

%I A247935 #27 May 23 2021 02:47:04
%S A247935 1,1,2,3,4,5,8,10,11,14,18,21,26,30,38,49,47,55,66,74,84,96,110,126,
%T A247935 134,151,171,195,209,235,272,318,307,349,377,422,448,491,534,595,617,
%U A247935 674,734,801,841,925,998,1098,1118,1219,1299,1418,1476,1591,1711,1865
%N A247935 Number of integer partitions of n whose distinct parts have no binary carries.
%C A247935 From _Gus Wiseman_, Mar 31 2019: (Start)
%C A247935 A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the reversed binary expansions of 2, 5, and 8 are
%C A247935   {0,1}
%C A247935   {1,0,1}
%C A247935   {0,0,0,1}
%C A247935 and since there are no columns with more than one 1, the partition (8,5,2) is counted under a(15). The Heinz numbers of these partitions are given by A325097.
%C A247935 (End)
%H A247935 Alois P. Heinz, <a href="/A247935/b247935.txt">Table of n, a(n) for n = 0..1000</a>
%e A247935 From _Gus Wiseman_, Mar 30 2019: (Start)
%e A247935 The a(1) = 1 through a(8) = 11 partitions:
%e A247935   (1)  (2)   (3)    (4)     (5)      (6)       (7)        (8)
%e A247935        (11)  (21)   (22)    (41)     (33)      (43)       (44)
%e A247935              (111)  (211)   (221)    (42)      (52)       (422)
%e A247935                     (1111)  (2111)   (222)     (61)       (611)
%e A247935                             (11111)  (411)     (421)      (2222)
%e A247935                                      (2211)    (2221)     (4211)
%e A247935                                      (21111)   (4111)     (22211)
%e A247935                                      (111111)  (22111)    (41111)
%e A247935                                                (211111)   (221111)
%e A247935                                                (1111111)  (2111111)
%e A247935                                                           (11111111)
%e A247935 (End)
%p A247935 with(Bits):
%p A247935 b:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(i<1, 0,
%p A247935       b(n, i-1, t) +`if`(i>n or And(t, i)>0, 0,
%p A247935       add(b(n-i*j, i-1, Or(t, i)), j=1..n/i))))
%p A247935     end:
%p A247935 a:= n-> b(n$2, 0):
%p A247935 seq(a(n), n=0..80);  # _Alois P. Heinz_, Dec 28 2014
%t A247935 binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A247935 stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
%t A247935 Table[Length[Select[IntegerPartitions[n],stableQ[#,Intersection[binpos[#1],binpos[#2]]!={}&]&]],{n,0,20}] (* _Gus Wiseman_, Mar 30 2019 *)
%t A247935 b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, If[i < 1, 0, b[n, i - 1, t] + If[i > n || BitAnd[t, i] > 0, 0, Sum[b[n - i*j, i - 1, BitOr[t, i]], {j, 1, n/i}]]]];
%t A247935 a[n_] := b[n, n, 0];
%t A247935 a /@ Range[0, 80] (* _Jean-François Alcover_, May 23 2021, after _Alois P. Heinz_ *)
%Y A247935 Cf. A000110, A000120, A050315, A070939, A080572, A248605, A267610.
%Y A247935 Cf. A325095, A325096, A325097, A325098, A325102, A325103, A325109.
%K A247935 nonn
%O A247935 0,3
%A A247935 _David S. Newman_, Sep 26 2014
%E A247935 More terms from _Alois P. Heinz_, Oct 15 2014
%E A247935 Name edited by _Gus Wiseman_, Mar 31 2019