cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 47 results. Next

A319952 Let M = A022342(n) be the n-th number whose Zeckendorf representation is even; then a(n) = A129761(M).

Original entry on oeis.org

1, 2, 3, 1, 6, 1, 2, 11, 1, 2, 3, 1, 22, 1, 2, 3, 1, 6, 1, 2, 43, 1, 2, 3, 1, 6, 1, 2, 11, 1, 2, 3, 1, 86, 1, 2, 3, 1, 6, 1, 2, 11, 1, 2, 3, 1, 22, 1, 2, 3, 1, 6, 1, 2, 171, 1, 2, 3, 1, 6, 1, 2, 11, 1, 2, 3, 1, 22, 1, 2, 3, 1, 6, 1
Offset: 2

Views

Author

Jeffrey Shallit and N. J. A. Sloane, Oct 03 2018

Keywords

Comments

The Zeckendorf representations of numbers are given in A014417. The even ones are specified by A022342.
The offset here is 2 (because A129761 should really have had offset 1 not 0).

Crossrefs

Cf. A003714, A014417, A022342, A072649, A129761, A130234.

Programs

  • Maple
    with(combinat): F:=fibonacci:
A130234 := proc(n)
    local i;
    for i from 0 do
        if F(i) >= n then
            return i;
        end if;
    end do:
end proc:
A014417 := proc(n)
    local nshi, Z, i ;
    if n <= 1 then
        return n;
    end if;
    nshi := n ;
    Z := [] ;
    for i from A130234(n) to 2 by -1 do
        if nshi >= F(i) and nshi > 0 then
            Z := [1, op(Z)] ;
            nshi := nshi-F(i) ;
        else
            Z := [0, op(Z)] ;
        end if;
    end do:
    add( op(i, Z)*10^(i-1), i=1..nops(Z)) ;
end proc:
A072649:= proc(n) local j; global F; for j from ilog[(1+sqrt(5))/2](n)
       while F(j+1)<=n do od; (j-1); end proc:
A003714 := proc(n) global F; option remember; if(n < 3) then RETURN(n); else RETURN((2^(A072649(n)-1))+A003714(n-F(1+A072649(n)))); fi; end proc:
A129761 := n -> A003714(n+1)-A003714(n):
a:=[];
for n from 1 to 120 do
   if (A014417(n) mod 2) = 0 then a:=[op(a), A129761(n-1)]; fi;
od;
a;

Formula

If the Zeckendorf representation of M ends with exactly k zeros, ...10^k, then a(n) = ceiling(2^k/3).

A066093 Duplicate of A022342.

Original entry on oeis.org

0, 2, 3, 5, 7, 8, 10, 11, 13, 15, 16, 18, 20, 21, 23, 24, 26, 28, 29, 31, 32, 34, 36, 37, 39
Offset: 0

Views

Author

Keywords

A000201 Lower Wythoff sequence (a Beatty sequence): a(n) = floor(n*phi), where phi = (1+sqrt(5))/2 = A001622.

Original entry on oeis.org

1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 33, 35, 37, 38, 40, 42, 43, 45, 46, 48, 50, 51, 53, 55, 56, 58, 59, 61, 63, 64, 66, 67, 69, 71, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90, 92, 93, 95, 97, 98, 100, 101, 103, 105, 106, 108, 110
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

This is the unique sequence a satisfying a'(n)=a(a(n))+1 for all n in the set N of natural numbers, where a' denotes the ordered complement (in N) of a. - Clark Kimberling, Feb 17 2003
This sequence and A001950 may be defined as follows. Consider the maps a -> ab, b -> a, starting from a(1) = a; then A000201 gives the indices of a, A001950 gives the indices of b. The sequence of letters in the infinite word begins a, b, a, a, b, a, b, a, a, b, a, ... Setting a = 0, b = 1 gives A003849 (offset 0); setting a = 1, b = 0 gives A005614 (offset 0). - Philippe Deléham, Feb 20 2004
These are the numbers whose lazy Fibonacci representation (see A095791) includes 1; the complementary sequence (the upper Wythoff sequence, A001950) are the numbers whose lazy Fibonacci representation includes 2 but not 1.
a(n) is the unique monotonic sequence satisfying a(1)=1 and the condition "if n is in the sequence then n+(rank of n) is not in the sequence" (e.g. a(4)=6 so 6+4=10 and 10 is not in the sequence) - Benoit Cloitre, Mar 31 2006
Write A for A000201 and B for A001950 (the upper Wythoff sequence, complement of A). Then the composite sequences AA, AB, BA, BB, AAA, AAB,...,BBB,... appear in many complementary equations having solution A000201 (or equivalently, A001950). Typical complementary equations: AB=A+B (=A003623), BB=A+2B (=A101864), BBB=3A+5B (=A134864). - Clark Kimberling, Nov 14 2007
Cumulative sum of A001468 terms. - Eric Angelini, Aug 19 2008
The lower Wythoff sequence also can be constructed by playing the so-called Mancala-game: n piles of total d(n) chips are standing in a row. The piles are numbered from left to right by 1, 2, 3, ... . The number of chips in a pile at the beginning of the game is equal to the number of the pile. One step of the game is described as follows: Distribute the pile on the very left one by one to the piles right of it. If chips are remaining, build piles out of one chip subsequently to the right. After f(n) steps the game ends in a constant row of piles. The lower Wythoff sequence is also given by n -> f(n). - Roland Schroeder (florola(AT)gmx.de), Jun 19 2010
With the exception of the first term, a(n) gives the number of iterations required to reverse the list {1,2,3,...,n} when using the mapping defined as follows: remove the first term of the list, z(1), and add 1 to each of the next z(1) terms (appending 1's if necessary) to get a new list. See A183110 where this mapping is used and other references given. This appears to be essentially the Mancala-type game interpretation given by R. Schroeder above. - John W. Layman, Feb 03 2011
Also row numbers of A213676 starting with an even number of zeros. - Reinhard Zumkeller, Mar 10 2013
From Jianing Song, Aug 18 2022: (Start)
Numbers k such that {k*phi} > phi^(-2), where {} denotes the fractional part.
Proof: Write m = floor(k*phi).
If {k*phi} > phi^(-2), take s = m-k+1. From m < k*phi < m+1 we have k < (m-k+1)*phi < k + phi, so floor(s*phi) = k or k+1. If floor(s*phi) = k+1, then (see A003622) floor((k+1)*phi) = floor(floor(s*phi)*phi) = floor(s*phi^2)-1 = s+floor(s*phi)-1 = m+1, but actually we have (k+1)*phi > m+phi+phi^(-2) = m+2, a contradiction. Hence floor(s*phi) = k.
If floor(s*phi) = k, suppose otherwise that k*phi - m <= phi^(-2), then m < (k+1)*phi <= m+2, so floor((k+1)*phi) = m+1. Suppose that A035513(p,q) = k for p,q >= 1, then A035513(p,q+1) = floor((k+1)*phi) - 1 = m = A035513(s,1). But it is impossible for one number (m) to occur twice in A035513. (End)
The formula from Jianing Song above is a direct consequence of an old result by Carlitz et al. (1972). Their Theorem 11 states that (a(n)) consists of the numbers k such that {k*phi^(-2)} < phi^(-1). One has {k*phi^(-2)} = {k*(2-phi)} = {-k*phi}. Using that 1-phi^(-1) = phi^(-2), the Jianing Song formula follows. - Michel Dekking, Oct 14 2023
In the Fokkink-Joshi paper, this sequence is the Cloitre (1,1,2,1)-hiccup sequence, i.e., a(1) = 1; for m < n, a(n) = a(n-1)+2 if a(m) = n-1, else a(n) = a(n-1)+1. - Michael De Vlieger, Jul 28 2025

Examples

			From Roland Schroeder (florola(AT)gmx.de), Jul 13 2010: (Start)
Example for n = 5; a(5) = 8;
(Start: [1,2,3,4,5]; 8 steps until [5,4,3,2,1]):
[1,2,3,4,5]; [3,3,4,5]; [4,5,6]; [6,7,1,1]; [8,2,2,1,1,1]: [3,3,2,2,2,1,1,1]; [4,3,3,2,1,1,1]; [4,4,3,2,1,1]; [5,4,3,2,1]. (End)

References

  • Eric Friedman, Scott M. Garrabrant, Ilona K. Phipps-Morgan, A. S. Landsberg and Urban Larsson, Geometric analysis of a generalized Wythoff game, in Games of no Chance 5, MSRI publ. Cambridge University Press, date?
  • M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman, 1989; see p. 107.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • I. M. Yaglom, Two games with matchsticks, pp. 1-7 of Qvant Selecta: Combinatorics I, Amer Math. Soc., 2001.

Links

Crossrefs

a(n) = least k such that s(k) = n, where s = A026242. Complement of A001950. See also A058066.
The permutation A002251 maps between this sequence and A001950, in that A002251(a(n)) = A001950(n), A002251(A001950(n)) = a(n).
First differences give A014675. a(n) = A022342(n) + 1 = A005206(n) + n + 1. a(2n)-a(n)=A007067(n). a(a(a(n)))-a(n) = A026274(n-1). - Benoit Cloitre, Mar 08 2003
A185615 gives values n such that n divides A000201(n)^m for some integer m>0.
Cf. A183110, A329825.
Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021
Bisections: A276854, A342279.

Programs

  • Haskell
    a000201 n = a000201_list !! (n-1)
a000201_list = f [1..] [1..] where
   f (x:xs) (y:ys) = y : f xs (delete (x + y) ys)
-- Reinhard Zumkeller, Jul 02 2015, Mar 10 2013
  • Maple
    Digits := 100; t := evalf((1+sqrt(5))/2); A000201 := n->floor(t*n);
  • Mathematica
    Table[Floor[N[n*(1+Sqrt[5])/2]], {n, 1, 75}]
Array[ Floor[ #*GoldenRatio] &, 68] (* Robert G. Wilson v, Apr 17 2010 *)
  • Maxima
    makelist(floor(n*(1+sqrt(5))/2),n,1,60); /* Martin Ettl, Oct 17 2012 */
  • PARI
    a(n)=floor(n*(sqrt(5)+1)/2)
  • PARI
    a(n)=(n+sqrtint(5*n^2))\2 \\ Charles R Greathouse IV, Feb 07 2013
  • Python
    def aupton(terms):
  alst, aset = [None, 1], {1}
  for n in range(1, terms):
    an = alst[n] + (1 if n not in aset else 2)
    alst.append(an); aset.add(an)
  return alst[1:]
print(aupton(68)) # Michael S. Branicky, May 14 2021
  • Python
    from math import isqrt
def A000201(n): return (n+isqrt(5*n**2))//2 # Chai Wah Wu, Jan 11 2022

Formula

Zeckendorf expansion of n (cf. A035517) ends with an even number of 0's.
Other properties: a(1)=1; for n>1, a(n) is taken to be the smallest integer greater than a(n-1) which is consistent with the condition "n is in the sequence if and only if a(n)+1 is not in the sequence".
a(1) = 1; for n>0, a(n+1) = a(n)+1 if n is not in the sequence, a(n+1) = a(n)+2 if n is in the sequence.
a(a(n)) = floor(n*phi^2) - 1 = A003622(n).
{a(k)} union {a(k)+1} = {1, 2, 3, 4, ...}. Hence a(1) = 1; for n>1, a(a(n)) = a(a(n)-1)+2, a(a(n)+1) = a(a(n))+1. - Benoit Cloitre, Mar 08 2003
{a(n)} is a solution to the recurrence a(a(n)+n) = 2*a(n)+n, a(1)=1 (see Barbeau et al.).
a(n) = A001950(n) - n. - Philippe Deléham, May 02 2004
a(0) = 0; a(n) = n + Max_{k : a(k) < n}. - Vladeta Jovovic, Jun 11 2004
a(Fibonacci(r-1)+j) = Fibonacci(r)+a(j) for 0 < j <= Fibonacci(r-2); 2 < r. - Paul Weisenhorn, Aug 18 2012
With 1 < k and A001950(k-1) < n <= A001950(k): a(n) = 2*n-k; A001950(n) = 3*n-k. - Paul Weisenhorn, Aug 21 2012

A001950 Upper Wythoff sequence (a Beatty sequence): a(n) = floor(n*phi^2), where phi = (1+sqrt(5))/2.

Original entry on oeis.org

2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, 49, 52, 54, 57, 60, 62, 65, 68, 70, 73, 75, 78, 81, 83, 86, 89, 91, 94, 96, 99, 102, 104, 107, 109, 112, 115, 117, 120, 123, 125, 128, 130, 133, 136, 138, 141, 143, 146, 149, 151, 154, 157
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Indices at which blocks (1;0) occur in infinite Fibonacci word; i.e., n such that A005614(n-2) = 0 and A005614(n-1) = 1. - Benoit Cloitre, Nov 15 2003
A000201 and this sequence may be defined as follows: Consider the maps a -> ab, b -> a, starting from a(1) = a; then A000201 gives the indices of a, A001950 gives the indices of b. The sequence of letters in the infinite word begins a, b, a, a, b, a, b, a, a, b, a, ... Setting a = 0, b = 1 gives A003849 (offset 0); setting a = 1, b = 0 gives A005614 (offset 0). - Philippe Deléham, Feb 20 2004
a(n) = n-th integer which is not equal to the floor of any multiple of phi, where phi = (1+sqrt(5))/2 = golden number. - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), May 09 2007
Write A for A000201 and B for the present sequence (the upper Wythoff sequence, complement of A). Then the composite sequences AA, AB, BA, BB, AAA, AAB, ..., BBB, ... appear in many complementary equations having solution A000201 (or equivalently, the present sequence). Typical complementary equations: AB=A+B (=A003623), BB=A+2B (=A101864), BBB=3A+5B (=A134864). - Clark Kimberling, Nov 14 2007
Apart from the initial 0 in A090909, is this the same as that sequence? - Alec Mihailovs (alec(AT)mihailovs.com), Jul 23 2007
If we define a base-phi integer as a positive number whose representation in the golden ratio base consists only of nonnegative powers of phi, and if these base-phi integers are ordered in increasing order (beginning 1, phi, ...), then it appears that the difference between the n-th and (n-1)-th base-phi integer is phi-1 if and only if n belongs to this sequence, and the difference is 1 otherwise. Further, if each base-phi integer is written in linear form as a + b*phi (for example, phi^2 is written as 1 + phi), then it appears that there are exactly two base-phi integers with b=n if and only if n belongs to this sequence, and exactly three base-phi integers with b=n otherwise. - Geoffrey Caveney, Apr 17 2014
Numbers with an odd number of trailing zeros in their Zeckendorf representation (A014417). - Amiram Eldar, Feb 26 2021
Numbers missing from A066096. - Philippe Deléham, Jan 19 2023

Examples

			From _Paul Weisenhorn_, Aug 18 2012 and Aug 21 2012: (Start)
a(14) = floor(14*phi^2) = 36; a'(14) = floor(14*phi)=22;
with r=9 and j=1: a(13+1) = 34 + 2 = 36;
with r=8 and j=1: a'(13+1) = 21 + 1 = 22.
k=6 and a(5)=13 < n <= a(6)=15
a(14) = 3*14 - 6 = 36; a'(14) = 2*14 - 6 = 22;
a(15) = 3*15 - 6 = 39; a'(15) = 2*15 - 6 = 24. (End)

References

  • Claude Berge, Graphs and Hypergraphs, North-Holland, 1973; p. 324, Problem 2.
  • Eric Friedman, Scott M. Garrabrant, Ilona K. Phipps-Morgan, A. S. Landsberg and Urban Larsson, Geometric analysis of a generalized Wythoff game, in Games of no Chance 5, MSRI publ. Cambridge University Press, 2019.
  • Martin Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman, 1989; see p. 107.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • I. M. Yaglom, Two games with matchsticks, pp. 1-7 of Qvant Selecta: Combinatorics I, Amer Math. Soc., 2001.

Links

Crossrefs

a(n) = greatest k such that s(k) = n, where s = A026242.
Complement of A000201 or A066096.
A002251 maps between A000201 and A001950, in that A002251(A000201(n)) = A001950(n), A002251(A001950(n)) = A000201(n).
Cf. A001622, A026352, A004976, A004919.
Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864.
First differences give (essentially) A076662.
Bisections: A001962, A001966.
Cf. A014417, A329825.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

Programs

  • Haskell
    a001950 n = a000201 n + n  -- Reinhard Zumkeller, Mar 10 2013
  • Magma
    [Floor(n*((1+Sqrt(5))/2)^2): n in [1..80]]; // Vincenzo Librandi, Nov 19 2016
  • Maple
    A001950 := proc(n)
    floor(n*(3+sqrt(5))/2) ;
end proc:
seq(A001950(n),n=0..40) ; # R. J. Mathar, Jul 16 2024
  • Mathematica
    Table[Floor[N[n*(1+Sqrt[5])^2/4]], {n, 1, 75}]
Array[ Floor[ #*GoldenRatio^2] &, 60] (* Robert G. Wilson v, Apr 17 2010 *)
  • PARI
    a(n)=floor(n*(sqrt(5)+3)/2)
  • PARI
    A001950(n)=(sqrtint(n^2*5)+n*3)\2 \\ M. F. Hasler, Sep 17 2014
  • Python
    from math import isqrt
def A001950(n): return (n+isqrt(5*n**2)>>1)+n # Chai Wah Wu, Aug 10 2022

Formula

a(n) = n + floor(n*phi). In general, floor(n*phi^m) = Fibonacci(m-1)*n + floor(Fibonacci(m)*n*phi). - Benoit Cloitre, Mar 18 2003
a(n) = n + floor(n*phi) = n + A000201(n). - Paul Weisenhorn and Philippe Deléham
Append a 0 to the Zeckendorf expansion (cf. A035517) of n-th term of A000201.
a(n) = A003622(n) + 1. - Philippe Deléham, Apr 30 2004
a(n) = Min(m: A134409(m) = A006336(n)). - Reinhard Zumkeller, Oct 24 2007
If a'=A000201 is the ordered complement (in N) of {a(n)}, then a(Fib(r-2) + j) = Fib(r) + a(j) for 0 < j <= Fib(r-2), 3 < r; and a'(Fib(r-1) + j) = Fib(r) + a'(j) for 0 < j <= Fib(r-2), 2 < r. - Paul Weisenhorn, Aug 18 2012
With a(1)=2, a(2)=5, a'(1)=1, a'(2)=3 and 1 < k and a(k-1) < n <= a(k) one gets a(n)=3*n-k, a'(n)=2*n-k. - Paul Weisenhorn, Aug 21 2012

Extensions

Corrected by Michael Somos, Jun 07 2000

A003849 The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).

Original entry on oeis.org

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A Sturmian word.
Define strings S(0)=0, S(1)=01, S(n)=S(n-1)S(n-2); iterate; sequence is S(infinity). If the initial 0 is omitted from S(n) for n>0, we obtain A288582(n+1).
The 0's occur at positions in A022342 (i.e., A000201 - 1), the 1's at positions in A003622.
Replace each run (1;1) with (1;0) in the infinite Fibonacci word A005614 (and add 0 as prefix) A005614 begins: 1,0,1,1,0,1,0,1,1,0,1,1,... changing runs (1,1) with (1,0) produces 1,0,0,1,0,1,0,0,1,0,0,1,... - Benoit Cloitre, Nov 10 2003
Characteristic function of A003622. - Philippe Deléham, May 03 2004
The fraction of 0's in the first n terms approaches 1/phi (see for example Allouche and Shallit). - N. J. A. Sloane, Sep 24 2007
The limiting mean and variance of the first n terms are 2-phi and 2*phi-3, respectively. - Clark Kimberling, Mar 12 2014, Aug 16 2018
Let S(n) be defined as above. Then this sequence is S(1) + Sum_{n=0..} S(n), where the addition of strings represents concatenation. - Isaac Saffold, May 03 2019
The word is a concatenation of three runs: 0, 1, and 00. The limiting proportions of these are respectively 1 - phi/2, 1/2, and (phi - 1)/2. The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010
From Amiram Eldar, Mar 10 2021: (Start)
a(n) is the number of the trailing 0's in the dual Zeckendorf representation of (n+1) (A104326).
The asymptotic density of the occurrences of k (0 or 1) is 1/phi^(k+1), where phi is the golden ratio (A001622).
The asymptotic mean of this sequence is 1/phi^2 (A132338). (End)

Examples

			The word is 010010100100101001010010010100...
Over the alphabet {a,b} this is a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, ...

References

  • J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
  • Jean Berstel, Fibonacci words—a survey, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
  • J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc. - see p. 64.
  • Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337. [See A317208 for a link.]
  • G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
  • Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.

Links

Crossrefs

There are several versions of this sequence in the OEIS. This one and A003842 are probably the most important. See also A008352, A076662, A288581, A288582.
Binary complement of A005614. Cf. A014675, A036299, A003714, A014417, A096268, A096270, A133235, A182028, A213975.
Positions of 1's gives A003622.
Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.
Cf. A001622, A104326, A132338.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

Programs

  • Haskell
    a003849 n = a003849_list !! n
a003849_list = tail $ concat fws where
   fws = [1] : [0] : (zipWith (++) fws $ tail fws)
-- Reinhard Zumkeller, Nov 01 2013, Apr 07 2012
  • Magma
    t1:=[ n le 2 select ["0","0,1"][n] else Self(n-1) cat "," cat Self(n-2) : n in [1..12]]; t1[12];
  • Maple
    z := proc(m) option remember; if m=0 then [0] elif m=1 then [0,1] else [op(z(m-1)),op(z(m-2))]; fi; end; z(12);
M:=19; S[0]:=`0`; S[1]:=`01`; for n from 2 to M do S[n]:=cat(S[n-1], S[n-2]); od:
t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i-1,substring(t0,i..i)); od: # N. J. A. Sloane, Nov 01 2006
  • Mathematica
    Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 10] (* Robert G. Wilson v, Mar 05 2005 *)
Flatten[Nest[{#, #[[1]]} &, {0, 1}, 9]] (* IWABUCHI Yu(u)ki, Oct 23 2013 *)
Table[Floor[(n + 2) #] - Floor[(n + 1) #], {n, 0, 120}] &[2 - GoldenRatio] (* Michael De Vlieger, Aug 15 2016 *)
SubstitutionSystem[{0->{0,1},1->{0}},{0},{10}][[1]] (* Harvey P. Dale, Dec 20 2021 *)
  • PARI
    a(n)=my(k=2);while(fibonacci(k)<=n,k++);while(n>1,while(fibonacci(k--)>n,); n-=fibonacci(k)); n==1 \\ Charles R Greathouse IV, Feb 03 2014
  • PARI
    M3849=[2,2,1,0]/*L(k),S(k),L(k-1),S(k-1)*/; A003849(n)={while(n>M3849[1],M3849=vecextract(M3849,[1,2,1,2])+[M3849[3],M3849[4]<M. F. Hasler, Apr 07 2021
  • Python
    def fib(n):
    """Return the concatenation of A003849(0..F-1) where F is the smallest
       Fibonacci number > n, so that the result contains a(n) at index n."""
    a, b = '10'
    while len(b)<=n:
        a, b = b, b + a
    return b # Robert FERREOL, Apr 15 2016, edited by M. F. Hasler, Apr 07 2021
  • Python
    from math import isqrt
def A003849(n): return 2-(n+2+isqrt(m:=5*(n+2)**2)>>1)+(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 25 2022

Formula

a(n) = floor((n+2)*r) - floor((n+1)*r) where r=phi/(1+2*phi) and phi is the Golden Ratio. - Benoit Cloitre, Nov 10 2003
a(n) = A003714(n) mod 2 = A014417(n) mod 2. - Philippe Deléham, Jan 04 2004
The first formula by Cloitre is just one of an infinite family of formulas. Using phi^2=1+phi, it follows that r=phi/(1+2*phi)=2-phi. Then from floor(-x)=-floor(x)-1 for non-integer x, it follows that a(n)=2-A014675(n)=2-(floor((n+2)* phi)-floor((n+1)*phi)). - Michel Dekking, Aug 27 2016
a(n) = 1 - A096270(n+1), i.e., A096270 is the complement of this sequence. - A.H.M. Smeets, Mar 31 2024

Extensions

Revised by N. J. A. Sloane, Jul 03 2012

A035513 Wythoff array read by falling antidiagonals.

Original entry on oeis.org

1, 2, 4, 3, 7, 6, 5, 11, 10, 9, 8, 18, 16, 15, 12, 13, 29, 26, 24, 20, 14, 21, 47, 42, 39, 32, 23, 17, 34, 76, 68, 63, 52, 37, 28, 19, 55, 123, 110, 102, 84, 60, 45, 31, 22, 89, 199, 178, 165, 136, 97, 73, 50, 36, 25, 144, 322, 288, 267, 220, 157, 118, 81, 58, 41, 27, 233, 521
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

T(0,0)=1, T(0,1)=2,...; y^2-x^2-xy
Inverse of sequence A064274 considered as a permutation of the nonnegative integers. - Howard A. Landman, Sep 25 2001
The Wythoff array W consists of all the Wythoff pairs (x(n),y(n)), where x=A000201 and y=A001950, so that W contains every positive integer exactly once. The differences T(i,2j+1)-T(i,2j) form the Wythoff difference array, A080164, which also contains every positive integer exactly once. - Clark Kimberling, Feb 08 2003
For n>2 the determinant of any n X n contiguous subarray of A035513 (as a square array) is 0. - Gerald McGarvey, Sep 18 2004
From Clark Kimberling, Nov 14 2007: (Start)
Except for initial terms in some cases:
(Row 1) = A000045
(Row 2) = A000032
(Row 3) = A006355
(Row 4) = A022086
(Row 5) = A022087
(Row 6) = A000285
(Row 7) = A022095
(Row 8) = A013655 (sum of Fibonacci and Lucas numbers)
(Row 9) = A022112
(Row 10-19) = A022113, A022120, A022121, A022379, A022130, A022382, A022088, A022136, A022137, A022089
(Row 20-28) = A022388, A022096, A022090, A022389, A022097, A022091, A022390, A022098, A022092
(Column 1) = A003622 = AA Wythoff sequence
(Column 2) = A035336 = BA Wythoff sequence
(Column 3) = A035337 = ABA Wythoff sequence
(Column 4) = A035338 = BBA Wythoff sequence
(Column 5) = A035339 = ABBA Wythoff sequence
(Column 6) = A035340 = BBBA Wythoff sequence
Main diagonal = A020941. (End)
The Wythoff array is the dispersion of the sequence given by floor(n*x+x-1), where x=(golden ratio). See A191426 for a discussion of dispersions. - Clark Kimberling, Jun 03 2011
If u and v are finite sets of numbers in a row of the Wythoff array such that (product of all the numbers in u) = (product of all the numbers in v), then u = v. See A160009 (row 1 products), A274286 (row 2), A274287 (row 3), A274288 (row 4). - Clark Kimberling, Jun 17 2016
All columns of the Wythoff array are compound Wythoff sequences. This follows from the main theorem in the 1972 paper by Carlitz, Scoville and Hoggatt. For an explicit expression see Theorem 10 in Kimberling's paper from 2008 in JIS. - Michel Dekking, Aug 31 2017
The Wythoff array can be viewed as an infinite graph over the set of nonnegative integers, built as follows: start with an empty graph; for all n = 0, 1, ..., create an edge between n and the sum of the degrees of all i < n. Finally, remove vertex 0. In the resulting graph, the connected components are chains and correspond to the rows of the Wythoff array. - Luc Rousseau, Sep 28 2017
Suppose that h < k are consecutive terms in a row of the Wythoff array. If k is in an even numbered column, then h = floor(k/tau); otherwise, h = -1 + floor(k/tau). - Clark Kimberling, Mar 05 2020
From Clark Kimberling, May 26 2020: (Start)
For k > = 0, column k shows the numbers m having F(k+1) as least term in the Zeckendorf representation of m. For n >= 1, let r(n,k) be the number of terms in column k that are <= n. Then n/r(n,k) = n/(F(k+1)*tau + F(k)*(n-1)), by Bottomley's formula, so that the limiting ratio is 1/(F(k+1)*tau + F(k)). Summing over all k gives Sum_{k>=0} 1/(F(k+1)*tau + F(k)) = 1. Thus, in the limiting sense:
38.19...% of the numbers m have least term 1;
23.60...% have least term 2;
14.58...% have least term 3;
9.01...% have least term 5, etc. (End)
Named after the Dutch mathematician Willem Abraham Wythoff (1865-1939). - Amiram Eldar, Jun 11 2021
From Clark Kimberling, Jun 04 2025: (Start)
Let u(n) = (T(n,1),T(n,2)) mod 2. The positive integers (A000027) are partitioned into 4 sets (sequences):
{n : u(n) = (0,0)} = (3, 5, 9, 15, 19, 25, 29,...) = 1 + 2*A190429
{n: u(n) = (0,1)} = (2, 6, 12, 16, 18, 22, 28,...) = A191331
{n : u(n) = (1,0)} = (1, 7, 11, 13, 17, 21, 23,...) = A086843
{n: u(n) = (1,1)} = (4, 8, 10, 14, 20, 24, 26,...) = A191330.
Let v(n) = (T(n,1),T(n,2)) mod 3. The positive integers are partitioned into 9 sets (sequences):
{n : v(n) = (0,0)} = (4, 13, 19, 28, 43, 52,...) = 1 + 3*A190434
{n: v(n) = (0,1)} = (3, 12, 27, 36, 42, 51,...) = 3*A140399
{n : v(n) = (0,2)} = (5, 11, 20, 35, 44, 50,...) = 2 + 3*A190439
{n: v(n) = (1,0)} = (9, 18, 24, 33, 48, 57,...) = 3*A140400
{n: v(n) = (1,1)} = (2, 8, 17, 26, 32, 41,...) = A384601
{n : v(n) = (1,2)} = (1, 10, 16, 25, 34, 40,...) = A384602
{n: v(n) = (2,0)} = (14, 23, 29, 38, 47, 53,...) = 2 + 3*A190438
{n: v(n) = (2,1)} = (7, 22, 31, 37, 46, 61,...) = 1 + 3*A190433
{n : v(n) = (2,2)} = (6, 15, 21, 30, 39, 45,...) = 3*A140398.
Conjecture: If m >= 2, then {(T(n,1), T(n,2)) mod m} has cardinality m^2. (End)

Examples

			The Wythoff array begins:
   1    2    3    5    8   13   21   34   55   89  144 ...
   4    7   11   18   29   47   76  123  199  322  521 ...
   6   10   16   26   42   68  110  178  288  466  754 ...
   9   15   24   39   63  102  165  267  432  699 1131 ...
  12   20   32   52   84  136  220  356  576  932 1508 ...
  14   23   37   60   97  157  254  411  665 1076 1741 ...
  17   28   45   73  118  191  309  500  809 1309 2118 ...
  19   31   50   81  131  212  343  555  898 1453 2351 ...
  22   36   58   94  152  246  398  644 1042 1686 2728 ...
  25   41   66  107  173  280  453  733 1186 1919 3105 ...
  27   44   71  115  186  301  487  788 1275 2063 3338 ...
  ...
The extended Wythoff array has two extra columns, giving the row number n and A000201(n), separated from the main array by a vertical bar:
0     1  |   1    2    3    5    8   13   21   34   55   89  144   ...
1     3  |   4    7   11   18   29   47   76  123  199  322  521   ...
2     4  |   6   10   16   26   42   68  110  178  288  466  754   ...
3     6  |   9   15   24   39   63  102  165  267  432  699 1131   ...
4     8  |  12   20   32   52   84  136  220  356  576  932 1508   ...
5     9  |  14   23   37   60   97  157  254  411  665 1076 1741   ...
6    11  |  17   28   45   73  118  191  309  500  809 1309 2118   ...
7    12  |  19   31   50   81  131  212  343  555  898 1453 2351   ...
8    14  |  22   36   58   94  152  246  398  644 1042 1686 2728   ...
9    16  |  25   41   66  107  173  280  453  733 1186 1919 3105   ...
10   17  |  27   44   71  115  186  301  487  788 1275 2063 3338   ...
11   19  |  30   49   79   ...
12   21  |  33   54   87   ...
13   22  |  35   57   92   ...
14   24  |  38   62   ...
15   25  |  40   65   ...
16   27  |  43   70   ...
17   29  |  46   75   ...
18   30  |  48   78   ...
19   32  |  51   83   ...
20   33  |  53   86   ...
21   35  |  56   91   ...
22   37  |  59   96   ...
23   38  |  61   99   ...
24   40  |  64   ...
25   42  |  67   ...
26   43  |  69   ...
27   45  |  72   ...
28   46  |  74   ...
29   48  |  77   ...
30   50  |  80   ...
31   51  |  82   ...
32   53  |  85   ...
33   55  |  88   ...
34   56  |  90   ...
35   58  |  93   ...
36   59  |  95   ...
37   61  |  98   ...
38   63  |     ...
   ...
Each row of the extended Wythoff array also satisfies the Fibonacci recurrence, and may be extended to the left using this recurrence backwards.
From _Peter Munn_, Jun 11 2021: (Start)
The Wythoff array appears to have the following relationship to the traditional Fibonacci rabbit breeding story, modified for simplicity to be a story of asexual reproduction.
Give each rabbit a number, 0 for the initial rabbit.
When a new round of rabbits is born, allocate consecutive numbers according to 2 rules (the opposite of many cultural rules for inheritance precedence): (1) newly born child of Rabbit 0 gets the next available number; (2) the descendants of a younger child of any given rabbit precede the descendants of an older child of the same rabbit.
Row n of the Wythoff array lists the children of Rabbit n (so Rabbit 0's children have the Fibonacci numbers: 1, 2, 3, 5, ...). The generation tree below shows rabbits 0 to 20. It is modified so that each round of births appears on a row.
                                                                 0
                                                                 :
                                       ,-------------------------:
                                       :                         :
                       ,---------------:                         1
                       :               :                         :
              ,--------:               2               ,---------:
              :        :               :               :         :
        ,-----:        3         ,-----:         ,-----:         4
        :     :        :         :     :         :     :         :
     ,--:     5     ,--:     ,---:     6     ,---:     7     ,---:
     :  :     :     :  :     :   :     :     :   :     :     :   :
  ,--:  8  ,--:  ,--:  9  ,--:  10  ,--:  ,--:  11  ,--:  ,--:  12
  :  :  :  :  :  :  :  :  :  :   :  :  :  :  :   :  :  :  :  :   :
  : 13  :  : 14  : 15  :  : 16   :  : 17  : 18   :  : 19  : 20   :
The extended array's nontrivial extra column (A000201) gives the number that would have been allocated to the first child of Rabbit n, if Rabbit n (and only Rabbit n) had started breeding one round early.
(End)

References

  • John H. Conway, Posting to Math Fun Mailing List, Nov 25 1996.
  • Clark Kimberling, "Stolarsky interspersions," Ars Combinatoria 39 (1995) 129-138.

Links

Crossrefs

See comments above for more cross-references.
Cf. A003622, A064274 (inverse), A083412 (transpose), A000201, A001950, A080164, A003603, A265650, A019586 (row that contains n).
For two versions of the extended Wythoff array, see A287869, A287870.

Programs

  • Maple
    W:= proc(n,k) Digits:= 100; (Matrix([n, floor((1+sqrt(5))/2* (n+1))]). Matrix([[0,1], [1,1]])^(k+1))[1,2] end: seq(seq(W(n, d-n), n=0..d), d=0..10); # Alois P. Heinz, Aug 18 2008
A035513 := proc(r, c)
    option remember;
    if c = 1 then
        A003622(r) ;
    else
        A022342(1+procname(r, c-1)) ;
    end if;
end proc:
seq(seq(A035513(r,d-r),r=1..d-1),d=2..15) ; # R. J. Mathar, Jan 25 2015
  • Mathematica
    W[n_, k_] := Fibonacci[k + 1] Floor[n*GoldenRatio] + (n - 1) Fibonacci[k]; Table[ W[n - k + 1, k], {n, 12}, {k, n, 1, -1}] // Flatten
  • PARI
    T(n,k)=(n+sqrtint(5*n^2))\2*fibonacci(k+1) + (n-1)*fibonacci(k)
for(k=0,9,for(n=1,k, print1(T(n,k+1-n)", "))) \\ Charles R Greathouse IV, Mar 09 2016
  • Python
    from sympy import fibonacci as F, sqrt
import math
tau = (sqrt(5) + 1)/2
def T(n, k): return F(k + 1)*int(math.floor(n*tau)) + F(k)*(n - 1)
for n in range(1, 11): print([T(k, n - k + 1) for k in range(1, n + 1)]) # Indranil Ghosh, Apr 23 2017
  • Python
    from math import isqrt, comb
from gmpy2 import fib2
def A035513(n):
    a = (m:=isqrt(k:=n<<1))+(k>m*(m+1))
    x = n-comb(a,2)
    b, c = fib2(a-x+2)
    return b*(x+isqrt(5*x*x)>>1)+c*(x-1) # Chai Wah Wu, Jun 26 2025

Formula

T(n, k) = Fib(k+1)*floor[n*tau]+Fib(k)*(n-1) where tau = (sqrt(5)+1)/2 = A001622 and Fib(n) = A000045(n). - Henry Bottomley, Dec 10 2001
T(n,-1) = n-1. T(n,0) = floor(n*tau). T(n,k) = T(n,k-1) + T(n,k-2) for k>=1. - R. J. Mathar, Sep 03 2016

Extensions

Comments about the extended Wythoff array added by N. J. A. Sloane, Mar 07 2016

A001951 A Beatty sequence: a(n) = floor(n*sqrt(2)).

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, 25, 26, 28, 29, 31, 32, 33, 35, 36, 38, 39, 41, 42, 43, 45, 46, 48, 49, 50, 52, 53, 55, 56, 57, 59, 60, 62, 63, 65, 66, 67, 69, 70, 72, 73, 74, 76, 77, 79, 80, 82, 83, 84, 86, 87, 89, 90, 91, 93, 94, 96, 97, 98, 100
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Earliest monotonic sequence greater than 0 satisfying the condition: "a(n) + 2n is not in the sequence". - Benoit Cloitre, Mar 25 2004
Also the integer part of the hypotenuse of isosceles right triangles. The real part of these numbers is irrational. For proof see Jones and Jones.
First differences are 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, ... (A006337 with a 1 in front). - Philippe Deléham, May 29 2006
It appears that the distance between the a(n)-th triangular number and the nearest square is not greater than floor(a(n)/2). - Ralf Stephan, Sep 14 2013
These are the nonnegative integers m satisfying sin(m*Pi/r)*sin((m+1)*Pi/r) <= 0, where r = sqrt(2). In general, the Beatty sequence of an irrational number r > 1 consists of the numbers m satisfying sin(m*x)*sin((m+1)*x) <= 0, where x = Pi/r. Thus the numbers m satisfying sin(m*x)*sin((m+1)*x) > 0 form the Beatty sequence of r/(1-r). - Clark Kimberling, Aug 21 2014
For n > 0: A080764(a(n)) = 1. - Reinhard Zumkeller, Jul 03 2015
From Clark Kimberling, Oct 17 2016: (Start)
We can generate A001951 and A001952 without using sqrt(2).
First write the even positive integers in a row:
2 4 6 8 10 12 14 . . .
Then put 1 under 2 and add:
2 4 6 8 10 12 14 . . .
1
3
Next, under 4, put the least positive integer that is not yet in rows 2 and 3;
it is 2; and add:
2 4 6 8 10 12 14 . . .
1 2
3 6
Next, under the 6 in row 1, put the least positive integer not yet in rows 2 and 3;
it is 4, and add:
2 4 6 8 10 12 14 . . .
1 2 4
3 6 10
Continue in this manner. (End)
This sequence contains an infinite number of powers of 2 (proof in Crux Mathematicorum link). See A103341. - Bernard Schott, Mar 08 2019
The terms of this sequence generate the multiplicative group of positive rational numbers (observation by Stephen M. Gagola, Jr.; see References). - Allen Stenger, Aug 05 2023
a(n) is also the number of distinct straight cylinders with integer radius and height having the same surface as a sphere with radius n. - Felix Huber, Sep 20 2024
Let P(x,y) be the condition x^2 + y^2 <= n^2, then 4*a(n) is the number of integer points (x,y) such that P(x,y) is true and at least one of P(x+1,y), P(x-1,y), P(x,y+1), P(x,y-1) is false. See LINKS for examples. - Bob de Boisvilliers, May 14 2025

References

  • Eric Duchêne, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, Urban Larsson, Wythoff Visions, Games of No Chance, Vol. 5; MSRI Publications, Vol. 70 (2017), pages 101-153.
  • Stephen M. Gagola Jr., Solution of Problem 12282, Am. Math. Monthly, 130 (2023), pp. 682-683.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 77.
  • Gareth A. Jones and J. Mary Jones, Elementary Number Theory, Springer, 1998; pp. 221-222.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Roland Sprague, Recreations in Mathematics, Blackie and Son, (1963).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, Revised edition (1997), Entry sqrt(2), p. 18.

Links

Crossrefs

Complement of A001952. Equals A001952(n) - 2*n for n>0.
Equals A003151(n) - n; a bisection of A094077.
Bisections: A022842, A342281.
Cf. A022342, A026250, A080764, A103341.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A003151 as the parent: A003151, A001951, A001952, A003152, A006337, A080763, A082844 (conjectured), A097509, A159684, A188037, A245219 (conjectured), A276862. - N. J. A. Sloane, Mar 09 2021
Partial sums: A194102.

Programs

  • Haskell
    a001951 = floor . (* sqrt 2) . fromIntegral
-- Reinhard Zumkeller, Sep 14 2014
  • Magma
    [Floor(n*Sqrt(2)): n in [0..60]]; // Vincenzo Librandi, Oct 22 2011
  • Magma
    [Isqrt(2*n^2):n in[0..60]]; // Jason Kimberley, Oct 28 2016
  • Maple
    a:=n->floor(n*sqrt(2)): seq(a(n),n=0..80); # Muniru A Asiru, Mar 09 2019
  • Mathematica
    Floor[Range[0, 72] Sqrt[2]] (* Robert G. Wilson v, Oct 17 2012 *)
  • Maxima
    makelist(floor(n*sqrt(2)), n, 0, 100); /* Martin Ettl, Oct 17 2012 */
  • PARI
    f(n) = for(j=1,n,print1(floor(sqrt(2*j^2))","))
  • PARI
    a(n)=sqrtint(2*n^2) \\ Charles R Greathouse IV, Oct 19 2016
  • Python
    from sympy import integer_nthroot
def A001951(n): return integer_nthroot(2*n**2,2)[0] # Chai Wah Wu, Mar 16 2021

Formula

a(n) = A000196(A001105(n)). - Jason Kimberley, Oct 26 2016
a(n) = floor(csc(1/(sqrt(2)*n))) for n > 0, since sqrt(2)*n < csc(1/(sqrt(2)*n)) < sqrt(2)*n + 1/(3*sqrt(2)*n) < floor(sqrt(2)*n) + 1 for n > 0. - Jianing Song, Sep 07 2021
a(n) = A194102(n) - A194102(n-1) for n > 0. - M. F. Hasler, Apr 23 2022

Extensions

More terms from David W. Wilson, Sep 20 2000

A191426 Dispersion of (3+[n*r]), where r=(golden ratio)=(1+sqrt(5))/2 and [ ]=floor, by antidiagonals.

Original entry on oeis.org

1, 4, 2, 9, 6, 3, 17, 12, 7, 5, 30, 22, 14, 11, 8, 51, 38, 25, 20, 15, 10, 85, 64, 43, 35, 27, 19, 13, 140, 106, 72, 59, 46, 33, 24, 16, 229, 174, 119, 98, 77, 56, 41, 28, 18, 373, 284, 195, 161, 127, 93, 69, 48, 32, 21, 606, 462, 318, 263, 208, 153, 114, 80, 54, 36, 23, 983, 750, 517, 428, 339, 250, 187, 132, 90, 61, 40, 26
Offset: 1

Views

Author

Clark Kimberling, Jun 02 2011

Keywords

Comments

Background discussion: Suppose that s is an increasing sequence of positive integers, that the complement t of s is infinite, and that t(1)=1. The dispersion of s is the array D whose n-th row is (t(n), s(t(n)), s(s(t(n))), s(s(s(t(n)))), ...). Every positive integer occurs exactly once in D, so that, as a sequence, D is a permutation of the positive integers. The sequence u given by u(n)=(number of the row of D that contains n) is a fractal sequence. Examples:
(1) s=A000040 (the primes), D=A114537, u=A114538.
(2) s=A022342 (without initial 0), D=A035513 (Wythoff array), u=A003603.
(3) s=A007067, D=A035506 (Stolarsky array), u=A133299.
More recent examples of dispersions: A191426-A191455.

Examples

			Northwest corner:
  1...4...9...17..30
  2...6...12..22..38
  3...7...14..25..43
  5...11..20..35..59
  8...15..27..46..77

References

  • Clark Kimberling, Fractal sequences and interspersions, Ars Combinatoria 45 (1997) 157-168.

Links

Crossrefs

Cf. A114537, A035513, A035506.

Programs

  • Mathematica
    (* Program generates the dispersion array T of increasing sequence f[n] *)
r = 40; r1 = 12; (* r=#rows of T, r1=#rows to show *)
c = 40; c1 = 12; (* c=#cols of T, c1=#cols to show *)
x = GoldenRatio; f[n_] := Floor[n*x + 3]
mex[list_] :=  NestWhile[#1 + 1 &, 1, Union[list][[#1]] <= #1 &, 1, Length[Union[list]]]
rows = {NestList[f, 1, c]};
Do[rows = Append[rows, NestList[f, mex[Flatten[rows]], r]], {r}];
t[i_, j_] := rows[[i, j]];
TableForm[Table[t[i, j], {i, 1, 10}, {j, 1, 10}]]
(* A191426 array *)
Flatten[Table[t[k, n - k + 1], {n, 1, c1}, {k, 1, n}]]  (* A191426 sequence *)
(* Program by Peter J. C. Moses, Jun 01 2011 *)

A003622 The Wythoff compound sequence AA: a(n) = floor(n*phi^2) - 1, where phi = (1+sqrt(5))/2.

Original entry on oeis.org

1, 4, 6, 9, 12, 14, 17, 19, 22, 25, 27, 30, 33, 35, 38, 40, 43, 46, 48, 51, 53, 56, 59, 61, 64, 67, 69, 72, 74, 77, 80, 82, 85, 88, 90, 93, 95, 98, 101, 103, 106, 108, 111, 114, 116, 119, 122, 124, 127, 129, 132, 135, 137, 140, 142, 145, 148, 150, 153, 156, 158, 161, 163, 166
Offset: 1

Views

Author

N. J. A. Sloane, Mira Bernstein, Marc LeBrun

Keywords

Comments

Also, integers with "odd" Zeckendorf expansions (end with ...+F_2 = ...+1) (Fibonacci-odd numbers); first column of Wythoff array A035513; from a 3-way splitting of positive integers. [Edited by Peter Munn, Sep 16 2022]
Also, numbers k such that A005206(k) = A005206(k+1). Also k such that A022342(A005206(k)) = k+1 (for all other k's this is k). - Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001
Also, positions of 1's in A139764, the smallest term in Zeckendorf representation of n. - John W. Layman, Aug 25 2011
From Amiram Eldar, Sep 03 2022: (Start)
Numbers with an odd number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is odd.
The asymptotic density of this sequence is 1 - 1/phi (A132338). (End)
{a(n)} is the unique monotonic sequence of positive integers such that {a(n)} and {b(n)}: b(n) = a(n) - n form a partition of the nonnegative integers. - Yifan Xie, Jan 25 2025

References

  • A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 62.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.
  • C. Kimberling, "Stolarsky interspersions", Ars Combinatoria 39 (1995) 129-138.
  • D. R. Morrison, "A Stolarsky array of Wythoff pairs", in A Collection of Manuscripts Related to the Fibonacci Sequence. Fibonacci Assoc., Santa Clara, CA, 1980, pp. 134-136.
  • J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 10.
  • N. J. A. Sloane and Simon Plouffe, Encyclopedia of Integer Sequences, Academic Press, 1995: this sequence appears twice, as both M3277 and M3278.

Links

Crossrefs

Positions of 1's in A003849.
Complement of A022342.
Cf. A066096, A139764, A035516, A026273, A104326, A132338, A356749.
The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

Programs

  • Haskell
    a003622 n = a003622_list !! (n-1)
a003622_list = filter ((elem 1) . a035516_row) [1..]
-- Reinhard Zumkeller, Mar 10 2013
  • Maple
    A003622 := proc(n)
    n+floor(n*(1+sqrt(5))/2)-1 ;
end proc: # R. J. Mathar, Jan 25 2015
# Maple code for the Wythoff compound sequences, from N. J. A. Sloane, Mar 30 2016
# The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.
# Assume files out1, out2 contain lists of the terms in the base sequences A and B from their b-files
read out1; read out2; b[0]:=b1: b[1]:=b2:
w2:=(i,j,n)->b[i][b[j][n]];
w3:=(i,j,k,n)->b[i][b[j][b[k][n]]];
for i from 0 to 1 do
lprint("name=",i);
lprint([seq(b[i][n],n=1..100)]):
od:
for i from 0 to 1 do for j from 0 to 1 do
lprint("name=",i,j);
lprint([seq(w2(i,j,n),n=1..100)]);
od: od:
for i from 0 to 1 do for j from 0 to 1 do for k from 0 to 1 do
lprint("name=",i,j,k);
lprint([seq(w3(i,j,k,n),n=1..100)]);
od: od: od:
  • Mathematica
    With[{c=GoldenRatio^2},Table[Floor[n c]-1,{n,70}]] (* Harvey P. Dale, Jun 11 2011 *)
Range[70]//Floor[#*GoldenRatio^2]-1& (* Waldemar Puszkarz, Oct 10 2017 *)
  • PARI
    a(n)=floor(n*(sqrt(5)+3)/2)-1
  • PARI
    a(n) = (sqrtint(n^2*5)+n*3)\2 - 1; \\ Michel Marcus, Sep 17 2022
  • Python
    from sympy import floor
from mpmath import phi
def a(n): return floor(n*phi**2) - 1 # Indranil Ghosh, Jun 09 2017
  • Python
    from math import isqrt
def A003622(n): return (n+isqrt(5*n**2)>>1)+n-1 # Chai Wah Wu, Aug 11 2022

Formula

a(n) = floor(n*phi) + n - 1. [Corrected by Jianing Song, Aug 18 2022]
a(n) = floor(floor(n*phi)*phi) = A000201(A000201(n)). [See the Mathematics Stack Exchange link for a proof of the equivalence of the definition. - Jianing Song, Aug 18 2022]
a(n) = 1 + A022342(1 + A022342(n)).
G.f.: 1 - (1-x)*Sum_{n>=1} x^a(n) = 1/1 + x/1 + x^2/1 + x^3/1 + x^5/1 + x^8/1 + ... + x^F(n)/1 + ... (continued fraction where F(n)=n-th Fibonacci number). - Paul D. Hanna, Aug 16 2002
a(n) = A001950(n) - 1. - Philippe Deléham, Apr 30 2004
a(n) = A022342(n) + n. - Philippe Deléham, May 03 2004
a(n) = a(n-1) + 2 + A005614(n-2); also a(n) = a(n-1) + 1 + A001468(n-1). - A.H.M. Smeets, Apr 26 2024

A005614 The binary complement of the infinite Fibonacci word A003849. Start with 1, apply 0->1, 1->10, iterate, take limit.

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Previous name was: The infinite Fibonacci word (start with 1, apply 0->1, 1->10, iterate, take limit).
Characteristic function of A022342. - Philippe Deléham, May 03 2004
a(n) = number of 0's between successive 1's (see also A003589 and A007538). - Eric Angelini, Jul 06 2005
With offset 1 this is the characteristic sequence for Wythoff A-numbers A000201=[1,3,4,6,...].
Eric Angelini's comment made me think that if 1 is defined to be the number of 0's between successive 1's in a string of 0's and 1's, then this string is 101. Applying the same operation to the digits of 101 leads to 101101, the iteration leads to successive palindromes of lengths given by A001911, up to a(n). - Rémi Schulz, Jul 06 2010
For generalized Fibonacci words see A221150, A221151, A221152, ... - Peter Bala, Nov 11 2013
The limiting mean of the first n terms is phi - 1; the limiting variance is phi (A001622). - Clark Kimberling, Mar 12 2014
Apply the difference operator to every column of the Wythoff difference array, A080164, to get an array of Fibonacci numbers, F(h). Replace each F(h) with h, and apply the difference operator to every column. In the resulting array, every column is A005614. - Clark Kimberling, Mar 02 2015
Binary expansion of the rabbit constant A014565. - M. F. Hasler, Nov 10 2018

Examples

			The infinite word is 101101011011010110101101101011...

References

  • J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
  • G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

Links

Crossrefs

Binary complement of A003849, which is the standard form of this sequence.
Two other essentially identical sequences are A096270, A114986.
Subwords: A178992, A171676.
Cf. A000045 (Fibonacci numbers), A001468, A001911, A005206 (partial sums), A014565, A014675, A022342, A036299, A044432, A221150, A221151, A221152.
Cf. A339051 (odd bisection), A339052 (even bisection).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

Programs

  • Haskell
    a005614 n = a005614_list !! n
a005614_list = map (1 -) a003849_list
-- Reinhard Zumkeller, Apr 07 2012
  • Magma
    [Floor((n+1)*(-1+Sqrt(5))/2)-Floor(n*(-1+Sqrt(5))/2): n in [1..100]]; // Vincenzo Librandi, Jan 17 2019
  • Maple
    Digits := 50; u := evalf((1-sqrt(5))/2); A005614 := n->floor((n+1)*u)-floor(n*u);
  • Mathematica
    Nest[ Flatten[ # /. {0 -> {1}, 1 -> {1, 0}}] &, {1}, 10] (* Robert G. Wilson v, Jan 30 2005 *)
Flatten[Nest[{#, #[[1]]} &, {1, 0}, 9]] (* IWABUCHI Yu(u)ki, Oct 23 2013 *)
SubstitutionSystem[{0 -> {1}, 1 -> {1, 0}}, {1, 0}, 9] // Last (* Jean-François Alcover, Feb 06 2020 *)
  • PARI
    a(n,w1,s0,s1)=local(w2); for(i=2,n,w2=[ ]; for(k=1,length(w1),w2=concat(w2, if(w1[ k ],s1,s0))); w1=w2); w2
for(n=2,10,print(n" "a(n,[ 0 ],[ 1 ],[ 1,0 ]))) \\ Gives successive convergents to sequence
  • PARI
    /* for m>=1 compute exactly A183136(m+1)+1 terms of the sequence */
r=(1+sqrt(5))/2;v=[1,0];for(n=2,m,v=concat(v,vector(floor((n+1)/r),i,v[i]));a(n)=v[n];) /* Benoit Cloitre, Jan 16 2013 */
  • Python
    from math import isqrt
def A005614(n): return (n+isqrt(m:=5*(n+2)**2)>>1)-(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 17 2022

Formula

Define strings S(0)=1, S(1)=10, thereafter S(n)=S(n-1)S(n-2); iterate. Sequence is S(oo). The individual S(n)'s are given in A036299.
a(n) = floor((n+2)*u) - floor((n+1)*u), where u = (-1 + sqrt(5))/2.
Sum_{n>=0} a(n)/2^(n+1) = A014565. - R. J. Mathar, Jul 19 2013
From Peter Bala, Nov 11 2013: (Start)
If we read the present sequence as the digits of a decimal constant c = 0.101101011011010 ... then we have the series representation c = Sum_{n >= 1} 1/10^floor(n*phi). An alternative representation is c = Sum_{n >= 1} 1/10^floor(n/phi) - 10/9.
The constant 9*c has the simple continued fraction representation [0; 1, 10, 10, 100, 1000, ..., 10^Fibonacci(n), ...]. See A010100.
Using this result we can find the alternating series representation c = 1/9 - 9*Sum_{n >= 1} (-1)^(n+1)*(1 + 10^Fibonacci(3*n+1))/( (10^(Fibonacci(3*n - 1)) - 1)*(10^(Fibonacci(3*n + 2)) - 1) ). The series converges very rapidly: for example, the first 10 terms of the series give a value for c accurate to more than 5.7 million decimal places. Cf. A014565. (End)
a(n) = A005206(n+1) - A005206(n). a(2*n) = A339052(n); a(2*n+1) = A339051(n+1). - Peter Bala, Aug 09 2022

Extensions

Corrected by Clark Kimberling, Oct 04 2000
Name corrected by Michel Dekking, Apr 02 2019
Showing 1-10 of 47 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.