cp's OEIS Frontend

A325095 Number of subsets of {1...n} with no binary carries.

%I A325095 #17 Jul 27 2019 14:57:51
%S A325095 1,2,4,5,10,12,14,15,30,35,40,42,47,49,51,52,104,119,134,139,154,159,
%T A325095 164,166,181,186,191,193,198,200,202,203,406,458,510,525,577,592,607,
%U A325095 612,664,679,694,699,714,719,724,726,778,793,808,813,828,833,838,840
%N A325095 Number of subsets of {1...n} with no binary carries.
%C A325095 A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. For example, the binary representations of {2,5,8} are:
%C A325095   2 =   10,
%C A325095   5 =  101,
%C A325095   8 = 1000,
%C A325095 and since there are no columns with more than one 1, {2,5,8} is counted under a(8).
%H A325095 Alois P. Heinz, <a href="/A325095/b325095.txt">Table of n, a(n) for n = 0..16383</a>
%F A325095 a(2^n - 1) = A000110(n + 1).
%e A325095 The a(1) = 1 through a(7) = 15 subsets:
%e A325095   {}   {}     {}     {}       {}       {}       {}
%e A325095   {1}  {1}    {1}    {1}      {1}      {1}      {1}
%e A325095        {2}    {2}    {2}      {2}      {2}      {2}
%e A325095        {1,2}  {3}    {3}      {3}      {3}      {3}
%e A325095               {1,2}  {4}      {4}      {4}      {4}
%e A325095                      {1,2}    {5}      {5}      {5}
%e A325095                      {1,4}    {1,2}    {6}      {6}
%e A325095                      {2,4}    {1,4}    {1,2}    {7}
%e A325095                      {3,4}    {2,4}    {1,4}    {1,2}
%e A325095                      {1,2,4}  {2,5}    {1,6}    {1,4}
%e A325095                               {3,4}    {2,4}    {1,6}
%e A325095                               {1,2,4}  {2,5}    {2,4}
%e A325095                                        {3,4}    {2,5}
%e A325095                                        {1,2,4}  {3,4}
%e A325095                                                 {1,2,4}
%p A325095 b:= proc(n, t) option remember; `if`(n=0, 1, b(n-1, t)+
%p A325095      `if`(Bits[And](n, t)=0, b(n-1, Bits[Or](n, t)), 0))
%p A325095     end:
%p A325095 a:= n-> b(n, 0):
%p A325095 seq(a(n), n=0..63);  # _Alois P. Heinz_, Mar 28 2019
%t A325095 binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];
%t A325095 stableQ[u_,Q_]:=!Apply[Or,Outer[#1=!=#2&&Q[#1,#2]&,u,u,1],{0,1}];
%t A325095 Table[Length[Select[Subsets[Range[n]],stableQ[#,Intersection[binpos[#1],binpos[#2]]!={}&]&]],{n,0,10}]
%Y A325095 Cf. A000110, A019565, A050315, A080572, A247935, A267610, A267700.
%Y A325095 Cf. A325094, A325096, A325097, A325100, A325103, A325104, A325105.
%K A325095 nonn,look
%O A325095 0,2
%A A325095 _Gus Wiseman_, Mar 27 2019
%E A325095 a(16)-a(55) from _Alois P. Heinz_, Mar 28 2019