A105774 A "fractal" transform of the Fibonacci numbers: a(1)=1; then if F(n) < k <= F(n+1), a(k) = F(n+1) - a(k - F(n)) where F(n) = A000045(n).

1, 1, 2, 4, 4, 7, 7, 6, 12, 12, 11, 9, 9, 20, 20, 19, 17, 17, 14, 14, 15, 33, 33, 32, 30, 30, 27, 27, 28, 22, 22, 23, 25, 25, 54, 54, 53, 51, 51, 48, 48, 49, 43, 43, 44, 46, 46, 35, 35, 36, 38, 38, 41, 41, 40, 88, 88, 87, 85, 85, 82, 82, 83, 77, 77, 78, 80, 80, 69, 69, 70, 72, 72

Offset

1,3

Comments

Let tau = (1+sqrt(5))/2; then the missing numbers 3,5,8,10,13,16,18,21,... are given by round(tau^2*k) for k > 0 (A004937).

Indices n such that a(n) = a(n+1) are given by floor(tau^2*k) - 1 for k > 0 (A003622).

Numbers n such that a(n) differs from a(n+1) are given by floor(tau*k+1/tau) for k > 0 (A022342).

Indices n giving isolated terms (a(n) differs from a(n-1) and a(n+1)) are given by floor(tau*floor(tau^2*k)) for k > 0 (A003623).

Remove 0's from the first differences of sorted values; then you get a version of the infinite Fibonacci word (A001468). I.e., sorted values are 1,1,2,4,4,6,7,7,9,9,11,12,12,..., first differences are 0,1,2,0,2,1,0,2,0,2,1,0,2,0,1,...; removing 0's gives 1,2,2,1,2,2,1,2,1,2,2,1,2,1,2,2,1,2,... #{ k : a(k)=k}=infty.

Links

Antti Karttunen, Table of n, a(n) for n = 1..10946

Benoit Cloitre and Jeffrey Shallit, Some Fibonacci-Related Sequences, arXiv:2312.11706 [math.CO], 2023.

Jeffrey Shallit, Using automata to prove theorems about sequences, One FLAT World Seminar, 2024.

Formula

a(A000045(n)) = A006498(n-1) for n >= 1. - Typo corrected by Antti Karttunen, Mar 17 2017

limsup a(n)/n = tau and liminf a(n)/n = (tau+2)/5 where tau = (1+sqrt(5))/2. - Corrected by Jeffrey Shallit, Dec 17 2023

a(n) mod 2 = A085002(n) - Benoit Cloitre, May 10 2005

a(1) = 1; for n > 1, a(n) = A000045(2+A072649(n-1)) - a(n-A000045(1 + A072649(n-1))). - Antti Karttunen, Mar 17 2017

Example

For 1 = F(2) < k <= F(3) = 2 the rule gives a(2) = 2 - a(1) = 1 ... if 5 = F(5) < k <= F(6) = 8 the rule forces a(6) = 8 - a(6-5) = 8 - a(1) = 7; a(7) = 8 - a(2) = 7; a(8) = 8 - a(3) = 6.

Prog

(Scheme, with memoization-macro definec)
(definec (A105774 n) (if (= 1 n) n (- (A000045 (+ 2 (A072649 (- n 1)))) (A105774 (- n (A000045 (+ 1 (A072649 (- n 1)))))))))
;; Antti Karttunen, Mar 17 2017

Crossrefs

Cf. A000045, A001468, A003622, A003623, A004937, A006498, A022342, A072649, A085002, A105669, A105670, A105672, A093347, A093348, A283766.

Sequence in context: A274593 A103622 A328853 * A130805 A023831 A233272

Adjacent sequences: A105771 A105772 A105773 * A105775 A105776 A105777

Keyword

nonn

Author

Benoit Cloitre, May 04 2005

Status

approved