login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A325095 Number of subsets of {1...n} with no binary carries. 13
1, 2, 4, 5, 10, 12, 14, 15, 30, 35, 40, 42, 47, 49, 51, 52, 104, 119, 134, 139, 154, 159, 164, 166, 181, 186, 191, 193, 198, 200, 202, 203, 406, 458, 510, 525, 577, 592, 607, 612, 664, 679, 694, 699, 714, 719, 724, 726, 778, 793, 808, 813, 828, 833, 838, 840 (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. For example, the binary representations of {2,5,8} are:
2 = 10,
5 = 101,
8 = 1000,
and since there are no columns with more than one 1, {2,5,8} is counted under a(8).
LINKS
FORMULA
a(2^n - 1) = A000110(n + 1).
EXAMPLE
The a(1) = 1 through a(7) = 15 subsets:
{} {} {} {} {} {} {}
{1} {1} {1} {1} {1} {1} {1}
{2} {2} {2} {2} {2} {2}
{1,2} {3} {3} {3} {3} {3}
{1,2} {4} {4} {4} {4}
{1,2} {5} {5} {5}
{1,4} {1,2} {6} {6}
{2,4} {1,4} {1,2} {7}
{3,4} {2,4} {1,4} {1,2}
{1,2,4} {2,5} {1,6} {1,4}
{3,4} {2,4} {1,6}
{1,2,4} {2,5} {2,4}
{3,4} {2,5}
{1,2,4} {3,4}
{1,2,4}
MAPLE
b:= proc(n, t) option remember; `if`(n=0, 1, b(n-1, t)+
`if`(Bits[And](n, t)=0, b(n-1, Bits[Or](n, t)), 0))
end:
a:= n-> b(n, 0):
seq(a(n), n=0..63); # Alois P. Heinz, Mar 28 2019
MATHEMATICA
binpos[n_]:=Join@@Position[Reverse[IntegerDigits[n, 2]], 1];
stableQ[u_, Q_]:=!Apply[Or, Outer[#1=!=#2&&Q[#1, #2]&, u, u, 1], {0, 1}];
Table[Length[Select[Subsets[Range[n]], stableQ[#, Intersection[binpos[#1], binpos[#2]]!={}&]&]], {n, 0, 10}]
CROSSREFS
Sequence in context: A241268 A285697 A047611 * A120491 A177186 A260385
KEYWORD
nonn,look
AUTHOR
Gus Wiseman, Mar 27 2019
EXTENSIONS
a(16)-a(55) from Alois P. Heinz, Mar 28 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 27 14:46 EST 2024. Contains 370376 sequences. (Running on oeis4.)