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.

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

Author

Marc LeBrun

Keywords

• nonn
• nice
• easy

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

• Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
• Joerg Arndt, Matters Computational (The Fxtbook)
• A. J. Macfarlane, On the fibbinary numbers and the Wythoff array, arXiv:2405.18128 [math.CO], 2024. See pages 3, 6.
• M. Rigo, P. Salimov, and E. Vandomme, Some Properties of Abelian Return Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.5.
• Jeffrey Shallit, The Hurt-Sada Array and Zeckendorf Representations, arXiv:2501.08823 [math.NT], 2025. See p. 2.
• N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
• 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 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