A048715 Binary expansion matches (100(0)*)*(0|1|10)?; or, Zeckendorf-like expansion of n using recurrence f(n) = f(n-1) + f(n-3).

0, 1, 2, 4, 8, 9, 16, 17, 18, 32, 33, 34, 36, 64, 65, 66, 68, 72, 73, 128, 129, 130, 132, 136, 137, 144, 145, 146, 256, 257, 258, 260, 264, 265, 272, 273, 274, 288, 289, 290, 292, 512, 513, 514, 516, 520, 521, 528, 529, 530, 544, 545, 546, 548, 576, 577, 578, 580

Offset: 0

Author

Antti Karttunen, Mar 30 1999

Keywords

• nonn
• base
• easy

Comments

No more than one 1-bit in each bit triple.

All terms satisfy A048727(n) = 7*n.

Constructed from A000930 in the same way as A003714 is constructed from A000045.

It appears that n is in the sequence if and only if C(7n,n) is odd (cf. A003714). - Benoit Cloitre, Mar 09 2003

The conjecture by Benoit is correct. This is easily proved using the well-known result that the multiplicity with which a prime p divides C(n+m,n) is the number of carries when adding n+m in base p. - Franklin T. Adams-Watters, Oct 06 2009

Appears to be the set of numbers x such that (x AND 5*x) = x and (x OR 3*x)/x = 3. - Gary Detlefs, Jun 08 2024

Links

• G. C. Greubel, Table of n, a(n) for n = 0..1275
• Sebastian Karlsson, Walnut code that verifies the conjectures of Paul D. Hanna
• Walnut can be downloaded from https://cs.uwaterloo.ca/~shallit/walnut.html.
• Index entries for sequences defined by congruent products between domains N and GF(2)[X]
• Index entries for sequences defined by congruent products under XOR
• Index entries for 2-automatic sequences.

Crossrefs

Subsequence of A048716.

Cf. A003726, A004742, A004743, A004744, A048717, A048718, A048719, A048730, A048733, A115422, A115423, A115424.

Programs

Mathematica

Reap[Do[If[OddQ[Binomial[7n, n]], Sow[n]], {n, 0, 400}]][[2, 1]]
(* Second program: *)
filterQ[n_] := With[{bb = IntegerDigits[n, 2]}, !MatchQ[bb, {_, 1, 0, 1, _}|{_, 1, 1, _}]];
Select[Range[0, 580], filterQ] (* Jean-François Alcover, Dec 31 2020 *)

PARI

is(n)=!bitand(n, 6*n) \\ Charles R Greathouse IV, Oct 03 2016

Perl

for my $k (0..580) { print "$k, " if sprintf("%b", $k) =~ m{^(100(0)*)*(0|1|10)?$}; } # Georg Fischer, Jun 26 2021

Python

import re
def ok(n): return re.fullmatch('(100(0)*)*(0|1|10)?', bin(n)[2:]) != None
print(list(filter(ok, range(581)))) # Michael S. Branicky, Jun 26 2021

Formula

a(0) = 0, a(n) = (2^(invfoo(n)-1))+a(n-foo(invfoo(n))), where foo(n) is foo(n-1) + foo(n-3) (A000930) and invfoo is its "integral" (floored down) inverse.

a(n) XOR 6*a(n) = 7*a(n); 3*a(n) XOR 4*a(n) = 7*a(n); 3*a(n) XOR 5*a(n) = 6*a(n); (conjectures). - Paul D. Hanna, Jan 22 2006

The conjectures can be verified using the Walnut theorem-prover (see links). - Sebastian Karlsson, Dec 31 2022

Extensions

Definition corrected by Georg Fischer, Jun 26 2021