|
|
A003714
|
|
Fibbinary numbers: if n = F(i1) + F(i2) + ... + F(ik) is the Zeckendorf representation of n (i.e., write n in Fibonacci number system) then a(n) = 2^(i1 - 2) + 2^(i2 - 2) + ... + 2^(ik - 2). Also numbers whose binary representation contains no two adjacent 1's.
|
|
208
|
|
|
0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20, 21, 32, 33, 34, 36, 37, 40, 41, 42, 64, 65, 66, 68, 69, 72, 73, 74, 80, 81, 82, 84, 85, 128, 129, 130, 132, 133, 136, 137, 138, 144, 145, 146, 148, 149, 160, 161, 162, 164, 165, 168, 169, 170, 256, 257, 258, 260, 261, 264
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
"... integers whose binary representation contains no consecutive ones and noticed that the number of such numbers with n bits was fibonacci(n)". [posting to sci.math by Bob Jenkins (bob_jenkins(AT)burtleburtle.net), Jul 17 2002]
A number m is in the sequence if and only if C(3m, m) (or equally, C(3m, 2m)) is odd.
Numbers m such that m XOR 2*m = 3*m. - Reinhard Zumkeller, May 03 2005. [This implies that A003188(2*a(n)) = 3*a(n) holds for all n.]
Numbers whose base-2 representation contains no two adjacent ones. For example, m = 17 = 10001_2 belongs to the sequence, but m = 19 = 10011_2 does not. - Ctibor O. Zizka, May 13 2008
m is in the sequence if and only if the central Stirling number of the second kind S(2*m, m) = A007820(m) is odd. - O-Yeat Chan (math(AT)oyeat.com), Sep 03 2009
Every nonnegative integer can be expressed as the sum of two terms of this sequence. - Franklin T. Adams-Watters, Jun 11 2011
The binary representation of each term m contains no two adjacent 1's, so we have (m XOR 2m XOR 3m) = 0, and thus a two-player Nim game with three heaps of (m, 2m, 3m) stones is a losing configuration for the first player. - V. Raman, Sep 17 2012
These numbers are similar to Fibternary numbers A003726, Tribbinary numbers A060140 and Tribternary numbers. This sequence is a subsequence of Fibternary numbers A003726. The number of Fibbinary numbers less than any power of two is a Fibonacci number. We can generate this sequence recursively: start with 0 and 1; then, if x is in the sequence add 2x and 4x+1 to the sequence. The Fibbinary numbers have the property that the n-th Fibbinary number is even if the n-th term of the Fibonacci word is a. Respectively, the n-th Fibbinary number is odd (of the form 4x+1) if the n-th term of the Fibonacci word is b. Every number has a Fibbinary multiple. - Tanya Khovanova and PRIMES STEP Senior, Aug 30 2022
This is the ordered set S of numbers defined recursively by: 0 is in S; if x is in S, then 2*x and 4*x + 1 are in S. See Kimberling (2006) Example 3, in references below. - Harry Richman, Jan 31 2024
|
|
REFERENCES
|
Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493.
|
|
LINKS
|
|
|
FORMULA
|
No two adjacent 1's in binary expansion.
Let f(x) := Sum_{n >= 0} x^Fibbinary(n). (This is the generating function of the characteristic function of this sequence.) Then f satisfies the functional equation f(x) = x*f(x^4) + f(x^2).
It appears that this sequence gives m such that A082759(3*m) is odd; or, probably equivalently, m such that A037011(3*m) = 1. - Benoit Cloitre, Jun 20 2003
If m is in the sequence then so are 2*m and 4*m + 1. - Henry Bottomley, Jan 11 2005
Sum_{n>=1} 1/a(n) = 3.704711752910469457886531055976801955909489488376627037756627135425780134020... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022
|
|
EXAMPLE
|
In the following, dots are used for zeros in the binary representation:
a(n) binary(a(n)) n
0: ....... 0
1: ......1 1
2: .....1. 2
4: ....1.. 3
5: ....1.1 4
8: ...1... 5
9: ...1..1 6
10: ...1.1. 7
16: ..1.... 8
17: ..1...1 9
18: ..1..1. 10
20: ..1.1.. 11
21: ..1.1.1 12
32: .1..... 13
33: .1....1 14
34: .1...1. 15
36: .1..1.. 16
37: .1..1.1 17
40: .1.1... 18
41: .1.1..1 19
42: .1.1.1. 20
64: 1...... 21
65: 1.....1 22
(End)
|
|
MAPLE
|
option remember;
if n < 3 then
n ;
else
end if;
end proc:
# To produce a table giving n, a(n) (base 10), a(n) (base 2) - from N. J. A. Sloane, Sep 30 2018
# binary: binary representation of n, in human order
binary:=proc(n) local t1, L;
if n<0 then ERROR("n must be nonnegative"); fi;
if n=0 then return([0]); fi;
t1:=convert(n, base, 2); L:=nops(t1);
[seq(t1[L+1-i], i=1..L)];
end;
for n from 0 to 100 do t1:=A003714(n); lprint(n, t1, binary(t1)); od:
|
|
MATHEMATICA
|
fibBin[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k--]; FromDigits[fr, 2]]; Table[fibBin[n], {n, 0, 61}] (* Robert G. Wilson v, Sep 18 2004 *)
Select[Range[0, 270], ! MemberQ[Partition[IntegerDigits[#, 2], 2, 1], {1, 1}] &] (* Harvey P. Dale, Jul 17 2011 *)
Select[Range[256], BitAnd[#, 2 #] == 0 &] (* Alonso del Arte, Jun 18 2012 *)
With[{r = Range[10^5]}, Pick[r, BitAnd[r, 2 r], 0]] (* Eric W. Weisstein, Aug 18 2017 *)
Select[Range[0, 299], SequenceCount[IntegerDigits[#, 2], {1, 1}] == 0 &] (* Requires Mathematica version 10 or later. -- Harvey P. Dale, Dec 06 2018 *)
|
|
PROG
|
(Haskell)
import Data.Set (Set, singleton, insert, deleteFindMin)
a003714 n = a003714_list !! n
a003714_list = 0 : f (singleton 1) where
f :: Set Integer -> [Integer]
f s = m : (f $ insert (4*m + 1) $ insert (2*m) s')
where (m, s') = deleteFindMin s
(PARI) msb(n)=my(k=1); while(k<=n, k<<=1); k>>1
for(n=1, 1e4, k=bitand(n, n<<1); if(k, n=bitor(n, msb(k)-1), print1(n", "))) \\ Charles R Greathouse IV, Jun 15 2011
(PARI) select( is_A003714(n)=!bitand(n, n>>1), [0..266])
{(next_A003714(n, t)=while(t=bitand(n+=1, n<<1), n=bitor(n, 1<<exponent(t)-1)); n); } t=0; vector(60, i, t=next_A003714(t)) \\ M. F. Hasler, Nov 30 2021
(Python)
for n in range(300):
if 2*n & n == 0:
(Python)
tlist, s = [1, 2], 0
while tlist[-1]+tlist[-2] <= n:
tlist.append(tlist[-1]+tlist[-2])
for d in tlist[::-1]:
s *= 2
if d <= n:
s += 1
n -= d
(Python)
def fibbinary():
x = 0
while True:
yield x
y = ~(x >> 1)
(C++)
/* start with x=0, then repeatedly call x=next_fibrep(x): */
ulong next_fibrep(ulong x)
{
// 2 examples: // ex. 1 // ex.2
// // x == [*]0 010101 // x == [*]0 01010
ulong y = x | (x>>1); // y == [*]? 011111 // y == [*]? 01111
ulong z = y + 1; // z == [*]? 100000 // z == [*]? 10000
z = z & -z; // z == [0]0 100000 // z == [0]0 10000
x ^= z; // x == [*]0 110101 // x == [*]0 11010
x &= ~(z-1); // x == [*]0 100000 // x == [*]0 10000
return x;
}
(Scala) (0 to 255).filter(n => (n & 2 * n) == 0) // Alonso del Arte, Apr 12 2020
(C#)
public static bool IsFibbinaryNum(this int n) => ((n & (n >> 1)) == 0) ? true : false; // Frank Hollstein, Jul 07 2021
|
|
CROSSREFS
|
Cf. A000045, A005203, A005590, A007895, A037011, A048728, A048679, A056017, A060112, A072649, A083368, A089939, A106027, A106028, A116361.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|