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 15 results. Next

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

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

A003842 The infinite Fibonacci word: start with 1, repeatedly apply the morphism 1->12, 2->1, take limit; or, start with S(0)=2, S(1)=1, and for n>1 define S(n)=S(n-1)S(n-2), then the sequence is S(oo).

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

Or, fixed point of the morphism 1->12, 2->1, starting from a(1) = 2.
A Sturmian word, as are all versions of this sequence. This means that if one slides a window of length n along the sequence, one sees exactly n+1 different subwords (see A213975). For a proof, see for example Chap. 2 of Lothaire (2002).
The limiting mean of the first n terms is 3 - phi, where phi is the golden ratio (A001622); the limiting variance is 2 - phi. - Clark Kimberling, Mar 12 2014
The Wikipedia article on L-system Example 1 is "Algae" given by the axiom: A and rules: A -> AB, B -> A. The sequence G(n) = G(n-1)G(n-2) yields this sequence when A -> 1, B -> 2. - Michael Somos, Jan 12 2015
In the limit #1's : #2's = phi : 1. - Frank M Jackson, Mar 12 2018

Examples

			Over the alphabet {a,b} this is the sequence 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. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
  • E. Bombieri and J. Taylor, Which distribution of matter diffracts? An initial investigation, in International Workshop on Aperiodic Crystals (Les Houches, 1986), J. de Physique, Colloq. C3, 47 (1986), C3-19 to C3-28.
  • Aldo de Luca and Stefano Varricchio, Finiteness and regularity in semigroups and formal languages. Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 1999. x+240 pp. ISBN: 3-540-63771-0 MR1696498 (2000g:68001). See p. 25.
  • 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.
  • G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

Links

Crossrefs

A003849 is another common version of this sequence.
See also A014675, A005614, A001468, A106750, A213975, A213976, A214317, A214318, A182028, A120613.
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
    a003842 n = a003842_list !! n
a003842_list = tail $ concat fws where
   fws = [2] : [1] : (zipWith (++) fws $ tail fws)
-- Reinhard Zumkeller, Oct 26 2013
  • Mathematica
    Nest[ Flatten[ # /. {1 -> {1, 2}, 2 -> {1}}] &, {1}, 10] (* Robert G. Wilson v, Mar 04 2005 *)
Table[n + 1 - Floor[((1 + Sqrt[5])/2)*Floor[2*(n + 1)/(1 + Sqrt[5])]], {n, 1, 50}] (* G. C. Greubel, May 18 2017 *)
SubstitutionSystem[{1->{1,2},2->{1}},{1},{10}][[1]] (* Harvey P. Dale, Nov 19 2022 *)
  • PARI
    for(n=1,50, print1(n+1 - floor(((1+sqrt(5))/2)*floor(2*(n+1)/(1+sqrt(5)))), ", ")) \\ G. C. Greubel, May 18 2017
  • Python
    def A003842(length):
    a = [1]
    while len(a)Nicholas Stefan Georgescu, Jun 14 2022
  • Python
    def aupto(nn):
    S, Fnm2, Fnm1 = [1, 2], 1, 2
    while len(S) < nn+1:
        S += S[:min(Fnm2, nn+1-len(S))]
        Fnm2, Fnm1 = Fnm1, Fnm1+Fnm2
    return S
print(aupto(104)) # Michael S. Branicky, Jun 06 2022
  • Python
    from math import isqrt
def A003842(n): return n+2-((m:=(n+2+isqrt(5*(n+2)**2)>>1)-n-2)+isqrt(5*m**2)>>1) # Chai Wah Wu, Aug 26 2022

Formula

Define strings S(0)=2, S(1)=1, S(n)=S(n-1)S(n-2); iterate. Sequence is S(infinity).
a(n) = n + 2 - A120613(n+1). - Benoit Cloitre, Jul 28 2005 [Corrected by N. J. A. Sloane, Jun 30 2018]

Extensions

Entry revised by N. J. A. Sloane, Jul 03 2012

A022342 Integers with "even" Zeckendorf expansions (do not end with ...+F_2 = ...+1) (the Fibonacci-even numbers); also, apart from first term, a(n) = Fibonacci successor to n-1.

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, 41, 42, 44, 45, 47, 49, 50, 52, 54, 55, 57, 58, 60, 62, 63, 65, 66, 68, 70, 71, 73, 75, 76, 78, 79, 81, 83, 84, 86, 87, 89, 91, 92, 94, 96, 97, 99, 100, 102, 104, 105, 107
Offset: 1

Views

Author

Marc LeBrun

Keywords

Comments

The Zeckendorf expansion of n is obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains; for example, 100 = 89 + 8 + 3.
The Fibonacci successor to n is found by replacing each F_i in the Zeckendorf expansion by F_{i+1}; for example, the successor to 100 is 144 + 13 + 5 = 162.
If k appears, k + (rank of k) does not (10 is the 7th term in the sequence but 10 + 7 = 17 is not a term of the sequence). - Benoit Cloitre, Jun 18 2002
From Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001: (Start)
a(n) = Sum_{k in A_n} F_{k+1}, where a(n)= Sum_{k in A_n} F_k is the (unique) expression of n as a sum of "noncontiguous" Fibonacci numbers (with index >= 2).
a(10^n) gives the first few digits of g = (sqrt(5)+1)/2.
The sequences given by b(n+1) = a(b(n)) obey the general recursion law of Fibonacci numbers. In particular the (sub)sequence (of a(-)) yielded by a starting value of 2=a(1), is the sequence of Fibonacci numbers >= 2. Starting points of all such subsequences are given by A035336.
a(n) = floor(phi*n+1/phi); phi = (sqrt(5)+1)/2. a(F_n)=F_{n+1} if F_n is the n-th Fibonacci number.
(End)
From Amiram Eldar, Sep 03 2022: (Start)
Numbers with an even number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is even.
The asymptotic density of this sequence is 1/phi (A094214). (End)

Examples

			The successors to 1, 2, 3, 4=3+1 are 2, 3, 5, 7=5+2.

References

  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.
  • E. Zeckendorf, Représentation des nombres naturels par une somme des nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41, 179-182, 1972.

Links

Crossrefs

Positions of 0's in A003849.
Complement of A003622.
Cf. A000201, A005206, A035336, A066096, A001950, A062879, A035516, A026274.
Cf. A035612, A094214, A104326, A356749.
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
    a022342 n = a022342_list !! (n-1)
a022342_list = filter ((notElem 1) . a035516_row) [0..]
-- Reinhard Zumkeller, Mar 10 2013
  • Magma
    [Floor(n*(Sqrt(5)+1)/2)-1: n in [1..100]]; // Vincenzo Librandi, Feb 16 2015
  • Maple
    A022342 := proc(n)
      local g;
      g := (1+sqrt(5))/2 ;
    floor(n*g)-1 ;
end proc: # R. J. Mathar, Aug 04 2013
  • Mathematica
    With[{t=GoldenRatio^2},Table[Floor[n*t]-n-1,{n,70}]] (* Harvey P. Dale, Aug 08 2012 *)
  • PARI
    a(n)=floor(n*(sqrt(5)+1)/2)-1
  • PARI
    a(n)=(sqrtint(5*n^2)+n-2)\2 \\ Charles R Greathouse IV, Feb 27 2014
  • Python
    from math import isqrt
def A022342(n): return (n+isqrt(5*n**2)>>1)-1 # Chai Wah Wu, Aug 17 2022

Formula

a(n) = floor(n*phi^2) - n - 1 = floor(n*phi) - 1 = A000201(n) - 1, where phi is the golden ratio.
a(n) = A003622(n) - n. - Philippe Deléham, May 03 2004
a(n+1) = A022290(2*A003714(n)). - R. J. Mathar, Jan 31 2015
For n > 1: A035612(a(n)) > 1. - Reinhard Zumkeller, Feb 03 2015
a(n) = A000201(n) - 1. First differences are given in A014675 (or A001468, ignoring its first term). - M. F. Hasler, Oct 13 2017
a(n) = a(n-1) + 1 + A005614(n-2) for n > 1; also a(n) = a(n-1) + A014675(n-2) = a(n-1) + A001468(n-1). - A.H.M. Smeets, Apr 26 2024

Extensions

Name edited by Peter Munn, Dec 07 2021

A014675 The infinite Fibonacci word (start with 1, apply 1->2, 2->21, take limit).

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

The limiting mean and variance of the first n terms are both equal to the golden ratio (A001622). - Clark Kimberling, Mar 12 2014
Let F = A000045 (Fibonacci numbers). For n >= 3, the first F(n)-2 terms of A014675 form a palindrome; see A001911. If k is not one of the numbers F(n)-2, then the first k terms of A014675 do not form a palindrome. - Clark Kimberling, Jul 14 2014
First differences of A000201. - Tom Edgar, Apr 23 2015 [Editor's note: except for the offset: as for A022342, below. - M. F. Hasler, Oct 13 2017]
Also first differences of A022342 (which starts at offset 1): a(n)=A022342(n+2)-A022342(n+1), n >= 0. Equal to A001468 without its first term: a(n) = A001468(n+1), n >= 0. - M. F. Hasler, Oct 13 2017
The word is a concatenation of three runs: 1, 2, and 22. The limiting proportions of these are respectively 1/2, 1 - phi/2, and (phi - 1)/2, where phi = golden ratio. The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010

References

  • D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. See Table 2.
  • D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7, p. 36.
  • G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

Links

Crossrefs

This is the {2,1} version. The standard form is A003849 (alphabet {0,1}). See also A005614 (alphabet {1,0}), A003842 (alphabet {1,2} instead of {2,1}).
Cf. A082389, A008351, A000045, A001622, A001911.
Equals A001468 except for initial term.
Differs from A025143 in many entries starting at entry 8.
First differences of A000201 and of A022342.
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

  • Maple
    Digits := 50: t := evalf( (1+sqrt(5))/2); A014675 := n->floor((n+2)*t)-floor((n+1)*t);
  • Mathematica
    Nest[ Flatten[ # /. {1 -> 2, 2 -> {2, 1}}] &, {1}, 11] (* Robert G. Wilson v *)
SubstitutionSystem[{1->{2},2->{2,1}},{1},{11}][[1]] (* Harvey P. Dale, Jan 01 2023 *)
  • PARI
    first(n)=my(v=[1],u); while(#vCharles R Greathouse IV, Jun 21 2017
  • PARI
    apply( {A014675(n,r=quadgen(5)-1)=(n+2)\r-(n+1)\r}, [0..99]) \\ M. F. Hasler, Apr 07 2021, improved on suggestion from Kevin Ryde, Apr 23 2021
  • Python
    from math import isqrt
def A014675(n): return (n+2+isqrt(m:=5*(n+2)**2)>>1)-(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 10 2022

Formula

Define strings S(0)=1, S(1)=2, S(n)=S(n-1).S(n-2) for n>=2. Sequence is S(infinity).
a(n) = floor((n+2)*phi) - floor((n+1)*phi) = A000201(n+2) - A000201(n+1), phi = (1 + sqrt(5))/2.

Extensions

Corrected by N. J. A. Sloane, Nov 07 2001

A096270 Fixed point of the morphism 0->01, 1->011.

Original entry on oeis.org

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, 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, 1, 1, 0, 1, 0
Offset: 0

Views

Author

N. J. A. Sloane, Jun 22 2004

Keywords

Comments

This is another version of the Fibonacci word A005614.
(With offset 1) for k>0, a(ceiling(k*phi^2))=0 and a(floor(k*phi^2))=1 where phi=(1+sqrt(5))/2 is the Golden ratio. - Benoit Cloitre, Apr 01 2006
(With offset 1) for n>1 a(A000045(n)) = (1-(-1)^n)/2.
Equals the Fibonacci word A005614 with an initial zero.
Also the Sturmian word of slope phi (cf. A144595). - N. J. A. Sloane, Jan 13 2009
More precisely: (a(n)) is the inhomogeneous Sturmian word of slope phi-1 and intercept 0: a(n) = floor((n+1)*(phi-1)) - floor(n*(phi-1)), n >= 0. - Michel Dekking, May 21 2018
The ratio of number of 1's to number of 0's tends to the golden ratio (1+sqrt(5))/2 = 1.618... - Zak Seidov, Feb 15 2012

References

  • J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

Links

Crossrefs

Cf. A003849, A096268, A001519. See A005614, A114986 for other versions.
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

  • Magma
    [-1+Floor(n*(1+Sqrt(5))/2)-Floor((n-1)*(1+Sqrt(5))/2): n in [1..100]]; // Wesley Ivan Hurt, Aug 29 2022
  • Mathematica
    Nest[ Function[l, {Flatten[(l /. {0 -> {0, 1}, 1 -> {0, 1, 1}})]}], {0}, 6] (* Robert G. Wilson v, Feb 04 2005 *)
  • PARI
    a(n)=-1+floor(n*(1+sqrt(5))/2)-floor((n-1)*(1+sqrt(5))/2) \\ Benoit Cloitre, Apr 01 2006
  • Python
    from math import isqrt
def A096270(n): return (n+1+isqrt(5*(n+1)**2)>>1)-(n+isqrt(5*n**2)>>1)>>1 # Chai Wah Wu, Aug 29 2022

Formula

Conjecture: a(n) is given recursively by a(1)=0 and, for n>1, by a(n)=1 if n=F(2k+1) and a(n)=a(n-F(2k+1)) otherwise, where F(2k+1) is the largest odd-indexed Fibonacci number smaller than or equal to n. (This has been confirmed for more than nine million terms.) The odd-indexed bisection of the Fibonacci numbers (A001519) is {1, 2, 5, 13, 34, 89, ...}. So by the conjecture, we would expect that a(30) = a(30-13) = a(17) = a(17-13) = a(4) = a(4-2) = a(2) = 1, which is in fact correct. - John W. Layman, Jun 29 2004
From Michel Dekking, Apr 13 2016: (Start)
Proof of the above conjecture:
Let g be the morphism above: g(0)=01, g(1)=011. Then g^n(0) has length F(2n+1), and (a(n)) starts with g^n(0) for all n>0. Obviously g^n(0) ends in 1 for all n, proving the first part of the conjecture.
We extend the semigroup of words with letters 0 and 1 to the free group, adding the inverses 0*:=0^{-1} and 1*:=1^{-1}. Easy observation: for any word w one has g(w1)= g(w0)1. We claim that for all n>1 one has g^n(0)=u(n)v(n)v(n)0*1, where u(n)=g(u(n-1))0 and v(n)=0*g(v(n-1))0. The recursion starts with u(2)=0, v(2)=10. Indeed: g^2(0)=01011=u(2)v(2)v(2)0*1. Induction step:
g^{n+1}(0)=g(g^n(0))= g(u(n)v(n)v(n)0*1)= g(u(n)v(n)v(n))1= g(u(n))00*g(v(n))00*g(v(n))00*1=u(n+1)v(n+1)v(n+1)0*1.
Since v(n) has length F(2n-1), which is the largest odd-indexed Fibonacci number smaller than or equal to m for all m between F(2n-1) and F(2n+1), the claim proves the second part of the conjecture. (End)
(With offset 1) a(n) = -1 + floor(n*phi) - floor((n-1)*phi) where phi=(1+sqrt(5))/2 so a(n) = -1 + A082389(n). - Benoit Cloitre, Apr 01 2006

Extensions

More terms from John W. Layman, Jun 29 2004

A001468 There are a(n) 2's between successive 1's.

Original entry on oeis.org

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

Views

Author

N. J. A. Sloane

Keywords

Comments

The Fibonacci word on the alphabet {2,1}, with an extra 1 in front. - Michel Dekking, Nov 26 2018
Start with 1, apply 1->12, 2->122, take limit. - Philippe Deléham, Sep 23 2005
Also number of occurrences of n in Hofstadter G-sequence (A005206) and in A019446. - Reinhard Zumkeller, Feb 02 2012, Aug 07 2011
A block-fractal sequence: every block occurs infinitely many times. Also a reverse block-fractal sequence. See A280511. - Clark Kimberling, Jan 06 2017

References

  • D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. See Table 2.
  • D. R. Hofstadter, personal communication, Jul 15 1977.
  • 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).

Links

Crossrefs

Same as A014675 if initial 1 is deleted. Cf. A003849, A000201, A280511.
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
    import Data.List (group)
a001468 n = a001468_list !! n
a001468_list = map length $ group a005206_list
-- Reinhard Zumkeller, Aug 07 2011
  • Maple
    Digits := 100: t := evalf( (1+sqrt(5))/2); A001468 := n-> floor((n+1)*t)-floor(n*t);
  • Mathematica
    Table[Floor[GoldenRatio*(n + 1)] - Floor[GoldenRatio*n], {n, 0, 80}] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Aug 14 2006 *)
Nest[ Flatten[# /. {1 -> {1, 2}, 2 -> {1, 2, 2}}] &, {1}, 6] (* Robert G. Wilson v, May 20 2014 and corrected Apr 24 2017 following Clark Kimberling's email of Mar 22 2017 *)
SubstitutionSystem[{1->{1,2},2->{1,2,2}},{1},{6}][[1]] (* Harvey P. Dale, Jan 31 2022 *)
  • PARI
    a=[1];for(i=1,30,a=concat([a,vector(a[i],j,2),1]));a \\ Or compute as A001468(n)=A201(n+1)-A201(n) with A201(n)=(n+sqrtint(5*n^2))\2, working for n>=0 although A000201 is defined for n>=1. - M. F. Hasler, Oct 13 2017
  • Python
    def A001468(length):
    a = [1]
    for i in range(length):
        for _ in range(a[i]):
            a.append(2)
        a.append(1)
        if len(a)>=length:
            break
    return a[:length] # Nicholas Stefan Georgescu, Jun 02 2022
  • Python
    from math import isqrt
def A001468(n): return (n+1+isqrt(m:=5*(n+1)**2)>>1)-(n+isqrt(m-10*n-5)>>1) # Chai Wah Wu, Aug 25 2022

Formula

a(n) = [(n+1) tau] - [n tau], tau = (1 + sqrt 5)/2 = A001622, [] = floor function.
a(n) = A000201(n+1) - A000201(n) = A022342(n+1) - A022342(n), n >= 1; i.e., the first term discarded, this yields the first differences of A000201 and A022342. - M. F. Hasler, Oct 13 2017

Extensions

Rechecked by N. J. A. Sloane, Nov 07 2001
Showing 1-10 of 15 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.