login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000201 Lower Wythoff sequence (a Beatty sequence): a(n) = floor(n*phi), where phi = (1+sqrt(5))/2 = A001622.
(Formerly M2322 N0917)
242

%I M2322 N0917

%S 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,

%T 42,43,45,46,48,50,51,53,55,56,58,59,61,63,64,66,67,69,71,72,74,76,77,

%U 79,80,82,84,85,87,88,90,92,93,95,97,98,100,101,103,105,106,108,110

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

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

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

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

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

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

%C Cumulative sum of A001468 terms. - _Eric Angelini_, Aug 19 2008

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

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

%C Also row numbers of A213676 starting with an even number of zeros. - _Reinhard Zumkeller_, Mar 10 2013

%D M. Bunder and K. Tognetti, On the self matching properties of [j tau], Discrete Math., 241 (2001), 139-151.

%D I. G. Connell, Some properties of Beatty sequences I, Canad. Math. Bull., 2 (1959), 190-197.

%D A. S. Fraenkel, The bracket function and complementary sets of integers, Canad. J. Math., 21 (1969), 6-27. [History, references, generalization]

%D A. S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, Amer. Math. Monthly, 89 (1982), 353-361 (the case a=1).

%D M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman, 1989; see p. 107.

%D David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.5.

%D A. M. Gleason et al., The William Lowell Putnam Mathematical Competition: Problems and Solutions 1938-1964, Math. Assoc. America, 1980, pp. 513-514.

%D Martin Griffiths, On a Matrix Arising from a Family of Iterated Self-Compositions, Journal of Integer Sequences, 18 (2015(, #15.11.8.

%D H. Grossman, A set containing all integers, Amer. Math. Monthly, 69 (1962), 532-533.

%D Clark Kimberling, Complementary equations and Wythoff sequences, Journal of Integer Sequences 11 (2008, Article 08.3.3) 1-8.

%D Clark Kimberling, Complementary Equations, Journal of Integer Sequences, 10 (2007), Article 07.1.4.

%D C. Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.

%D U. Larsson, N. Fox, An Aperiodic Subtraction Game of Nim-Dimension Two, Journal of Integer Sequences, 2015, Vol. 18, #15.7.4.

%D D. J. Newman, Problem 5252, Amer. Math. Monthly, 72 (1965), 1144-1145. Problem 3117, Amer. Math. Monthly, 34 (1927), 158-159.

%D Gabriel Nivasch, More on the Sprague-Grundy function for Wythoff’s game, pages 377-410 in "Games of No Chance 3, MSRI Publications Volume 56, 2009; available from http://www.msri.org/people/staff/levy/files/Book56/43nivasch.pdf

%D Michel Rigo, Invariant games and non-homogeneous Beatty sequences, Slides of a talk, Journée de Mathématiques Discrètes, 2015; http://orbi.ulg.be/bitstream/2268/177711/1/Rigo.pdf

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D K. B. Stolarsky, Beatty sequences, continued fractions and certain shift operators, Canad. Math. Bull., 19 (1976), 473-482.

%D X. Sun, Wythoff's sequence ..., Discr. Math., 300 (2005), 180-195.

%D I. M. Yaglom, Two games with matchsticks, pp. 1-7 of Qvant Selecta: Combinatorics I, Amer Math. Soc., 2001.

%H N. J. A. Sloane, <a href="/A000201/b000201.txt">The first 10000 terms</a>

%H J.-P. Allouche, J. Shallit and G. Skordev, <a href="http://dx.doi.org/10.1016/j.disc.2004.12.004">Self-generating sets, integers with missing blocks and substitutions</a>, Discrete Math. 292 (2005) 1-15.

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp.756-757

%H Shiri Artstein-Avidan, Aviezri S. Fraenkel and Vera T. Sos, <a href="http://dx.doi.org/10.1016/j.disc.2007.08.070">A two-parameter family of an extension of Beatty</a>, Discr. Math. 308 (2008), 4578-4588.

%H Shiri Artstein-avidan, Aviezri S. Fraenkel and Vera T. Sos, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/coatp8.pdf">A two-parameter family of an extension of Beatty sequences</a>, Discrete Math., 308 (2008), 4578-4588.

%H E. J. Barbeau, J. Chew and S. Tanny, <a href="http://www.combinatorics.org/Volume_4/Abstracts/v4i1r16.html">A matrix dynamics approach to Golomb's recursion</a>, Electronic J. Combinatorics, #4.1 16 1997.

%H L. Carlitz, R. Scoville and T. Vaughan, <a href="http://www.fq.math.ca/Scanned/11-4/carlitz.pdf">Some arithmetic functions related to Fibonacci numbers</a>, Fib. Quart., 11 (1973), 337-386.

%H B. Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="http://www.emis.de/journals/JIS/VOL6/Cloitre/cloitre2.html">Numerical analogues of Aronson's sequence</a>, J. Integer Seqs., Vol. 6 (2003), #03.2.2.

%H B. Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="http://arXiv.org/abs/math.NT/0305308">Numerical analogues of Aronson's sequence</a>, arXiv:math/0305308 [math.NT], 2003.

%H J. H. Conway and N. J. A. Sloane, <a href="/A019586/a019586.pdf">Notes on the Para-Fibonacci and related sequences</a>

%H H. S. M. Coxeter, <a href="/A000201/a000201.pdf">The Golden Section, Phyllotaxis and Wythoff's Game</a>, Scripta Math. 19 (1953), 135-143. [Annotated scanned copy]

%H F. Michel Dekking, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Dekking/dekk4.html">Morphisms, Symbolic Sequences, and Their Standard Forms</a>, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.

%H P. J. Downey and R. E. Griswold, <a href="http://www.fq.math.ca/Scanned/22-4/downey.pdf">On a family of nested recurrences</a>, Fib. Quart., 22 (1984), 310-317.

%H Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/WythoffWisdomJune62016.pdf">Wythoff Wisdom</a>, 43 pages, no date, unpublished.

%H Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, <a href="/A001950/a001950.pdf">Wythoff Wisdom</a>, unpublished, no date [Cached copy, with permission]

%H N. Fox, <a href="http://arxiv.org/abs/1407.2823">On Aperiodic Subtraction Games with Bounded Nim Sequence</a>, arXiv preprint arXiv:1407.2823 [math.CO], 2014.

%H A. S. Fraenkel, <a href="http://www.wisdom.weizmann.ac.il/~fraenkel/Papers/RationalGames3.pdf">Ratwyt</a>, December 28 2011.

%H M. Griffiths, <a href="http://www.jstor.org/stable/10.4169/amer.math.monthly.118.06.497">The Golden String, Zeckendorf Representations, and the Sum of a Series</a>, Amer. Math. Monthly, 118 (2011), 497-507.

%H T. Karki, A. Lacroix, M. Rigo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Rigo/rigo6.html">On the recognizability of self-generating sets</a>, JIS 13 (2010) #10.2.2.

%H C. Kimberling, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/goldentext.html">A Self-Generating Set and the Golden Mean</a>, J. Integer Sequences, 3 (2000), #00.2.8.

%H C. Kimberling, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Kimberling/kimberling24.html">Matrix Transformations of Integer Sequences</a>, J. Integer Seqs., Vol. 6, 2003.

%H Clark Kimberling, <a href="http://www.fq.math.ca/Papers1/52-5/Problems.pdf">Problem Proposals</a>, The Fibonacci Quarterly, vol. 52 #5, 2015, p5-14.

%H R. J. Nowakowski, <a href="/A104429/a104429.pdf">Generalizations of the Langford-Skolem problem</a>, M.S. Thesis, Dept. Math., Univ. Calgary, May 1975. [Scanned copy, with permission.]

%H Vincent Russo and Loren Schwiebert, <a href="http://www.fq.math.ca/49-2.html">Beatty Sequences, Fibonacci Numbers, and the Golden Ratio</a>, The Fibonacci Quarterly, Vol 49, Number 2, May 2011.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).

%H N. J. A. Sloane, <a href="/classic.html#WYTH">Classic Sequences</a>

%H Richard Southwell and Jianwei Huang, <a href="http://arxiv.org/abs/1205.0596">Complex Networks from Simple Rewrite Systems</a>, arXiv preprint arXiv:1205.0596 [cs.SI], 2012. - _N. J. A. Sloane_, Oct 13 2012

%H J. C. Turner, <a href="http://www.fq.math.ca/Scanned/27-1/turner.pdf">The alpha and the omega of the Wythoff pairs</a>, Fib. Q., 27 (1989), 76-86.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/BeattySequence.html">Beatty Sequence</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GoldenRatio.html">Golden Ratio</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RabbitConstant.html">Rabbit Constant</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WythoffsGame.html">Wythoff's Game</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WythoffArray.html">Wythoff Array</a>

%H <a href="/index/Be#Beatty">Index entries for sequences related to Beatty sequences</a>

%H <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>

%F Zeckendorf expansion of n (cf. A035517) ends with an even number of 0's.

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

%F a(1) = 1; for n>0, a(n+1) = a(n)+1 if n is not in sequence, a(n+1) = a(n)+2 if n is in sequence.

%F a(a(n)) = floor[n*phi^2] - 1 = A003622(n).

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

%F {a(n)} is a solution to the recurrence a(a(n)+n) = 2*a(n)+n, a(1)=1 (see Barbeau et al.).

%F a(n) = A001950(n) - n - _Philippe Deléham_, May 02 2004

%F a(0) = 0; a(n) = n + max{ k : a(k) < n}. - _Vladeta Jovovic_, Jun 11 2004

%F a(Fib(r-1)+j) = Fib(r)+a(j) for 0<j<=Fib(r-2); 2<r. - _Paul Weisenhorn_, Aug 18 2012

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

%e From Roland Schroeder (florola(AT)gmx.de), Jul 13 2010: (Start)

%e Example for n = 5; a(5) = 8

%e (Start: [1,2,3,4,5]; 8 steps until [5,4,3,2,1]):

%e [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)

%p Digits := 100; t := evalf((1+sqrt(5))/2); A000201 := n->floor(t*n);

%t Table[Floor[N[n*(1+Sqrt[5])/2]], {n, 1, 75}]

%t Array[ Floor[ #*GoldenRatio] &, 68] (* _Robert G. Wilson v_, Apr 17 2010 *)

%o (PARI) a(n)=floor(n*(sqrt(5)+1)/2)

%o (PARI) a(n)=(n+sqrtint(5*n^2))\2 \\ _Charles R Greathouse IV_, Feb 07 2013

%o (Maxima) makelist(floor(n*(1+sqrt(5))/2),n,1,60); [_Martin Ettl_, Oct 17 2012]

%o (Haskell)

%o a000201 n = a000201_list !! (n-1)

%o a000201_list = f [1..] [1..] where

%o f (x:xs) (y:ys) = y : f xs (delete (x + y) ys)

%o -- _Reinhard Zumkeller_, Jul 02 2015, Mar 10 2013

%Y a(n) = least k such that s(k) = n, where s = A026242. Complement of A001950. See also A058066.

%Y The permutation A002251 maps between this sequence and A001950, in that A002251(a(n)) = A001950(n), A002251(A001950(n)) = a(n).

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

%Y A185615 gives values n such that n divides A000201(n)^m for some integer m>0.

%Y Cf. A183110.

%Y Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864.

%K nonn,easy,nice

%O 1,2

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 19 12:48 EST 2018. Contains 299333 sequences. (Running on oeis4.)