login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A325105 Number of binary carry-connected subsets of {1...n}. 10
1, 2, 3, 7, 8, 20, 48, 112, 113, 325, 777, 1737, 3709, 7741, 15869, 32253, 32254, 96538, 225798, 485702, 1006338, 2049602, 4137346, 8315266, 16697102, 33465934, 67007886, 134100366, 268301518, 536720590, 1073575118, 2147316942, 2147316943, 6441886323 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

A binary carry of two positive integers is an overlap of the positions of 1's in their reversed binary expansion. A subset is binary carry-connected if the graph whose vertices are the elements and whose edges are binary carries is connected.

LINKS

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

FORMULA

a(n) = A306297(n,0) + A306297(n,1). - Alois P. Heinz, Mar 31 2019

EXAMPLE

The a(0) = 1 through a(4) = 8 subsets:

  {}  {}   {}   {}       {}

      {1}  {1}  {1}      {1}

           {2}  {2}      {2}

                {3}      {3}

                {1,3}    {4}

                {2,3}    {1,3}

                {1,2,3}  {2,3}

                         {1,2,3}

MAPLE

h:= proc(n, s) local i, m; m:= n;

      for i in s do m:= Bits[Or](m, i) od; {m}

    end:

g:= (n, s)-> (w-> `if`(w={}, s union {n}, s minus w union

              h(n, w)))(select(x-> Bits[And](n, x)>0, s)):

b:= proc(n, s) option remember; `if`(n=0,

      `if`(nops(s)>1, 0, 1), b(n-1, s)+b(n-1, g(n, s)))

    end:

a:= n-> b(n, {}):

seq(a(n), n=0..35);  # Alois P. Heinz, Mar 31 2019

MATHEMATICA

binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];

Table[Length[Select[Subsets[Range[n]], Length[csm[binpos/@#]]<=1&]], {n, 0, 10}]

CROSSREFS

Cf. A019565, A080572, A247935, A304714, A304716, A305078.

Cf. A325095, A325098, A325099, A325104, A325107, A325118, A325119.

Partial sums of A306299.

Sequence in context: A247843 A181658 A251541 * A276032 A114281 A137823

Adjacent sequences:  A325102 A325103 A325104 * A325106 A325107 A325108

KEYWORD

nonn

AUTHOR

Gus Wiseman, Mar 28 2019

EXTENSIONS

a(16)-a(33) from Alois P. Heinz, Mar 31 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 17:51 EDT 2021. Contains 345419 sequences. (Running on oeis4.)