A048715 - OEIS

%I #64 Jun 28 2024 23:06:47

%S 0,1,2,4,8,9,16,17,18,32,33,34,36,64,65,66,68,72,73,128,129,130,132,

%T 136,137,144,145,146,256,257,258,260,264,265,272,273,274,288,289,290,

%U 292,512,513,514,516,520,521,528,529,530,544,545,546,548,576,577,578,580

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

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

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

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

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

%C 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

%C 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

%H G. C. Greubel, <a href="/A048715/b048715.txt">Table of n, a(n) for n = 0..1275</a>

%H Sebastian Karlsson, <a href="/A048715/a048715.txt">Walnut code that verifies the conjectures of Paul D. Hanna</a>

%H Walnut can be downloaded from <a href="https://cs.uwaterloo.ca/~shallit/walnut.html">https://cs.uwaterloo.ca/~shallit/walnut.html</a>.

%H <a href="/index/Con#CongruCrossDomain">Index entries for sequences defined by congruent products between domains N and GF(2)[X]</a>

%H <a href="/index/Con#CongruXOR">Index entries for sequences defined by congruent products under XOR</a>

%H <a href="/index/Ar#2-automatic">Index entries for 2-automatic sequences</a>.

%F 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.

%F 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

%F The conjectures can be verified using the Walnut theorem-prover (see links). - _Sebastian Karlsson_, Dec 31 2022

%t Reap[Do[If[OddQ[Binomial[7n, n]], Sow[n]], {n, 0, 400}]][[2, 1]]

%t (* Second program: *)

%t filterQ[n_] := With[{bb = IntegerDigits[n, 2]}, !MatchQ[bb, {___, 1, 0, 1, ___}|{___, 1, 1, ___}]];

%t Select[Range[0, 580], filterQ] (* _Jean-François Alcover_, Dec 31 2020 *)

%o (PARI) is(n)=!bitand(n, 6*n) \\ _Charles R Greathouse IV_, Oct 03 2016

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

%o (Python)

%o import re

%o def ok(n): return re.fullmatch('(100(0)*)*(0|1|10)?', bin(n)[2:]) != None

%o print(list(filter(ok, range(581)))) # _Michael S. Branicky_, Jun 26 2021

%Y Subsequence of A048716.

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

%K nonn,base,easy

%O 0,3

%A _Antti Karttunen_, Mar 30 1999

%E Definition corrected by _Georg Fischer_, Jun 26 2021