A035513 Wythoff array read by falling antidiagonals.
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
A005248 Bisection of Lucas numbers: a(n) = L(2*n) = A000032(2*n).
2, 3, 7, 18, 47, 123, 322, 843, 2207, 5778, 15127, 39603, 103682, 271443, 710647, 1860498, 4870847, 12752043, 33385282, 87403803, 228826127, 599074578, 1568397607, 4106118243, 10749957122, 28143753123, 73681302247, 192900153618, 505019158607, 1322157322203
Offset: 0
Comments
Drop initial 2; then iterates of A050411 do not diverge for these starting values. - David W. Wilson
All nonnegative integer solutions of Pell equation a(n)^2 - 5*b(n)^2 = +4 together with b(n)=A001906(n), n>=0. - Wolfdieter Lang, Aug 31 2004
a(n+1) = B^(n)AB(1), n>=0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 3=`10`, 7=`010`, 18=`0010`, 47=`00010`, ..., in Wythoff code. a(0) = 2 = B(1) in Wythoff code.
Output of Tesler's formula (as well as that of Lu and Wu) for the number of perfect matchings of an m X n Möbius band where m and n are both even specializes to this sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009
Numbers having two 1's in their base-phi representation. - Robert G. Wilson v, Sep 13 2010
Pisano period lengths: 1, 3, 4, 3, 2, 12, 8, 6, 12, 6, 5, 12, 14, 24, 4, 12, 18, 12, 9, 6, ... - R. J. Mathar, Aug 10 2012
From Wolfdieter Lang, Feb 18 2013: (Start)
a(n) is also one half of the total number of round trips, each of length 2*n, on the graph P_4 (o-o-o-o) (the simple path with 4 points (vertices) and 3 lines (or edges)). See the array and triangle A198632 for the general case of the graph P_N (there N is n and the length is l=2*k).
O.g.f. for w(4,l) (with zeros for odd l): y*(d/dy)S(4,y)/S(4,y) with y=1/x and Chebyshev S-polynomials (coefficients A049310). See also A198632 for a rewritten form. One half of this o.g.f. for x -> sqrt(x) produces the g.f. (2-3x)/(1-3x+x^2) given below. (End)
Solutions (x, y) = (a(n), a(n+1)) satisfying x^2 + y^2 = 3xy - 5. - Michel Lagneau, Feb 01 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 7xy + y^2 + 45 = 0. - Colin Barker, Feb 16 2014
Except for the first term, positive values of x (or y) satisfying x^2 - 18xy + y^2 + 320 = 0. - Colin Barker, Feb 16 2014
a(n) are the numbers such that a(n)^2-2 are Lucas numbers. - Michel Lagneau, Jul 22 2014
All sequences of this form, b(n+1) = 3*b(n) - b(n-1), regardless of initial values, which includes this sequence, yield this sequence as follows: a(n) = (b(j+n) + b(j-n))/b(j), for any j, except where b(j) = 0. Also note formula below relating this a(n) to all sequences of the form G(n+1) = G(n) + G(n-1). - Richard R. Forberg, Nov 18 2014
A non-simple continued fraction expansion for F(2n*(k+1))/F(2nk) k>=1 is a(n) + (-1)/(a(n) + (-1)/(a(n) + ... + (-1)/a(n))) where a(n) appears exactly k times (F(n) denotes the n-th Fibonacci number). E.g., F(16)/F(12) equals 7 + (-1)/(7 + (-1)/7). Furthermore, these a(n) are exactly the positive integers k such that the non-simple infinite continued fraction k + (-1)/(k + (-1)/(k + (-1)/(k + ...))) belongs to Q(sqrt(5)). Compare to Benoit Cloitre and Thomas Baruchel's comments at A002878. - Greg Dresden, Aug 13 2019
For n >= 1, a(n) is the number of cyclic up-down words of length 2*n over an alphabet of size 3. - Sela Fried, Apr 08 2025
Examples
G.f. = 2 + 3*x + 7*x^2 + 18*x^3 + 47*x^4 + 123*x^5 + 322*x^6 + 843*x^7 + ... - _Michael Somos_, Aug 11 2009
References
- 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).
- Richard P. Stanley, Enumerative combinatorics, Vol. 2. Volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..1000
- Richard André-Jeannin, Summation of Certain Reciprocal Series Related to Fibonacci and Lucas Numbers, The Fibonacci Quarterly, Vol. 29, No. 3 (1991), pp. 200-204.
- Peter Bala, Some simple continued fraction expansions for an infinite product, Part 1.
- Hacène Belbachir, Soumeya Merwa Tebtoub, and László Németh, Ellipse Chains and Associated Sequences, J. Int. Seq., Vol. 23 (2020), Article 20.8.5.
- Pooja Bhadouria, Deepika Jhala and Bijendra Singh, Binomial Transforms of the k-Lucas Sequences and its Properties, The Journal of Mathematics and Computer Science (JMCS), Vol. 8, No. 1 (2014), pp. 81-92; sequences B_1, T_1 and R_1.
- Yurii S. Bystryk, Vitalii L. Denysenko, and Volodymyr I. Ostryk, Lune and Lens Sequences, ResearchGate preprint, 2024. See pp. 51, 56.
- Noureddine Chair, Exact two-point resistance, and the simple random walk on the complete graph minus N edges, Ann. Phys., Vol. 327, No. 12 (2012), pp. 3116-3129, Eq. (18).
- Tony Crilly, Double sequences of positive integers, Math. Gaz., Vol. 69 (1985), pp. 263-271.
- Pedro P. B. de Oliveira, Enrico Formenti, Kévin Perrot, Sara Riva and Eurico L. P. Ruivo, Non-maximal sensitivity to synchronism in periodic elementary cellular automata: exact asymptotic measures, arXiv:2004.07128 [cs.FL], 2020.
- Robert G. Donnelly, Molly W. Dunkum, Murray L. Huber and Lee Knupp, Sign-alternating Gibonacci polynomials, arXiv:2012.14993 [math.CO], 2020.
- Sergio Falcon, Relationships between Some k-Fibonacci Sequences, Applied Mathematics, Vol. 5, No. 15 (2014), pp. 2226-2234.
- Margherita Maria Ferrari and Norma Zagaglia Salvi, Aperiodic Compositions and Classical Integer Sequences, Journal of Integer Sequences, Vol. 20 (2017), Article 17.8.8.
- Sela Fried, A formula for the number of up-down words, arXiv:2503.02005 [math.CO], 2025.
- Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 8.
- Dale Gerdemann, Collision of Digits "Also interesting are the two bisections of the Lucas numbers A005248 (digit minimizer) and A002878 (digit maximizer). I particularly like the multiples of A005248 because I have this image of the two digits piling up on top of each other and then spreading out like waves".
- André Gougenheim, About the linear sequence of integers such that each term is the sum of the two preceding Part 1 Part 2, Fib. Quart., Vol. 9, No. 3 (1971), pp. 277-295, 298.
- Richard K. Guy, Letter to N. J. A. Sloane, Feb 1986.
- Tanya Khovanova, Recursive Sequences.
- Emrah Kılıç, Yücel Türker Ulutaş and Neşe Ömür, A Formula for the Generating Functions of Powers of Horadam's Sequence with Two Additional Parameters, J. Int. Seq., Vol. 14 (2011), Article 11.5.6, Table 2.
- Wentao T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, Vol. 293, No. 5-6 (2002), pp. 235-246. [From Sarah-Marie Belcastro, Jul 04 2009]
- Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee and Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
- Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992, arXiv:0911.4975 [math.NT], 2009.
- Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
- Sara Riva, Factorisation of Discrete Dynamical Systems, Ph.D. Thesis, Univ. Côte d'Azur (France 2023).
- Jeffrey Shallit, An interesting continued fraction, Math. Mag., Vol. 48, No. 4 (1975), pp. 207-211.
- Jeffrey Shallit, An interesting continued fraction, Math. Mag., Vol. 48, No. 4 (1975), pp. 207-211. [Annotated scanned copy]
- Jeffrey Shallit, Proving Properties of phi-Representations with the Walnut Theorem-Prover, arXiv:2305.02672 [math.NT], 2023.
- Jeffrey Shallit and N. J. A. Sloane, Correspondence, 1975.
- Paweł J. Szabłowski, On moments of Cantor and related distributions, arXiv preprint arXiv:1403.0386 [math.PR], 2014.
- Glenn Tesler, Matchings in Graphs on Non-Orientable Surfaces, Journal of Combinatorial Theory, Series B, Vol. 78, No. 2 (2000), pp. 198-231.
- Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
- Eric Weisstein's World of Mathematics, Phi Number System.
- A. V. Zarelua, On Matrix Analogs of Fermat’s Little Theorem, Mathematical Notes, Vol. 79, No. 6 (2006), pp. 783-796. Translated from Matematicheskie Zametki, Vol. 79, No. 6 (2006), pp. 840-855.
- Index entries for recurrences a(n) = k*a(n - 1) +/- a(n - 2).
- Index entries for sequences related to Chebyshev polynomials.
- Index entries for two-way infinite sequences.
- Index entries for linear recurrences with constant coefficients, signature (3,-1).
Crossrefs
Programs
-
Haskell
a005248 n = a005248_list !! n a005248_list = zipWith (+) (tail a001519_list) a001519_list -- Reinhard Zumkeller, Jan 11 2012
-
Magma
[Lucas(2*n) : n in [0..100]]; // Vincenzo Librandi, Apr 14 2011
-
Maple
a:= n-> (<<2|3>>. <<3|1>, <-1|0>>^n)[1$2]: seq(a(n), n=0..30); # Alois P. Heinz, Jul 31 2008 with(combinat): seq(5*fibonacci(n)^2+2*(-1)^n, n= 0..26);
-
Mathematica
a[0] = 2; a[1] = 3; a[n_] := 3a[n - 1] - a[n - 2]; Table[ a[n], {n, 0, 27}] (* Robert G. Wilson v, Jan 30 2004 *) Fibonacci[1 + 2n] + 1/2 (-Fibonacci[2n] + LucasL[2n]) (* Tesler. Sarah-Marie Belcastro, Jul 04 2009 *) LinearRecurrence[{3, -1}, {2, 3}, 50] (* Sture Sjöstedt, Nov 27 2011 *) LucasL[Range[0,60,2]] (* Harvey P. Dale, Sep 30 2014 *) -
PARI
{a(n) = fibonacci(2*n + 1) + fibonacci(2*n - 1)}; /* Michael Somos, Jun 23 2002 */ -
PARI
{a(n) = 2 * subst( poltchebi(n), x, 3/2)}; /* Michael Somos, Jun 28 2003 */ -
Sage
[lucas_number2(n,3,1) for n in range(37)] # Zerinvary Lajos, Jun 25 2008
Formula
a(n) = Fibonacci(2*n-1) + Fibonacci(2*n+1).
G.f.: (2-3*x)/(1-3*x+x^2). - Simon Plouffe in his 1992 dissertation.
a(n) = S(n, 3) - S(n-2, 3) = 2*T(n, 3/2) with S(n-1, 3) = A001906(n) and S(-2, x) = -1. U(n, x)=S(n, 2*x) and T(n, x) are Chebyshev's U- and T-polynomials.
a(n) = a(k)*a(n - k) - a(n - 2k) for all k, i.e., a(n) = 2*a(n) - a(n) = 3*a(n - 1) - a(n - 2) = 7*a(n - 2) - a(n - 4) = 18*a(n - 3) - a(n - 6) = 47*a(n - 4) - a(n - 8) etc., a(2n) = a(n)^2 - 2. - Henry Bottomley, May 08 2001
a(n) ~ phi^(2*n) where phi=(1+sqrt(5))/2. - Joe Keane (jgk(AT)jgk.org), May 15 2002
a(0)=2, a(1)=3, a(n) = 3*a(n-1) - a(n-2) = a(-n). - Michael Somos, Jun 28 2003
a(n) = phi^(2*n) + phi^(-2*n) where phi=(sqrt(5)+1)/2, the golden ratio. E.g., a(4)=47 because phi^(8) + phi^(-8) = 47. - Dennis P. Walsh, Jul 24 2003
With interpolated zeros, trace(A^n)/4, where A is the adjacency matrix of path graph P_4. Binomial transform is then A049680. - Paul Barry, Apr 24 2004
a(n) = (floor((3+sqrt(5))^n) + 1)/2^n. - Lekraj Beedassy, Oct 22 2004
a(n) = ((3-sqrt(5))^n + (3+sqrt(5))^n)/2^n (Note: substituting the number 1 for 3 in the last equation gives A000204, substituting 5 for 3 gives A020876). - Creighton Dement, Apr 19 2005
a(n) = (1/(n+1/2))*Sum_{k=0..n} B(2k)*L(2n+1-2k)*binomial(2n+1, 2k) where B(2k) is the (2k)-th Bernoulli number. - Benoit Cloitre, Nov 02 2005
a(n) = term (1,1) in the 1 X 2 matrix [2,3] . [3,1; -1,0]^n. - Alois P. Heinz, Jul 31 2008
a(n) = 2*cosh(2*n*psi), where psi=log((1+sqrt(5))/2). - Al Hakanson, Mar 21 2009
From Sarah-Marie Belcastro, Jul 04 2009: (Start)
a(n) - (a(n) - F(2n))/2 - F(2n+1) = 0. (Tesler)
Product_{r=1..n} (1 + 4*(sin((4r-1)*Pi/(4n)))^2). (Lu/Wu) (End)
a(n) = Fibonacci(2n+6) mod Fibonacci(2n+2), n > 1. - Gary Detlefs, Nov 22 2010
a(n) = 5*Fibonacci(n)^2 + 2*(-1)^n. - Gary Detlefs, Nov 22 2010
a(n) = 2^(2*n) * Sum_{k=1..2} (cos(k*Pi/5))^(2*n). - L. Edson Jeffery, Jan 21 2012
From Peter Bala, Jan 04 2013: (Start)
Let F(x) = Product_{n>=0} (1 + x^(4*n+1))/(1 + x^(4*n+3)). Let alpha = 1/2*(3 - sqrt(5)). This sequence gives the simple continued fraction expansion of 1 + F(alpha) = 2.31829 56058 81914 31334 ... = 2 + 1/(3 + 1/(7 + 1/(18 + ...))).
Also F(-alpha) = 0.64985 97768 07374 32950 has the continued fraction representation 1 - 1/(3 - 1/(7 - 1/(18 - ...))) and the simple continued fraction expansion 1/(1 + 1/((3-2) + 1/(1 + 1/((7-2) + 1/(1 + 1/((18-2) + 1/(1 + ...))))))).
F(alpha)*F(-alpha) has the simple continued fraction expansion 1/(1 + 1/((3^2-4) + 1/(1 + 1/((7^2-4) + 1/(1 + 1/((18^2-4) + 1/(1 + ...))))))).
Added Oct 13 2019: 1/2 + 1/2*F(alpha)/F(-alpha) = 1.5142923542... has the simple continued fraction expansion 1 + 1/((3 - 2) + 1/(1 + 1/((18 - 2) + 1/(1 + 1/(123 - 2) + 1/(1 + ...))))). (End)
G.f.: (W(0)+6)/(5*x), where W(k) = 5*x*k + x - 6 + 6*x*(5*k-9)/W(k+1) (continued fraction). - Sergei N. Gladkovskii, Aug 19 2013
Sum_{n >= 1} 1/( a(n) - 5/a(n) ) = 1. Compare with A001906, A002878 and A023039. - Peter Bala, Nov 29 2013
0 = a(n) * a(n+2) - a(n+1)^2 - 5 for all n in Z. - Michael Somos, Aug 24 2014
a(n) = (G(j+2n) + G(j-2n))/G(j), for n >= 0 and any j, positive or negative, except where G(j) = 0, and for any sequence of the form G(n+1) = G(n) + G(n-1) with any initial values for G(0), G(1), including non-integer values. G(n) includes Lucas, Fibonacci. Compare with A081067 for odd number offsets from j. - Richard R. Forberg, Nov 16 2014
a(n) = [x^n] ( (1 + 3*x + sqrt(1 + 6*x + 5*x^2))/2 )^n for n >= 1. - Peter Bala, Jun 23 2015
From J. M. Bergot, Oct 28 2015: (Start)
For n>0, a(n) = F(n-1) * L(n) + F(2*n+1) - (-1)^n with F(k) = A000045(k).
For n>1, a(n) = F(n+1) * L(n) + F(2*n-1) - (-1)^n.
For n>2, a(n) = 5*F(2*n-3) + 2*L(n-3) * L(n) + 8*(-1)^n. (End)
For n>1, a(n) = L(n-2)*L(n+2) -7*(-1)^n. - J. M. Bergot, Feb 10 2016
a(n) = 6*F(n-1)*L(n-1) - F(2*n-6) with F(n)=A000045(n) and L(n)=A000032(n). - J. M. Bergot, Apr 21 2017
E.g.f.: exp(4*x/(1+sqrt(5))^2) + exp((1/4)*(1+sqrt(5))^2*x). - Stefano Spezia, Aug 13 2019
From Peter Bala, Oct 14 2019: (Start)
a(n) = trace(M^n), where M is the 2 X 2 matrix [0, 1; 1, 1]^2 = [1, 1; 1, 2].
Consequently the Gauss congruences hold: a(n*p^k) = a(n*p^(k-1)) ( mod p^k ) for all prime p and positive integers n and k. See Zarelua and also Stanley (Ch. 5, Ex. 5.2(a) and its solution).
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 1/a(n) ) = 1/5.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 3/(a(n) + 2/(a(n))) ) = 1/6.
Sum_{n >= 1} (-1)^(n+1)/( a(n) + 9/(a(n) + 4/(a(n) + 1/(a(n)))) ) = 1/9.
x*exp(Sum_{n >= 1} a(n)*x^/n) = x + 3*x^2 + 8*x^3 + 21*x^4 + ... is the o.g.f. for A001906. (End)
a(n) = n + 2 + Sum_{k=1..n-1} k*a(n-k). - Yu Xiao, May 30 2020
Sum_{n>=1} 1/a(n) = A153415. - Amiram Eldar, Nov 11 2020
Sum_{n>=0} 1/(a(n) + 3) = (2*sqrt(5) + 1)/10 (André-Jeannin, 1991). - Amiram Eldar, Jan 23 2022
a(n) = 2*cosh(2*n*arccsch(2)) = 2*cosh(2*n*asinh(1/2)). - Peter Luschny, May 25 2022
a(n) = (5/2)*(Sum_{k=-n..n} binomial(2*n, n+5*k)) - (1/2)*4^n. - Greg Dresden, Jan 05 2023
a(n) = Sum_{k>=0} Lucas(2*n*k)/(Lucas(2*n)^(k+1)). - Diego Rattaggi, Jan 12 2025
Extensions
Additional comments from Michael Somos, Jun 23 2001
A007895 Number of terms in the Zeckendorf representation of n (write n as a sum of non-consecutive distinct Fibonacci numbers).
0, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 2, 3, 3, 3, 4, 3, 4, 4, 3, 4, 4, 4, 5, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 2, 3, 3
Offset: 0
Comments
Also number of 0's (or B's) in the Wythoff representation of n -- see the Reble link. See also A135817 for references and links for the Wythoff representation for n >= 1. - Wolfdieter Lang, Jan 21 2008; N. J. A. Sloane, Jun 28 2008
Or, a(n) is the number of applications of Wythoff's B sequence A001950 needed in the unique Wythoff representation of n >= 1. E.g., 16 = A(B(A(A(B(1))))) = ABAAB = `10110`, hence a(16) = 2. - Wolfdieter Lang, Jan 21 2008
Let M(0) = 0, M(1) = 1 and for i > 0, M(i+1) = f(concatenation of M(j), j from 0 to i - 1) where f is the morphism f(k) = k + 1. Then the sequence is the concatenation of M(j) for j from 0 to infinity. - Claude Lenormand (claude.lenormand(AT)free.fr), Dec 16 2003
From Joerg Arndt, Nov 09 2012: (Start)
Let m be the number of parts in the listing of the compositions of n into odd parts as lists of parts in lexicographic order, a(k) = (n - length(composition(k)))/2 for all k < Fibonacci(n) and all n (see example).
Let m be the number of parts in the listing of the compositions of n into parts 1 and 2 as lists of parts in lexicographic order, a(k) = n - length(composition(k)) for all k < Fibonacci(n) and all n (see example).
A000120 gives the equivalent for (all) compositions. (End)
a(n) = A104324(n) - A213911(n); row lengths in A035516 and A035516. - Reinhard Zumkeller, Mar 10 2013
a(n) is also the minimum number of Fibonacci numbers which sum to n, regardless of adjacency or duplication. - Alan Worley, Apr 17 2015
This follows from the fact that the sequence is subadditive: a(n+m) <= a(n) + a(m) for nonnegative integers n,m. See Lemma 2.1 of the Stoll link. - Robert Israel, Apr 17 2015
From Michel Dekking, Mar 08 2020: (Start)
This sequence is a morphic sequence on an infinite alphabet, i.e., (a(n)) is a letter-to-letter projection of a fixed point of a morphism tau.
The alphabet is {0,1,...,j,...}X{0,1}, and tau is given by
tau((j,0)) = (j,0) (j+1,1),
tau((j,1)) = (j,0).
The letter-to-letter map is given by the projection on the first coordinate: (j,i)->j for i=0,1.
To prove this, note first that the second coordinate of the letters generates the infinite Fibonacci word = A003849 = 0100101001001....
This implies that for all n and j one has
|tau^n(j,0)| = F(n+2),
where |w| denotes the length of a word w, and (F(n)) = A000045 are the Fibonacci numbers.
Secondly, we need the following simple, but crucial observation. Let the Zeckendorf representation of n be Z(n) = A014417(n). For example,
Z(0) = 0, Z(1) = 1, Z(2) = 10, Z(3) = 100, Z(4) = 101, Z(5) = 1000.
From the unicity of the Zeckendorf representation it follows that for the positions i = 0,1,...,F(n)-1 one has
Z(F(n+1)+i) = 10...0 Z(i),
where zeros are added to Z(i) to give the total representation length n-1.
This gives for i = 0,1,...,F(n)-1 that
a(F(n+1)+i) = a(i) + 1.
From the first observation follows that the first F(n+1) letters of tau^n(j,0) are equal to tau^{n-1}(j,0), and the last F(n) letters of tau^n(j,0) are equal to tau^{n-1}(j+1,1) = tau^{n-2}(j+1,0).
Combining this with the second observation shows that the first coordinate of the fixed point of tau, starting from (0,0), gives (a(n)).
It is of course possible to obtain a morphism tau' on the natural numbers by changing the alphabet: (j,0)-> 2j (j,1)-> 2j+1, which yields the morphism
tau'(2j) = 2j, 2j+3, tau'(2j+1) = 2j.
The fixed point of tau' starting with 0 is
u = 03225254254472544747625...
The corresponding letter-to-letter map lambda is given by lambda(2j)=j, lambda(2j+1)= j. Then lambda(u) = (a(n)).
(End)
Examples
a(46) = a(1 + 3 + 8 + 34) = 4.
From _Joerg Arndt_, Nov 09 2012: (Start)
Connection to the compositions of n into odd parts (see comment):
[ #]: a(n) composition into odd parts
[ 0] [ 0] 1 1 1 1 1 1 1 1
[ 1] [ 1] 1 1 1 1 1 3
[ 2] [ 1] 1 1 1 1 3 1
[ 3] [ 1] 1 1 1 3 1 1
[ 4] [ 2] 1 1 1 5
[ 5] [ 1] 1 1 3 1 1 1
[ 6] [ 2] 1 1 3 3
[ 7] [ 2] 1 1 5 1
[ 8] [ 1] 1 3 1 1 1 1
[ 9] [ 2] 1 3 1 3
[10] [ 2] 1 3 3 1
[11] [ 2] 1 5 1 1
[12] [ 3] 1 7
[13] [ 1] 3 1 1 1 1 1
[14] [ 2] 3 1 1 3
[15] [ 2] 3 1 3 1
[16] [ 2] 3 3 1 1
[17] [ 3] 3 5
[18] [ 2] 5 1 1 1
[19] [ 3] 5 3
[20] [ 3] 7 1
Connection to the compositions of n into parts 1 or 2 (see comment):
[ #]: a(n) composition into parts 1 and 2
[ 0] [0] 1 1 1 1 1 1 1
[ 1] [1] 1 1 1 1 1 2
[ 2] [1] 1 1 1 1 2 1
[ 3] [1] 1 1 1 2 1 1
[ 4] [2] 1 1 1 2 2
[ 5] [1] 1 1 2 1 1 1
[ 6] [2] 1 1 2 1 2
[ 7] [2] 1 1 2 2 1
[ 8] [1] 1 2 1 1 1 1
[ 9] [2] 1 2 1 1 2
[10] [2] 1 2 1 2 1
[11] [2] 1 2 2 1 1
[12] [3] 1 2 2 2
[13] [1] 2 1 1 1 1 1
[14] [2] 2 1 1 1 2
[15] [2] 2 1 1 2 1
[16] [2] 2 1 2 1 1
[17] [3] 2 1 2 2
[18] [2] 2 2 1 1 1
[19] [3] 2 2 1 2
[20] [3] 2 2 2 1
(End)
From _Michel Dekking_, Mar 08 2020: (Start)
The third iterate of the morphism tau generating this sequence:
tau^3((0,0)) = (0,0)(1,1)(1,0)(1,0)(2,1)
= (a(0),0)(a(1),1)(a(2),0)(a(3),0)(a(4),1). (End)
References
- Cornelius Gerrit Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1952), 190-195.
- F. Weinstein, The Fibonacci Partitions, preprint, 1995.
- Édouard 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
- T. D. Noe, Table of n, a(n) for n = 0..10000
- Joerg Arndt, Matters Computational (The Fxtbook), pp. 754-756.
- Paul Baird-Smith, Alyssa Epstein, Kristen Flint, and Steven J. Miller, The Zeckendorf Game, arXiv:1809.04881 [math.NT], 2018.
- D. E. Daykin, Representation of natural numbers as sums of generalized Fibonacci numbers, J. London Math. Soc. 35 (1960) 143-160.
- Michel Dekking, Points of increase of the sum of digits function of the base phi expansion, arXiv:2003.14125 [math.CO], 2020.
- F. Michel Dekking, The sum of digits functions of the Zeckendorf and the base phi expansions, Theoretical Computer Science (2021) Vol. 859, 70-79.
- Damien Jamet, Pierre Popoli, and Thomas Stoll, Maximum order complexity of the sum of digits function in Zeckendorf base and polynomial subsequences, arXiv:2106.09959 [math.NT], 2021, see p. 5.
- C. G. Lekkerkerker, Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Stichting Mathematisch Centrum, Zuivere Wiskunde, 1951.
- A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See p. 10.
- I. Nemes, Fibonacci representations of multiples of Fibonacci numbers.
- Don Reble, Zeckendorf vs. Wythoff representations: Comments on A007895.
- Thomas Stoll, Combinatorial constructions for the Zeckendorf sum of digits of polynomial values, The Ramanujan Journal November 2013, Volume 32, Issue 2, pp 227-243.
- F. V. Weinstein, Notes on Fibonacci partitions, arXiv:math/0307150 [math.NT], 2003-2018.
Crossrefs
Cf. A000045, A007953, A035514, A035515, A035516, A035517, A105446, A189920, A213676, A000120, A001950, A003714, A007015, A007016, A104324, A182535, A213911, A014417, A003849.
Cf. A135817 (lengths of Wythoff representation), A135818 (number of 1's (or A's) in the Wythoff representation).
Record positions are in A027941.
Programs
-
Haskell
a007895 = length . a035516_row -- Reinhard Zumkeller, Mar 10 2013
-
Maple
# With the following Maple program (not the best one), B(n) (n >= 1) yields the number of terms in the Zeckendorf representation of n. with(combinat): B := proc (n) local A, ct, m, j: A := proc (n) local i: for i while fibonacci(i) <= n do n-fibonacci(i) end do end proc: ct := 0; m := n: for j while 0 < A(m) do ct := ct+1: m := A(m) end do: ct+1 end proc: 0, seq(B(n), n = 1 .. 104); # Emeric Deutsch, Jul 05 2010 N:= 1000: # to get a(n) for n <= N m:= ceil(log[(1+sqrt(5))/2](sqrt(5)*N)): Z:= Vector(m): a[0]:= 0: for n from 1 to N do if Z[1] = 0 then Z[1]:= 1; q:= 1; else Z[2]:= 1; Z[1]:= 0; q:= 2; fi; while Z[q+1] = 1 do Z[q]:= 0; Z[q+1]:= 0; Z[q+2]:= 1; q:= q+2; od: a[n]:= add(Z[i],i=1..m); od: seq(a[n],n=0..N); # Robert Israel, Apr 17 2015 # alternative read("transforms") : # https://oeis.org/transforms.txt A007895 := proc(n) wt(A003714(n)) ; end proc: seq(A007895(n),n=0..10) ; # R. J. Mathar, Sep 22 2020
-
Mathematica
zf[n_] := (k = 1; ff = {}; While[(fi = Fibonacci[k]) <= n, AppendTo[ff, fi]; k++]; Drop[ff, 1]); zeckRep[n_] := If[n == 0, 0, r = n; s = {}; fr = zf[n]; While[r > 0, lf = Last[fr]; If[lf <= r, r = r - lf; PrependTo[s, lf]]; fr = Drop[fr, -1]]; s]; zeckRepLen[n_] := Length[zeckRep[n]]; Table[zeckRepLen[n], {n, 0, 104}] (* Jean-François Alcover, Sep 27 2011 *) DigitCount[Select[Range[0, 1000], BitAnd[#, 2#] == 0 &], 2, 1] (* Jean-François Alcover, Jan 25 2018 *) Table[Length[DeleteCases[NestWhileList[# - Fibonacci[Floor[Log[Sqrt[5] * # + 3/2]/Log[GoldenRatio]]] &, n, # > 1 &], 0]], {n, 0, 143}] (* Alonso del Arte, May 14 2019 *) Flatten[Nest[{Flatten[#], #[[1]] + 1} &, {0, 1}, 9]] (* Paolo Xausa, Jun 17 2024 *) -
PARI
a(n,mx=0)=if(n<4,n>0,if(!mx,while(fibonacci(mx)
-
PARI
a(n)=if(n<4, n>0, my(k=2,s,t); while(fibonacci(k++)<=n,); while(k && n, t=fibonacci(k); if(t<=n, n-=t; s++); k--); s) \\ Charles R Greathouse IV, Sep 02 2015
-
Python
from sympy import fibonacci def a(n): k=0 x=0 while n>0: k=0 while fibonacci(k)<=n: k+=1 x+=10**(k - 3) n-=fibonacci(k - 1) return str(x).count("1") print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 09 2017
Formula
a(n) = A143299(n+1) - 1. - Filip Zaludek, Oct 31 2016
Extensions
A014417 Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary words starting with 1 not containing 11, with the word 0 added.
0, 1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, 100000, 100001, 100010, 100100, 100101, 101000, 101001, 101010, 1000000, 1000001, 1000010, 1000100, 1000101, 1001000, 1001001, 1001010, 1010000, 1010001, 1010010, 1010100, 1010101
Offset: 0
Comments
Old name was: Representation of n in base of Fibonacci numbers (the Zeckendorf representation of n). Also, binary vectors not containing 11.
For n > 0, write n = Sum_{i >= 2} eps(i) Fib_i where eps(i) = 0 or 1 and no 2 consecutive eps(i) can be 1 (see A035517); then a(n) is obtained by writing the eps(i) in reverse order.
"One of the most important properties of the Fibonacci numbers is the special way in which they can be used to represent integers. Let's write j >> k <==> j >= k+2. Then every positive integer has a unique representation of the form n = F_k1 + F_k2 + ... + F_kr, where k1 >> k2 >> ... >> kr >> 0. (This is 'Zeckendorf's theorem.') ... We can always find such a representation by using a "greedy" approach, choosing F_k1 to be the largest Fibonacci number =< n, then choosing F_k2 to be the largest that is =< n - F_k1 and so on. Fibonacci representation needs a few more bits because adjacent 1's are not permitted; but the two representations are analogous." [Concrete Math.]
Since the binary representation of n in base of Fibonacci numbers allows only the successive bit pairs 00, 01, 10 and leaves 11 unused, we can use a ternary representation using all trits 0, 1, 2 where 00 --> 0, 01 --> 1 and 10 --> 2 (e.g. binary 1001010 as ternary 1022). - Daniel Forgues, Nov 30 2009
The same sequence also arises when considering the NegaFibonacci representations of the integers, as follows. Take the NegaFibonacci representations of n = 0, 1, 2, ... (A215022) and of n = -1, -2, -3, ... (A215023), sort the union of these two lists into increasing binary order, and we get A014417. Likewise the corresponding list of decimal representations, A003714, is the union of A215024 and A215025 sorted into increasing order. - N. J. A. Sloane, Aug 10 2012
Also, numbers, written in binary, such that no adjacent bits are equal to 1: A one-dimensional analog of the matrices considered in A228277/A228285, A228390, A228476, A228506 etc. - M. F. Hasler, Apr 27 2014
The sequence of final bits, starting with a(1), is the complement of the Fibonacci word A005614. - N. J. A. Sloane, Oct 03 2018
This representation is named after the Belgian Army doctor and mathematician Edouard Zeckendorf (1901-1983). - Amiram Eldar, Jun 11 2021
Examples
The Zeckendorf expansions of 1, 2, ... are 1 = 1 = Fib_2 -> 1, 2 = 2 = Fib_3 -> 10, 3 = Fib_4 -> 100, 4 = 3+1 = Fib_4 + Fib_2 -> 101, 5 = 5 = Fib_5 -> 1000, 6 = 1+5 = Fib_2 + Fib_5 -> 1001, etc.
References
- Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990.
- Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.3, p. 169.
- Edouard 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
- T. D. Noe and Harry J. Smith, Table of n, a(n) for n = 0..10000
- Paul Dalenberg and Tom Edgar, Consecutive factorial base Niven numbers, Fibonacci Quart., Vol. 56, No. 2 (2018), pp. 163-166.
- Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, 43 pages, no date, apparently unpublished. See Table 2.
- Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, unpublished, no date. [Cached copy, with permission]
- Donald E. Knuth, Fibonacci multiplication, Appl. Math. Lett., Vol. 1, No. 1 (1988), pp. 57-60.
- Julien Leroy, Michel Rigo and Manon Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Mathematics, Vol. 340, No. 5 (2017), pp. 862-881.
- Casey Mongoven, Zeckendorf Representations no. 17 (a musical composition with A014417).
- Wikipedia, Zeckendorf's theorem.
Crossrefs
Programs
-
Haskell
a014417 0 = 0 a014417 n = foldl (\v z -> v * 10 + z) 0 $ a189920_row n -- Reinhard Zumkeller, Mar 10 2013
-
Maple
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 >= A000045(i) and nshi > 0 then Z := [1,op(Z)] ; nshi := nshi-A000045(i) ; else Z := [0,op(Z)] ; end if; end do: add( op(i,Z)*10^(i-1),i=1..nops(Z)) ; end proc: # R. J. Mathar, Jan 31 2015
-
Mathematica
fb[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n * Sqrt[5]]], t = n, fr = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[fr, 1]; t = t - Fibonacci[k], AppendTo[fr, 0]]; k-- ]; FromDigits[fr]]; Table[ fb[n], {n, 0, 30}] (* Robert G. Wilson v, May 15 2004 *) r = Map[Fibonacci, Range[2, 12]]; Table[Total[FromDigits@ PadRight[{1}, Flatten@ #] &@ Reverse@ Position[r, #] & /@ Abs@ Differences@ NestWhileList[Function[k, k - SelectFirst[Reverse@ r, # < k &]], n + 1, # > 1 &]], {n, 0, 33}] (* Michael De Vlieger, Mar 27 2016, Version 10 *) FromDigits/@Select[Tuples[{0,1},7],SequenceCount[#,{1,1}]==0&] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Aug 14 2019 *) -
PARI
Zeckendorf(n)=my(k=0,v,m); while(fibonacci(k)<=n,k=k+1); m=k-1; v=vector(m-1); v[1]=1; n=n-fibonacci(k-1); while(n>0,k=0; while(fibonacci(k)<=n,k=k+1); v[m-k+2]=1; n=n-fibonacci(k-1)); v \\ Ralf Stephan
-
PARI
Zeckendorf(n)= { local(k); a=0; while(n>0, k=0; while(fibonacci(k)<=n, k=k+1); a=a+10^(k-3); n=n-fibonacci(k-1); ); a } { for (n=0, 10000, Zeckendorf(n); print(n," ",a); write("b014417.txt", n, " ", a) ) } \\ Harry J. Smith, Jan 17 2009 -
Python
from sympy import fibonacci def a(n): k=0 x=0 while n>0: k=0 while fibonacci(k)<=n: k+=1 x+=10**(k - 3) n-=fibonacci(k - 1) return x print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 07 2017, after PARI code by Harry J. Smith
Extensions
Comment layout fixed by Daniel Forgues, Dec 07 2009
Typo corrected by Daniel Forgues, Mar 25 2010
Definition expanded and Duchene et al. reference added by N. J. A. Sloane, Aug 07 2018
Name corrected by Michel Dekking, Nov 30 2020
A003622 The Wythoff compound sequence AA: a(n) = floor(n*phi^2) - 1, where phi = (1+sqrt(5))/2.
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
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
- A.H.M. Smeets, Table of n, a(n) for n = 1..20000 (terms 1.1000 from T. D. Noe)
- J.-P. Allouche and F. M. Dekking, Generalized Beatty sequences and complementary triples, arXiv:1809.03424 [math.NT], 2018.
- Jon Asier Bárcena-Petisco, Luis Martínez, María Merino, Juan Manuel Montoya, and Antonio Vera-López, Fibonacci-like partitions and their associated piecewise-defined permutations, arXiv:2503.19696 [math.CO], 2025. See p. 4.
- A. Brousseau, Fibonacci and Related Number Theoretic Tables, Fibonacci Association, San Jose, CA, 1972, p. 62.
- Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, February 2012. - _N. J. A. Sloane_, Jun 10 2012
- Aviezri S. Fraenkel, The Raleigh game, INTEGERS: Electronic Journal of Combinatorial Number Theory 7.2 (2007): A13, 10 pages. See Table 1.
- Martin Griffiths, On a Matrix Arising from a Family of Iterated Self-Compositions, Journal of Integer Sequences, 18 (2015), Article 15.11.8.
- V. E. Hoggatt, Jr., 7-page typed letter to N. J. A. Sloane with suggestions for new sequences, circa 1977.
- Clark Kimberling, Interspersions.
- Clark Kimberling, Complementary equations and Wythoff Sequences, JIS 11 (2008), Article 08.3.3.
- Clark Kimberling, Lucas Representations of Positive Integers, J. Int. Seq., Vol. 23 (2020), Article 20.9.5.
- Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
- Clark Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
- Johan Kok, Integer sequences with conjectured relation with certain graph parameters of the family of linear Jaco graphs, arXiv:2507.16500 [math.CO], 2025. See pp. 5-6.
- L. Lindroos, A. Sills, and H. Wang, Odd fibbinary numbers and the golden ratio, Fib. Q., 52 (2014), 61-65.
- A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See page 3.
- Mathematics Stack Exchange, Golden ratio and floor function floor(phi^2*n) - floor(phi*floor(phi*n)) = 1.
- M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.5.
- N. J. A. Sloane, Classic Sequences
- N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
- Jiemeng Zhang, Zhixiong Wen, and Wen Wu, Some Properties of the Fibonacci Sequence on an Infinite Alphabet, Electronic Journal of Combinatorics, 24(2) (2017), Article P2.52.
Crossrefs
Positions of 1's in A003849.
Complement of A022342.
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]
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
A005206 Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.
0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47
Offset: 0
Comments
Rule for finding n-th term: a(n) = An, where An denotes the Fibonacci antecedent to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58) = 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002
From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):
14 15 16 17 18 19 20 21
\ / / \ / \ / /
9 10 11 12 13
\ / / \ /
6 7 8
\ / /
\ / /
\ / /
4 5
\ /
\ /
\ /
\ /
\ /
3
/
2
\ /
1
To construct the tree: node n is connected with the node a(n) below
n
/
a(n)
For example, since a(7) = 4:
7
/
4
If the nodes of the tree are read from bottom to top, left to right, one obtains the positive integers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the construct
/
x
\ /
x
can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.,
/
x
/ \ /
x x
\ / /
x x
\ /
\ /
x
When moving from a node to a lower connected node, one is moving to the parent. Parent node of n: floor((n+1)/tau). Left child of n: floor(tau*n). Right child of n: floor(tau*(n+1))-1 where tau=(1+sqrt(5))/2. (See the Sillke link.)
(End)
The number n appears A001468(n) times; A001468(n) = floor((n+1)*Phi) - floor(n*Phi) with Phi = (1 + sqrt 5)/2. - Philippe Deléham, Sep 22 2005
Number of positive Wythoff A-numbers A000201 not exceeding n. - N. J. A. Sloane, Oct 09 2006
Number of positive Wythoff B-numbers < A000201(n+1). - N. J. A. Sloane, Oct 09 2006
From Bernard Schott, Apr 23 2022: (Start)
Properties coming from the 1st problem proposed during the 45th Czech and Slovak Mathematical Olympiad in 1996 (see IMO Compendium link):
-> a(n) >= a(n-1) for any positive integer n,
-> a(n) - a(n-1) belongs to {0,1},
-> No integer n exists such that a(n-1) = a(n) = a(n+1). (End)
For n >= 1, find n in the Wythoff array (A035513). a(n) is the number that precedes n in its row, using the preceding column of the extended Wythoff array (A287870) if n is at the start of the (unextended) row. - Peter Munn, Sep 17 2022
See my 2023 publication on Hofstadter's G-sequence for a proof of the equality of (a(n)) with the sequence A073869. - Michel Dekking, Apr 28 2024
From Michel Dekking, Dec 16 2024: (Start)
Focus on the pairs of duplicate values, i.e., the pairs (a(n-1),a(n)) with a(n-1) = a(n). Directly from Theorem 1 in Kimberling and Stolarsky (2016) one derives that the m-th pair of duplicate values (a(n-1),a(n)) occurs at n = U(m), where U = 2,5,7,10,... is the upper Wythoff sequence. For example, (3,3) is the second pair, and occurs at U(2) = 5.
This property can be used to give a simple construction for (a(n)) -- ignoring the superfluous a(0) = 0.
Let 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,... be the sequence of positive natural numbers. Double all the elements of the lower Wythoff sequence (L(n)) = 1,3,4,6,8,9,11,....:
(x(n)) := 1,1, 2, 3,3, 4,4, 5, 6,6, 7, 8,8, 9,9, 10,....
Claim: the result is (a(n)). This follows since because of the doubling, the m-th pair of duplicate values (a(n-1),a(n)) occurs in x at n = L(m) + m = U(m). The second equality by a well-known formula.
It follows from this by Theorem 1 of K&S, that a(n-1) = x(n-1), and a(n) = x(n) if n = U(m), for all m. But since L and U are complementary sequences, a(n) = x(n) will also hold if n = L(k), for all k. For example, L(4) = 6, and a(6) = x(6) = 4.
Corollary: for n >= 2 replace every pair of duplicate values (a(n-1),a(n)) by 0, and all the remaining elements of (a(n)) by 1. Then the result is the Fibonacci word 0,1,0,0,1,0,1,0,0... This is implied by the fact that L gives the positions of the 0s, and U the position of the 1's in the Fibonacci word. (End)
For all n >= 0, a(n) <= A005374(n), as proved in Letouzey-Li-Steiner link. Last equality occurs at n = 12, while a(n) < A005374(n) afterwards. - Pierre Letouzey, Feb 20 2025
References
- D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
- N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Links
- N. J. A. Sloane and T. D. Noe, Table of n, a(n) for n = 0..20000 (the first 1000 terms were found by T. D. Noe)
- L. Carlitz, Fibonacci Representations, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220. a(n) = e(n) at equation 1.10 or 2.11 and see equation 3.8 recurrence.
- M. Celaya and F. Ruskey, Morphic Words and Nested Recurrence Relations, arXiv preprint arXiv:1307.0153 [math.CO], 2013.
- M. Celaya and F. Ruskey, Another Property of Only the Golden Ratio, American Mathematical Monthly, Problem 11651, solutions volume 121, number 6, June-July 2014, pages 549-556.
- F. Michel Dekking, Morphisms, Symbolic Sequences, and Their Standard Forms, Journal of Integer Sequences, Vol. 19 (2016), Article 16.1.1.
- F. M. Dekking, On Hofstadter's G-sequence, Journal of Integer Sequences 26 (2023), Article 23.9.2, 1-11.
- Larry Ericksen and Peter G. Anderson, Patterns in differences between rows in k-Zeckendorf arrays, The Fibonacci Quarterly, Vol. 50, No. 1 (February 2012), pp. 11-18.
- 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. Also annotated scanned copy.
- Martin Griffiths, A formula for an infinite family of Fibonacci-word sequences, Fib. Q., 56 (2018), 75-80.
- H. W. Gould, J. B. Kim and V. E. Hoggatt, Jr., Sequences associated with t-ary coding of Fibonacci's rabbits, Fib. Quart., 15 (1977), 311-318.
- Vincent Granville and Jean-Paul Rasson, A strange recursive relation, J. Number Theory 30 (1988), no. 2, 238--241. MR0961919(89j:11014).
- J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
- Nick Hobson, Python program for this sequence
- D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
- D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]
- D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991
- The IMO Compendium, Problem 1, 45th Czech and Slovak Mathematical Olympiad 1996.
- Clark Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
- Pierre Letouzey, Hofstadter's problem for curious readers, Technical Report, 2015.
- Pierre Letouzey, S. Li and W. Steiner, Pointwise order of generalized Hofstadter functions G,H and beyond, arXiv:2410.00529 [cs.DM], 2024.
- Pierre Letouzey, Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy arXiv:2502.12615 [cs.DM], 2025.
- Mustazee Rahman, A Combinatorial interpretation of Hofstadter's G-sequence, arXiv:1105.1718 [math.CO], 2011-2013.
- B. Schoenmakers, A tight lower bound for top-down skew heaps, Information Processing Letters, 61(5): 279-284, 14 March 1997.
- Torsten Sillke, Floor Recurrences
- Th. Stoll, On Hofstadter's married functions, Fib. Q., 46/47 (2008/2009), 62-67. - _N. J. A. Sloane_, May 30 2009
- Eric Weisstein's World of Mathematics, Hofstadter G-Sequence
- Wikipedia, Hofstadter sequence
- Index entries for Hofstadter-type sequences
- Index entries for sequences from "Goedel, Escher, Bach"
- Index to sequences related to Olympiads.
Crossrefs
Programs
-
Haskell
a005206 n = a005206_list !! n a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list) -- Reinhard Zumkeller, Feb 02 2012, Aug 07 2011
-
Haskell
a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1) -- Reinhard Zumkeller, Mar 10 2013
-
Magma
[Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // Vincenzo Librandi, Nov 19 2016
-
Maple
H:=proc(n) option remember; if n=0 then 0 elif n=1 then 1 else n-H(H(n-1)); fi; end proc: seq(H(n),n=0..76);
-
Mathematica
a[0] = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0] (* Second program: *) Fold[Append[#1, #2 - #1[[#1[[#2]] + 1 ]] ] &, {0}, Range@ 76] (* Michael De Vlieger, Nov 13 2017 *) -
PARI
first(n)=my(v=vector(n)); v[1]=1; for(k=2,n, v[k]=k-v[v[k-1]]); concat(0,v) \\ Charles R Greathouse IV, Sep 02 2015
-
Python
from math import isqrt def A005206(n): return (n+1+isqrt(5*(n+1)**2)>>1)-n-1 # Chai Wah Wu, Aug 09 2022
Formula
a(n) = floor((n+1)*tau) - n - 1 = A000201(n+1)-n-1, where tau = (1+sqrt(5))/2; or a(n) = floor(sigma*(n+1)) where sigma = (sqrt(5)-1)/2.
a(0)=0, a(1)=1, a(n) = n - a(floor(n/tau)). - Benoit Cloitre, Nov 27 2002
a(n) = A019446(n) - 1. - Reinhard Zumkeller, Feb 02 2012
a(n) = n - A060144(n+1). - Reinhard Zumkeller, Apr 07 2012
a(n) = Sum_{k=1..A072649(m)} A000045(m)*A213676(m,k): m=A000201(n+1). - Reinhard Zumkeller, Mar 10 2013
From Pierre Letouzey, Sep 09 2015: (Start)
a(n + a(n)) = n.
a(n) + a(a(n+1) - 1) = n.
a(0) = 0, a(n+1) = a(n) + d(n) and d(0) = 1, d(n+1)=1-d(n)*d(a(n)). (End)
a(n) = A293688(n)/(n+1) for n >= 0 (conjectured). - Enrique Navarrete, Oct 15 2017
A generalization of Diego Torres's 2002 comment as a formula: if n = Sum_{i in S} A000045(i+1), where S is a set of positive integers, then a(n) = Sum_{i in S} A000045(i). - Peter Munn, Sep 28 2022
Conjectures from Chunqing Liu, Aug 01 2023: (Start)
a(A000201(n)-1) = n-1.
Extensions
a(0) = 0 added in the Name by Bernard Schott, Apr 23 2022
A005614 The binary complement of the infinite Fibonacci word A003849. Start with 1, apply 0->1, 1->10, iterate, take limit.
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
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
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
- T. D. Noe, Table of n, a(n) for n = 0..10945 (19 iterations)
- Ricardo Gómez Aíza, Symbolic dynamical scales: modes, orbitals, and transversals, arXiv:2009.02669 [math.DS], 2020.
- F. Axel et al., Vibrational modes in a one dimensional "quasi-alloy": the Morse case, J. de Physique, Colloq. C3, Supp. to No. 7, Vol. 47 (Jul 1986), pp. C3-181-C3-186; see Eq. (10).
- Joerg Arndt, Matters Computational (The Fxtbook), 753-754.
- E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183. (Annotated scanned copy)
- M. Bunder and K. Tognetti, On the self matching properties of [j tau], Discrete Math., 241 (2001), 139-151.
- J. T. Butler, Letter to N. J. A. Sloane, Dec. 1978.
- Glen Joyce C. Dulatre, Jamilah V. Alarcon, Vhenedict M. Florida, and Daisy Ann A. Disu, On Fractal Sequences, DMMMSU-CAS Science Monitor (2016-2017) Vol. 15 No. 2, 109-113.
- S. Dulucq and D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm, Theoret. Comput. Sci. 71 (1990), 381-400.
- M. S. El Naschie, Statistical geometry of a Cantor discretum and semiconductors, Computers & Mathematics with Applications, Vol. 29 (Issue 12, June 1995), 103-110.
- 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.
- D. Gault and M. Clint, "Curiouser and curiouser said Alice. Further reflections on an interesting recursive function, Intern. J. Computer. Math., 26 (1988), 35-43. (Annotated scanned copy)
- J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
- Clark Kimberling, Intriguing infinite words composed of zeros and ones, Elemente der Mathematik (2021).
- Clark Kimberling and K. B. Stolarsky, Slow Beatty sequences, devious convergence, and partitional divergence, Amer. Math. Monthly, 123 (No. 2, 2016), 267-273.
- K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)
- Ron Knott, The Fibonacci Rabbit Sequence
- Wolfdieter Lang, The Tribonacci and ABC Representations of Numbers are Equivalent, arXiv preprint arXiv:1810.09787 [math.NT], 2018.
- G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
- S. Mneimneh, Fibonacci in The Curriculum: Not Just a Bad Recurrence, in Proceeding SIGCSE '15 Proceedings of the 46th ACM Technical Symposium on Computer Science Education, 253-258.
- C. Mongoven, The Rabbit Sequence (a musical composition with A005614).
- T. D. Noe, The first 1652 subwords, including leading zeros.
- José L. Ramírez, Gustavo N. Rubiano, and Rodrigo de Castro, A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake, arXiv preprint arXiv:1212.1368 [cs.DM], 2012-2014.
- Jeffrey Shallit, Characteristic words as fixed points of homomorphisms, University of Waterloo Technical Report CS-91-72, 1991.
- Jeffrey Shallit, Characteristic words as fixed points of homomorphisms. [Cached copy, with permission]
- N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
- K. B. Stolarsky, Beatty sequences, continued fractions and certain shift operators, Canad. Math. Bull., 19 (1976), 473-482.
- Scott V. Tezlaf, On ordinal dynamics and the multiplicity of transfinite cardinality, arXiv:1806.00331 [math.NT], 2018. See p. 10.
- Eric Weisstein's World of Mathematics, Rabbit Constant and Rabbit Sequence.
- Index entries for characteristic functions
- Index entries for sequences that are fixed points of mappings
Crossrefs
Binary complement of A003849, which is the standard form of this sequence.
Cf. A000045 (Fibonacci numbers), A001468, A001911, A005206 (partial sums), A014565, A014675, A022342, A036299, A044432, A221150, A221151, A221152.
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
A289780 p-INVERT of the positive integers (A000027), where p(S) = 1 - S - S^2.
1, 4, 14, 47, 156, 517, 1714, 5684, 18851, 62520, 207349, 687676, 2280686, 7563923, 25085844, 83197513, 275925586, 915110636, 3034975799, 10065534960, 33382471801, 110713382644, 367182309614, 1217764693607, 4038731742156, 13394504020957, 44423039068114
Offset: 0
Comments
Suppose s = (c(0), c(1), c(2), ...) is a sequence and p(S) is a polynomial. Let S(x) = c(0)*x + c(1)*x^2 + c(2)*x^3 + ... and T(x) = (-p(0) + 1/p(S(x)))/x. The p-INVERT of s is the sequence t(s) of coefficients in the Maclaurin series for T(x).
Taking p(S) = 1 - S gives the INVERT transform of s, so that p-INVERT is a generalization of the INVERT transform (e.g., A033453).
Guide to p-INVERT sequences using p(S) = 1 - S - S^2:
Examples
Example 1: s = (1,2,3,4,5,6,...) = A000027 and p(S) = 1 - S. S(x) = x + 2x^2 + 3x^3 + 4x^4 + ... p(S(x)) = 1 - (x + 2x^2 + 3x^3 + 4x^4 + ... ) - p(0) + 1/p(S(x)) = -1 + 1 + x + 3x^2 + 8x^3 + 21x^4 + ... T(x) = 1 + 3x + 8x^2 + 21x^3 + ... t(s) = (1,3,8,21,...) = A001906. *** Example 2: s = (1,2,3,4,5,6,...) = A000027 and p(S) = 1 - S - S^2. S(x) = x + 2x^2 + 3x^3 + 4x^4 + ... p(S(x)) = 1 - ( x + 2x^2 + 3x^3 + 4x^4 + ...) - ( x + 2x^2 + 3x^3 + 4x^4 + ...)^2 - p(0) + 1/p(S(x)) = -1 + 1 + x + 4x^2 + 14x^3 + 47x^4 + ... T(x) = 1 + 4x + 14x^2 + 47x^3 + ... t(s) = (1,4,14,47,...) = A289780.
Links
- Clark Kimberling, Table of n, a(n) for n = 0..1000
- Index entries for linear recurrences with constant coefficients, signature (5, -7, 5, -1)
Crossrefs
Cf. A000027.
Programs
-
GAP
P:=[1,4,14,47];; for n in [5..10^2] do P[n]:=5*P[n-1]-7*P[n-2]+5*P[n-3]-P[n-4]; od; P; # Muniru A Asiru, Sep 03 2017
-
Mathematica
z = 60; s = x/(1 - x)^2; p = 1 - s - s^2; Drop[CoefficientList[Series[s, {x, 0, z}], x], 1] (* A000027 *) Drop[CoefficientList[Series[1/p, {x, 0, z}], x], 1] (* A289780 *) -
PARI
x='x+O('x^99); Vec((1-x+x^2)/(1-5*x+7*x^2-5*x^3+x^4)) \\ Altug Alkan, Aug 13 2017
Formula
G.f.: (1 - x + x^2)/(1 - 5 x + 7 x^2 - 5 x^3 + x^4).
a(n) = 5*a(n-1) - 7*a(n-2) + 5*a(n-3) - a(n-4).
A001611 a(n) = Fibonacci(n) + 1.
1, 2, 2, 3, 4, 6, 9, 14, 22, 35, 56, 90, 145, 234, 378, 611, 988, 1598, 2585, 4182, 6766, 10947, 17712, 28658, 46369, 75026, 121394, 196419, 317812, 514230, 832041, 1346270, 2178310, 3524579, 5702888, 9227466, 14930353, 24157818, 39088170, 63245987, 102334156
Offset: 0
Comments
a(0) = 1, a(1) = 2 then the largest number such that a triangle is constructible with three successive terms as sides. - Amarnath Murthy, Jun 03 2003
a(n+2) = A^(n)B(1), n>=0, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 2=`0`, 3=`10`, 4=`110`, 6=`1110`, ..., in Wythoff code.
The first-difference sequence is the Fibonacci sequence (A000045). - Roland Schroeder (florola(AT)gmx.de), Aug 05 2010
2 and 3 are the only primes in this sequence.
a(n) is the number of 1 X n nonogram puzzles which can be solved uniquely. See A242876 for puzzle definition. - Lior Manor, Jan 23 2022
References
- G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
- 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
- Vincenzo Librandi, Table of n, a(n) for n = 0..250
- Andrei Asinowski, Cyril Banderier and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).
- K.-W. Chen, Greatest Common Divisors in Shifted Fibonacci Sequences, J. Int. Seq. 14 (2011) # 11.4.7.
- Massimiliano Fasi and Gian Maria Negri Porzio, Determinants of Normalized Bohemian Upper Hessemberg Matrices, University of Manchester (England, 2019).
- Martin Griffiths, On a Matrix Arising from a Family of Iterated Self-Compositions, Journal of Integer Sequences, 18 (2015), #15.11.8.
- R. K. Guy and N. J. A. Sloane, Correspondence, 1988.
- Fumio Hazama, Spectra of graphs attached to the space of melodies, Discr. Math., 311 (2011), 2368-2383. See Table 5.1.
- INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 402
- Dov Jarden, Recurring Sequences, Riveon Lematematika, Jerusalem, 1966. [Annotated scanned copy] See p. 97.
- N. S. Mendelsohn, Permutations with confined displacement, Canad. Math. Bull., 4 (1961), 29-38.
- Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
- Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
- Index entries for linear recurrences with constant coefficients, signature (2,0,-1).
Crossrefs
Programs
-
Haskell
a001611 = (+ 1) . a000045 a001611_list = 1 : 2 : map (subtract 1) (zipWith (+) a001611_list $ tail a001611_list) -- Reinhard Zumkeller, Jul 30 2013 -
Magma
[Fibonacci(n)+1: n in [1..37]]; // Bruno Berselli, Jul 26 2011
-
Maple
A001611:=-(-1+2*z**2)/(z-1)/(z**2+z-1); # Simon Plouffe in his 1992 dissertation with(combinat): seq((fibonacci(n)+1), n=0..35);
-
Mathematica
a[0] = 1; a[1] = 2; a[n_] := a[n] = a[n-2] + a[n-1] - 1; Table[ a[n], {n, 0, 40} ] Fibonacci[Range[0,50]]+1 (* Harvey P. Dale, Mar 23 2011 *) -
PARI
a(n)=fibonacci(n)+1 \\ Charles R Greathouse IV, Jul 25 2011
Formula
G.f.: (1-2*x^2)/(1-2*x+x^3).
a(n) = 2*a(n-1) - a(n-3). - Tanya Khovanova, Jul 13 2007
a(0) = 1, a(1) = 2, a(n) = a(n - 2) + a(n - 1) - 1.
F(4*n) + 1 = F(2*n-1)*L(2*n+1); F(4*n+1) + 1 = F(2*n+1)*L(2*n); F(4*n+2) + 1 = F(2*n+2)*L(2*n); F(4*n+3) + 1 = F(2*n+1)*L(2*n+2) where F(n)=Fibonacci(n) and L(n)=Lucas(n). - R. K. Guy, Feb 27 2003
a(1) = 2; a(n+1)=floor(a(n)*(sqrt(5)+1)/2). - Roland Schroeder (florola(AT)gmx.de), Aug 05 2010
a(n) = Sum_{k=0..n+1} Fibonacci(k-3). - Ehren Metcalfe, Apr 15 2019
Product_{n>=1} (1 - (-1)^n/a(n)) = sin(3*Pi/10) (A019863). - Amiram Eldar, Nov 28 2024
A027941 a(n) = Fibonacci(2*n + 1) - 1.
0, 1, 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, 75024, 196417, 514228, 1346268, 3524577, 9227464, 24157816, 63245985, 165580140, 433494436, 1134903169, 2971215072, 7778742048, 20365011073, 53316291172, 139583862444, 365435296161, 956722026040
Offset: 0
Comments
Also T(2n+1,n+1), T given by A027935. Also first row of Inverse Stolarsky array.
Third diagonal of array defined by T(i, 1)=T(1, j)=1, T(i, j)=Max(T(i-1, j)+T(i-1, j-1); T(i-1, j-1)+T(i, j-1)). - Benoit Cloitre, Aug 05 2003
Number of Schroeder paths of length 2(n+1) having exactly one up step starting at an even height (a Schroeder path is a lattice path starting from (0,0), ending at a point on the x-axis, consisting only of steps U=(1,1) (up steps), D=(1,-1) (down steps) and H=(2,0) (level steps) and never going below the x-axis). Schroeder paths are counted by the large Schroeder numbers (A006318). Example: a(1)=4 because among the six Schroeder paths of length 4 only the paths (U)HD, (U)UDD, H(U)D, (U)DH have exactly one U step that starts at an even height (shown between parentheses). - Emeric Deutsch, Dec 19 2004
Also: smallest number not writeable as the sum of fewer than n positive Fibonacci numbers. E.g., a(5)=88 because it is the smallest number that needs at least 5 Fibonacci numbers: 88 = 55 + 21 + 8 + 3 + 1. - Johan Claes, Apr 19 2005 [corrected for offset and clarification by Mike Speciner, Sep 19 2023] In general, a(n) is the sum of n positive Fibonacci numbers as a(n) = Sum_{i=1..n} A000045(2*i). See A001076 when negative Fibonacci numbers can be included in the sum. - Mike Speciner, Sep 24 2023
Except for first term, numbers a(n) that set a new record in the number of Fibonacci numbers needed to sum up to n. Position of records in sequence A007895. - Ralf Stephan, May 15 2005
Successive extremal petal bends beta(n) = a(n-2). See the Ring Lemma of Rodin and Sullivan in K. Stephenson, Introduction to Circle Packing (Cambridge U. P., 2005), pp. 73-74 and 318-321. - David W. Cantrell (DWCantrell(AT)sigmaxi.net)
a(n+1)= AAB^(n)(1), n>=1, with compositions of Wythoff's complementary A(n):=A000201(n) and B(n)=A001950(n) sequences. See the W. Lang link under A135817 for the Wythoff representation of numbers (with A as 1 and B as 0 and the argument 1 omitted). E.g., 4=`110`, 12=`1100`, 33=`11000`, 88=`110000`, ..., in Wythoff code. AA(1)=1=a(1) but for uniqueness reason 1=A(1) in Wythoff code. - N. J. A. Sloane, Jun 29 2008
Start with n. Each n generates a sublist {n-1,n-1,n-2,..,1}. Each element of each sublist also generates a sublist. Add numbers in all terms. For example, 3->{2,2,1} and both 2->{1,1}, so a(3) = 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 = 12. - Jon Perry, Sep 01 2012
For n>0: smallest number such that the inner product of Zeckendorf binary representation and its reverse equals n: A216176(a(n)) = n, see also A189920. - Reinhard Zumkeller, Mar 10 2013
Also, numbers m such that 5*m*(m+2)+1 is a square. - Bruno Berselli, May 19 2014
Also, number of nonempty submultisets of multisets of weight n that span an initial interval of integers (see 2nd example). - Gus Wiseman, Feb 10 2015
From Robert K. Moniot, Oct 04 2020: (Start)
Including a(-1):=0, consecutive terms (a(n-1),a(n))=(u,v) or (v,u) give all points on the hyperbola u^2-u+v^2-v-4*u*v=0 with both coordinates nonnegative integers. Note that this follows from identifying (1,u+1,v+1) with the Markov triple (1,Fibonacci(2n-1),Fibonacci(2n+1)). See A001519 (comments by Robert G. Wilson, Oct 05 2005, and Wolfdieter Lang, Jan 30 2015).
Let T(n) denote the n-th triangular number. If i, j are any two successive elements of the above sequence then (T(i-1) + T(j-1))/T(i+j-1) = 3/5. (End)
Examples
a(5) = 88 = 2*33 + 12 + 4 + 1 + 5. a(6) = 232 = 2*88 + 33 + 12 + 4 + 1 + 6. - _Jon Perry_, Sep 01 2012 a(4) = 33 counts all nonempty submultisets of the last row: [1][2][3][4], [11][12][13][14][22][23][24][33][34], [111][112][113][122][123][124][133][134][222][223][233][234], [1111][1112][1122][1123][1222][1223][1233][1234]. - _Gus Wiseman_, Feb 10 2015
References
- A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 12.
Links
- T. D. Noe, Table of n, a(n) for n = 0..200
- R. C. Alperin, A nonlinear recurrence and its relations to Chebyshev polynomials, Fib. Q., Vol. 58, No. 2 (2020), 140-142.
- Russ Euler and Jawad Sadek, Problem B-912, Elementary Problems and Solutions, The Fibonacci Quarterly, Vol. 39, No. 1 (2001), p. 85; From a Product to a Sum, Solution to Problem B-912 by Charles K. Cook, ibid., Vol. 39, No. 5 (2001), pp. 468-469.
- Sela Fried, Even-up words and their variants, arXiv:2505.14196 [math.CO], 2025. See p. 7.
- Clark Kimberling, Interspersions.
- Clark Kimberling, Interspersions and dispersions, Proceedings of the American Mathematical Society, 117 (1993) 313-321.
- Ioana-Claudia Lazăr, Lucas sequences in t-uniform simplicial complexes, arXiv:1904.06555 [math.GR], 2019.
- R. J. Mathar, Paving rectangular regions with rectangular tiles: tatami and non-tatami tilings, arXiv:1311.6135 [math.CO], 2013, Table 60 (doubled).
- Luis A. Medina and Armin Straub, On multiple and infinite log-concavity, Annals of Combinatorics, Vol. 20, No. 1 (2016), pp. 125-138; arXiv preprint, arXiv:1405.1765 [math.CO], 2014; preprint, 2014.
- László Németh, Hyperbolic Pascal pyramid, arXiv:1511.02067 [math.CO], 2015 (2nd line of Table 1 is 3*a(n-2)).
- László Németh, Pascal pyramid in the space H^2×R, arXiv:1701.06022 [math.CO], 2016. See bn in Table 1 p.10.
- N. J. A. Sloane, Classic Sequences.
- Index entries for sequences related to Chebyshev polynomials.
- Index entries for linear recurrences with constant coefficients, signature (4,-4,1).
Crossrefs
Programs
-
Haskell
a027941 = (subtract 1) . a000045 . (+ 1) . (* 2) -- Reinhard Zumkeller, Mar 10 2013
-
Magma
[Fibonacci(2*n+1)-1: n in [0..30]]; // Vincenzo Librandi, Apr 18 2011
-
Maple
with(combinat): seq(fibonacci(2*n+1)-1,n=1..27); # Emeric Deutsch, Dec 19 2004 a:=n->sum(binomial(n+k+1,2*k), k=0..n): seq(a(n), n=-1..26); # Zerinvary Lajos, Oct 02 2007
-
Mathematica
Table[Fibonacci[2*n+1]-1,{n,0,17}] (* Vladimir Joseph Stephan Orlovsky, Jul 21 2008 *) LinearRecurrence[{4,-4,1},{0,1,4},40] (* Harvey P. Dale, Aug 17 2021 *) -
Maxima
a(n):=sum(binomial(n+1,k+1)*fib(k),k,0,n); /* Vladimir Kruchinin, Oct 14 2016 */
-
PARI
a(n)=fibonacci(2*n+1)-1 \\ Charles R Greathouse IV, Nov 20 2012
-
PARI
concat(0, Vec(x/((1-x)*(1-3*x+x^2)) + O(x^40))) \\ Colin Barker, Jun 03 2016
Formula
a(n) = Sum_{i=1..n} binomial(n+i, n-i). - Benoit Cloitre, Oct 15 2002
G.f.: Sum_{k>=1} x^k/(1-x)^(2*k+1). - Benoit Cloitre, Apr 21 2003
a(n) = Sum_{k=1..n} F(2*k), i.e., partial sums of A001906. - Benoit Cloitre, Oct 27 2003
a(n) = Sum_{k=0..n-1} U(k, 3/2) = Sum_{k=0..n-1} S(k, 3), with S(k, 3) = A001906(k+1). - Paul Barry, Nov 14 2003
G.f.: x/((1-x)*(1-3*x+x^2)) = x/(1-4*x+4*x^2-x^3).
a(n) = 4*a(n-1) - 4*a(n-2) + a(n-3) with n>=2, a(-1)=0, a(0)=0, a(1)=1.
a(n) = 3*a(n-1) - a(n-2) + 1 with n>=1, a(-1)=0, a(0)=0.
a(n) = Sum_{k=1..n} F(k)*L(k), where L(k) = Lucas(k) = A000032(k) = F(k-1) + F(k+1). - Alexander Adamchuk, May 18 2007
a(n) = 2*a(n-1) + (Sum_{k=1..n-2} a(k)) + n. - Jon Perry, Sep 01 2012
Sum {n >= 1} 1/a(n) = 3 - phi, where phi = 1/2*(1 + sqrt(5)) is the golden ratio. The ratio of adjacent terms r(n) := a(n)/a(n-1) satisfies the recurrence r(n+1) = (4*r(n) - 1)/(r(n) + 1) for n >= 2. - Peter Bala, Dec 05 2013
a(n) = S(n, 3) - S(n-1, 3) - 1, n >= 0, with Chebyshev's S-polynomials (see A049310), where S(-1, x) = 0. - Wolfdieter Lang, Aug 28 2014
a(n) = -1 + (2^(-1-n)*((3-sqrt(5))^n*(-1+sqrt(5)) + (1+sqrt(5))*(3+sqrt(5))^n)) / sqrt(5). - Colin Barker, Jun 03 2016
E.g.f.: (sqrt(5)*sinh(sqrt(5)*x/2) + 5*cosh(sqrt(5)*x/2))*exp(3*x/2)/5 - exp(x). - Ilya Gutkovskiy, Jun 03 2016
a(n) = Sum_{k=0..n} binomial(n+1,k+1)*Fibonacci(k). - Vladimir Kruchinin, Oct 14 2016
a(n) = Sum_{k=0..n-1} Sum_{i=0..n-1} C(k+i+1,k-i). - Wesley Ivan Hurt, Sep 21 2017
a(n)*a(n-2) = a(n-1)*(a(n-1) - 1) for n>1. - Robert K. Moniot, Aug 23 2020
a(n) = Sum_{k=1..n} C(2*n-k,k). - Wesley Ivan Hurt, Dec 22 2020
a(n) = Sum_{k = 1..2*n+2} (-1)^k*Fibonacci(k). - Peter Bala, Nov 14 2021
a(n) = (2*cosh((1 + 2*n)*arccsch(2)))/sqrt(5) - 1. - Peter Luschny, Nov 21 2021
a(n) = F(n + (n mod 2)) * L(n+1 - (n mod 2)), where L(n) = A000032(n) and F(n) = A000045(n) (Euler and Sadek, 2001). - Amiram Eldar, Jan 13 2022
Extensions
More terms from James Sellers, Sep 08 2000
Paul Barry's Nov 14 2003 formula, recurrences and g.f. corrected for offset 0 and index link for Chebyshev polynomials added by Wolfdieter Lang, Aug 28 2014
Comments
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
Links
Crossrefs
Programs
Maple
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}] // FlattenPARI
Python
Python
Formula
Extensions