A004780 -id:A004780 - cp's OEIS frontend

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.

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

Offset: 0

N. J. A. Sloane

The name "Fibbinary" is due to Marc LeBrun.
"... 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]
From Benoit Cloitre, Mar 08 2003: (Start)
A number m is in the sequence if and only if C(3m, m) (or equally, C(3m, 2m)) is odd.
a(n) == A003849(n) (mod 2). (End)
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
A000120(3*a(n)) = 2*A000120(a(n)); A002450 is a subsequence.
Every nonnegative integer can be expressed as the sum of two terms of this sequence. - Franklin T. Adams-Watters, Jun 11 2011
Subsequence of A213526. - Arkadiusz Wesolowski, Jun 20 2012
This is also the union of A215024 and A215025 - see the Comment in A014417. - N. J. A. Sloane, Aug 10 2012
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
Positions of zeros in A014081. - John Keith, Mar 07 2022
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

			From _Joerg Arndt_, Jun 11 2011: (Start)
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)

Donald E. Knuth, The Art of Computer Programming: Fundamental Algorithms, Vol. 1, 2nd ed., Addison-Wesley, 1973, pp. 85, 493.

G. C. Greubel and T. D. Noe, Table of n, a(n) for n = 0..5000 (terms 0 to 1363 by T. D. Noe)
J.-P. Allouche, J. Shallit, and G. Skordev, Self-generating sets, integers with missing blocks and substitutions, Discrete Math., Vol. 292, No. 1-3 (2005), pp. 1-15.
Joerg Arndt, Matters Computational (The Fxtbook), pp. 74-77, pp. 754-756.
Robert Baillie and Thomas Schmelzer, Summing Kempner's Curious (Slowly-Convergent) Series, Mathematica Notebook kempnerSums.nb, Wolfram Library Archive, 2008.
Marc Chamberland and Karl Dilcher, A Binomial Sum Related to Wolstenholme's Theorem, J. Number Theory, Vol. 171, Issue 11 (Nov. 2009), pp. 2659-2672. See Lemma 4.2 p. 2668.
O-Yeat Chan and Dante Manna, Divisibility properties of Stirling numbers of the second kind.
F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
David Eppstein, Generating fibbinary numbers, three ways, 2021.
Clark Kimberling, Affinely recursive sets and orderings of languages, Discrete Math., Vol. 274, No. 1-3 (2004), pp. 147-160.
Roman S. Klyujkov, Quick Fibbinary Numbers Addition, C++ function with test program.
Ron Knott, Rabbit Sequence in Zeckendorf Expansion (A003714).
Linus Lindroos, Andrew Sills, and Hua Wang, Odd fibbinary numbers and the golden ratio, Fib. Q., Vol. 52, No. 1 (2014), pp. 61-65; alternative link.
A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 1, 5.
Douglas M. McKenna, Fibbinary Zippers in a Monoid of Toroidal Hamiltonian Cycles that Generate Hilbert-Style Square-Filling Curves, ECA 2:2 (2022) Article S2R13.
Joris Nieuwveld, Fractions, Functions and Folding. A Novel Link between Continued Fractions, Mahler Functions and Paper Folding, Master's Thesis, arXiv:2108.11382 [math.NT], 2021.
Yaron Shany and Amit Berman, The Generating Idempotent Is a Minimum-Weight Codeword for Some Binary BCH Codes, arXiv:2408.08218 [cs.IT], 2024. See p. 10.
N. J. A. Sloane, Table of n, a(n) (base 10), a(n) (base 2), for n = 0..1000.
Chai Wah Wu, Record values in appending and prepending bitstrings to runs of binary digits, arXiv:1810.02293 [math.NT], 2018.
Index entries for 2-automatic sequences.
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.

A007088(a(n)) = A014417(n) (same sequence in binary). Complement: A004780. Char. function: A085357. Even terms: A022340, odd terms: A022341. First difference: A129761.
Other sequences based on similar restrictions on binary expansion: A003726 & A278038, A003754, A048715, A048718, A107907, A107909.
Cf. A000045, A005203, A005590, A007895, A037011, A048728, A048679, A056017, A060112, A072649, A083368, A089939, A106027, A106028, A116361.
3*a(n) is in A001969.
Cf. also A215022-A215025, A242407.
Cf. A014081 (count 11 bits).

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
-- Reinhard Zumkeller, Jun 03 2012, Feb 07 2012

A003714 := proc(n)
    option remember;
    if n < 3 then
        n ;
    else
        2^(A072649(n)-1) + procname(n-combinat[fibonacci](1+A072649(n))) ;
    end if;
end proc:
seq(A003714(n),n=0..10) ;
# 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:

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 *)

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

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<A003714(t)) \\ M. F. Hasler, Nov 30 2021

for n in range(300):
    if 2*n & n == 0:
        print(n, end=",") # Alex Ratushnyak, Jun 21 2012

def A003714(n):
    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
    return s # Chai Wah Wu, Jun 14 2018

def fibbinary():
    x = 0
    while True:
        yield x
        y = ~(x >> 1)
        x = (x - y) & y # Falk Hüffner, Oct 23 2021
(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;
}
/* Joerg Arndt, Jun 22 2012 */

(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

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).
a(0) = 0, a(1) = 1, a(2) = 2, a(n) = 2^(A072649(n) - 1) + a(n - A000045(1 + A072649(n))). - Antti Karttunen
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
A116361(a(n)) <= 1. - Reinhard Zumkeller, Feb 04 2006
A085357(a(n)) = 1; A179821(a(n)) = a(n). - Reinhard Zumkeller, Jul 31 2010
a(n)/n^k is bounded (but does not tend to a limit), where k = 1.44... = A104287. - Charles R Greathouse IV, Sep 19 2012
a(n) = a(A193564(n+1))*2^(A003849(n) + 1) + A003849(n) for n > 0. - Daniel Starodubtsev, Aug 05 2021
There are Fibonacci(n+1) terms with up to n bits in this sequence. - Charles R Greathouse IV, Oct 22 2021
Sum_{n>=1} 1/a(n) = 3.704711752910469457886531055976801955909489488376627037756627135425780134020... (calculated using Baillie and Schmelzer's kempnerSums.nb, see Links). - Amiram Eldar, Feb 12 2022

Edited by Antti Karttunen, Feb 21 2006
Cross reference to A007820 added (into O-Y.C. comment) by Jason Kimberley, Sep 14 2009
Typo corrected by Jeffrey Shallit, Sep 26 2014

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 67, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Sep 02 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The terms, binary expansions, and standard compositions:
   1:       1  (1)
   3:      11  (1,1)
   5:     101  (2,1)
   6:     110  (1,2)
   7:     111  (1,1,1)
   9:    1001  (3,1)
  11:    1011  (2,1,1)
  12:    1100  (1,3)
  13:    1101  (1,2,1)
  14:    1110  (1,1,2)
  15:    1111  (1,1,1,1)
  17:   10001  (4,1)
  19:   10011  (3,1,1)
  21:   10101  (2,2,1)
  22:   10110  (2,1,2)
  23:   10111  (2,1,1,1)
  24:   11000  (1,4)
  25:   11001  (1,3,1)
  26:   11010  (1,2,2)
  27:   11011  (1,2,1,1)
  28:   11100  (1,1,3)
  29:   11101  (1,1,2,1)
  30:   11110  (1,1,1,2)
  31:   11111  (1,1,1,1,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
The case beginning with 1 is A004760, complement A004754.
The complement is A022340.
These compositions are counted by A099036, complement A212804.
The case covering an initial interval is A333217.
The gapless but non-initial version is A356843, unordered A356845.
Cf. A004780, A005408, A055932, A073492, A073493, A132747.

Select[Range[0,100],OddQ[#]||MatchQ[IntegerDigits[#,2],{_,1,1,_}]&]

Union of A005408 and A004780.

A175466 Table read by antidiagonals: a(m,n) = the largest positive integer occurring, when written in binary, as a substring in both binary m and binary n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 4, 1, 2, 1, 1, 1, 3, 2, 2, 3, 1, 1, 1, 2, 3, 2, 5, 2, 3, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 4, 1, 6, 1, 4, 1, 2, 1, 1, 2, 1, 4, 2, 3, 3, 2, 4, 1, 2, 1, 1, 2, 3, 2, 2, 2, 7, 2, 2

Offset: 1

Leroy Quet, May 24 2010

			From _Rémy Sigrist_, Jul 20 2019: (Start)
Table a(n, k) begins (in decimal):
  n\k|  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15
  ---+---------------------------------------------------
    1|  1  1  1  1  1  1  1  1  1   1   1   1   1   1   1
    2|  1  2  1  2  2  2  1  2  2   2   2   2   2   2   1
    3|  1  1  3  1  1  3  3  1  1   1   3   3   3   3   3
    4|  1  2  1  4  2  2  1  4  4   2   2   4   2   2   1
    5|  1  2  1  2  5  2  1  2  2   5   5   2   5   2   1
    6|  1  2  3  2  2  6  3  2  2   2   3   6   6   6   3
    7|  1  1  3  1  1  3  7  1  1   1   3   3   3   7   7
    8|  1  2  1  4  2  2  1  8  4   2   2   4   2   2   1
    9|  1  2  1  4  2  2  1  4  9   2   2   4   2   2   1
   10|  1  2  1  2  5  2  1  2  2  10   5   2   5   2   1
   11|  1  2  3  2  5  3  3  2  2   5  11   3   5   3   3
   12|  1  2  3  4  2  6  3  4  4   2   3  12   6   6   3
   13|  1  2  3  2  5  6  3  2  2   5   5   6  13   6   3
   14|  1  2  3  2  2  6  7  2  2   2   3   6   6  14   7
   15|  1  1  3  1  1  3  7  1  1   1   3   3   3   7  15
Table a(n, k) begins (in binary):
   n\k| 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111
  ----+----------------------------------------------------------------
     1| 1  1  1   1   1   1   1    1    1    1    1    1    1    1    1
    10| 1 10  1  10  10  10   1   10   10   10   10   10   10   10    1
    11| 1  1 11   1   1  11  11    1    1    1   11   11   11   11   11
   100| 1 10  1 100  10  10   1  100  100   10   10  100   10   10    1
   101| 1 10  1  10 101  10   1   10   10  101  101   10  101   10    1
   110| 1 10 11  10  10 110  11   10   10   10   11  110  110  110   11
   111| 1  1 11   1   1  11 111    1    1    1   11   11   11  111  111
  1000| 1 10  1 100  10  10   1 1000  100   10   10  100   10   10    1
  1001| 1 10  1 100  10  10   1  100 1001   10   10  100   10   10    1
  1010| 1 10  1  10 101  10   1   10   10 1010  101   10  101   10    1
  1011| 1 10 11  10 101  11  11   10   10  101 1011   11  101   11   11
  1100| 1 10 11 100  10 110  11  100  100   10   11 1100  110  110   11
  1101| 1 10 11  10 101 110  11   10   10  101  101  110 1101  110   11
  1110| 1 10 11  10  10 110 111   10   10   10   11  110  110 1110  111
  1111| 1  1 11   1   1  11 111    1    1    1   11   11   11  111 1111
(End)

Rémy Sigrist, Table of n, a(n) for n = 1..11325
Rémy Sigrist, Colored representation of the table for n = 1..1023 and k = 1023

Cf. A043529, A004780, A175488.

sub(n) = { my (b=binary(n), s=[]); for (i=1, #b, if (b[i], for (j=i, #b, s=setunion(s, Set(fromdigits(b[i..j], 2)))))); return (s) }
T(n,k) = my (i=setintersect(sub(n), sub(k))); i[#i] \\ Rémy Sigrist, Jul 20 2019

From Rémy Sigrist, Jul 20 2019: (Start)
1 <= a(n, k) <= min(n, k).
a(n, k) = a(k, n).
a(n, n) = n.
a(n, 1) = 1.
a(n, 2) = A043529(n).
a(n, 3) = 3 iff n belongs to A004780. (End)

More terms from Rémy Sigrist, Jul 20 2019

A090077 In binary expansion of n: reduce contiguous blocks of 1's to 1.

Original entry on oeis.org

0, 1, 2, 1, 4, 5, 2, 1, 8, 9, 10, 5, 4, 5, 2, 1, 16, 17, 18, 9, 20, 21, 10, 5, 8, 9, 10, 5, 4, 5, 2, 1, 32, 33, 34, 17, 36, 37, 18, 9, 40, 41, 42, 21, 20, 21, 10, 5, 16, 17, 18, 9, 20, 21, 10, 5, 8, 9, 10, 5, 4, 5, 2, 1, 64, 65, 66, 33, 68, 69, 34, 17, 72, 73, 74, 37, 36, 37, 18, 9

Offset: 0

Reinhard Zumkeller, Nov 20 2003

			100 -> '1100100' -> [11]00[1]00 -> [1]00[1]00 -> '100100' -> 36=a(100).

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Index entries for sequences related to binary expansion of n

Cf. A007088, A090079, A090078, A348710.

Array[FromDigits[Flatten[Split@ IntegerDigits[#, 2] /. w_List /; First[w] == 1 -> {1}], 2] &, 80, 0] (* Michael De Vlieger, Jul 28 2022 *)

def a(n):
    b = bin(n)[2:]
    while "11" in b: b = b.replace("11", "1")
    return int(b, 2)
print([a(n) for n in range(81)]) # Michael S. Branicky, Jul 27 2022

a(a(n)) = a(n); a(A090078(n)) = A090078(a(n)) = A090079(n).

a(A003714(n)) = A003714(n); a(A004780(n)) < A004780(n); a(n) <= A179821(n); A085357(a(n)) = 1. - Reinhard Zumkeller, Jul 31 2010

A261891 Least k>0 such that n AND (k*n) = 0, where AND stands for the binary AND operator.

Original entry on oeis.org

2, 2, 4, 2, 2, 4, 8, 2, 2, 2, 12, 4, 10, 8, 16, 2, 2, 2, 4, 2, 2, 12, 24, 4, 4, 10, 12, 8, 10, 16, 32, 2, 2, 2, 4, 2, 2, 4, 40, 2, 2, 2, 12, 12, 10, 24, 48, 4, 4, 4, 4, 10, 34, 12, 56, 8, 18, 10, 12, 16, 42, 32, 64, 2, 2, 2, 4, 2, 2, 4, 8, 2, 2, 2, 12, 4, 10

Offset: 1

Paul Tek, Sep 05 2015

All terms are even.
a(A003714(n)) = 2 for any n>0.
a(A004780(n)) > 2 for any n>0.
a(n) <= 2^A116361(n) for any n>0.
a(2n) = a(n) for any n>0.

			For n=7:
+---+-------------+
| k | 7 AND (k*7) |
|   | (in binary) |
+---+-------------+
| 1 |         111 |
| 2 |         110 |
| 3 |         101 |
| 4 |         100 |
| 5 |          11 |
| 6 |          10 |
| 7 |           1 |
| 8 |           0 |
+---+-------------+
Hence, a(7) = 8.

Paul Tek, Table of n, a(n) for n = 1..16384

Cf. A003714, A004780, A116361, A261892.

Table[k = 1; While[BitAnd[k n, n] != 0, k++]; k, {n, 60}] (* Michael De Vlieger, Sep 06 2015 *)

a(n) = {k=1; while (bitand(n, k*n), k++); k;} \\ Michel Marcus, Sep 06 2015

sub a {
   my $n = shift;
   my $k = 1;
   while ($n & ($k*$n)) {
      $k++;
   }
   return $k;
}

from itertools import count
def A261891(n): return next(k for k in count(2) if not n&k*n) # Chai Wah Wu, Jul 19 2024

A377232 Odd numbers with binary representations corresponding to winning positions in Gordon Hamilton's Jumping Frogs game.

Original entry on oeis.org

1, 3, 7, 11, 13, 15, 23, 27, 29, 31, 39, 47, 55, 57, 59, 61, 63, 75, 79, 95, 103, 105, 107, 111, 115, 119, 121, 123, 125, 127, 143, 155, 159, 183, 191, 203, 207, 211, 215, 217, 219, 223, 231, 235, 237, 239, 241, 243, 247, 249, 251, 253, 255

Offset: 1

Glen Whitney, Oct 21 2024

A position in the jumping frogs game is a finite sequence P of nonnegative integers. If P_i = k ("lily pad i has k frogs"), and P_{i+k} > 0 ("lily pad i+k has at least one frog"), then it is legal to move to position Q where Q_i = 0, Q_{i+k} = P_{i+k} + k, and all other Q_j = P_j ("k frogs may together jump k places"). Similarly, if P_{i-k} > 0 then it is legal to move to Q' where Q'i = 0, Q'{i-k} = P_{i-k} + k, and Q'_j = P_j for all other j. These are the only legal moves. A position is considered "winning" if there is a sequence of legal moves leading to a position with only one nonzero entry ("the frogs want to all party together"). Any number represents a position with at most one frog per lily pad via its binary representation considered as a sequence of ones and zeros. We only consider odd numbers in this sequence to keep the positions distinct; trailing zeros in a sequence can never be used or affect whether it is winning or not winning.
Every number of the form 2^k - 1 is a term: As shown in the Hamilton reference, the position consisting of k consecutive frogs can be won by starting in the middle and jumping 1, 2, ..., k-1 places outward, alternating left and right.
The example below for i=5 generalizes to show that every term (except the first) must be a term of A004780, i.e., have two consecutive ones in its binary representation.
Since arbitrary nonnegative numbers are allowed in positions of the jumping frogs game, one could generate an analogous sequence for any base b by interpreting a number as its sequence of digits in base b, and including only those numbers corresponding to winning positions with no trailing zeros.
An odd number k is a term if and only if A030101(k) (the binary reversal of k) is a term. - Pontus von Brömssen, Oct 23 2024

			Consider i = 5 with binary representation 101. There are no legal moves from the position 1,0,1 (since no "frog" is adjacent to another one, and single frogs may only jump one place). Therefore 5 is not a term.
Conversely, consider i = 11 with binary representation 1011. From 1, 0, 1, 1, it is legal to move to 1, 0, 2, 0, and then to 3, 0, 0, 0, with only one nonzero entry. Therefore, 1, 0, 1, 1 is a winning position, and 11 does appear as a(4).
The Numberphile video (see the Links) mentions a then-open problem as to whether any number of the form 2^k - 2^{k-2} - 2 - 1 (corresponding to a single frog, an empty place, k-4 consecutive frogs, an empty place, and then a final lone frog) is a term. In fact, 3069 corresponding to k=12 appears (as a(371), and no smaller number of this form occurs, although many larger ones do):
  1 0 1 1 1 1 1 1 1 1 0 1
  1 0 1 1 1 1 1 1 0 2 0 1
  1 0 1 1 1 1 1 1 0 0 0 3
  1 0 1 1 1 1 2 0 0 0 0 3
  1 0 1 0 2 1 2 0 0 0 0 3
  1 0 1 0 4 1 0 0 0 0 0 3
  5 0 1 0 0 1 0 0 0 0 0 3
  0 0 1 0 0 6 0 0 0 0 0 3
  0 0 1 0 0 0 0 0 0 0 0 9
  0 0 X 0 0 0 0 0 0 0 0 0

Gordon Hamilton, The Infinite Pickle, Our Street Books, 2024, pp. 77-114.

Glen Whitney, Table of n, a(n) for n = 1..10000
Gordon Hamilton, Jumping Frogs, Math Pickle, 2017.
Gordon Hamilton and Brady Haran, Frog Jumping, Numberphile video, 2017.
Glen Whitney, Python code to generate b-file

Except for a(1), subsequence of A004780.

Cf. A030101.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Python

Scala

Formula

Extensions

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A175466 Table read by antidiagonals: a(m,n) = the largest positive integer occurring, when written in binary, as a substring in both binary m and binary n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A090077 In binary expansion of n: reduce contiguous blocks of 1's to 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A261891 Least k>0 such that n AND (k*n) = 0, where AND stands for the binary AND operator.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Python

A377232 Odd numbers with binary representations corresponding to winning positions in Gordon Hamilton's Jumping Frogs game.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A179821 In binary representation of n: replace all blocks of k contiguous ones with binary representation of k.

Views

Author