A194029 Natural fractal sequence of the Fibonacci sequence (1, 2, 3, 5, 8, ...).

1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 7, 8, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34

Offset: 1

Author

Clark Kimberling, Aug 12 2011

Keywords

• nonn
• tabf

Comments

Suppose that c(1), c(2), c(3), ... is an increasing sequence of positive integers with c(1) = 1, and that the sequence c(k+1) - c(k) is strictly increasing. The natural fractal sequence f of c is defined by:

If c(k) <= n < c(k+1), then f(n) = 1 + n - c(k).

This defines the present sequence a(n) = f(n) for c = A000045.

The natural interspersion of c is here introduced as the array given by T(n,k) =(position of k-th n in f). Note that c = (row 1 of T).

As a different example from the one considered here (c = A000045), let c = A000217 = (1, 3, 6, 10, 15, ...), the triangular numbers, so that f = (1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ...) = A002260, and a northwest corner of T = A194029 is:

1 3 6 10 15 ...

2 4 7 11 16 ...

5 8 12 17 23 ...

9 13 18 24 31 ...

...

Since every number in the set N of positive integers occurs exactly once in this (and every) interspersion, a listing of the terms of T by antidiagonals comprises a permutation, p, of N; letting q denote the inverse of p, we thus have for each c a fractal sequence, an interspersion T, and two permutations of N:

c f T / p q

A000045 A194029 A194030 A194031

A000290 A071797 A194032 A194033

A000217 A002260 A066182 A066181

A028387 A074294 A194034 A194035

A028872 A071797 A194036 A194037

A034856 A002260 A194038 A194040

It appears that this is also a triangle read by rows in which row n lists the first A000045(n) positive integers, n >= 1 (see example). - Omar E. Pol, May 28 2012

This is true, because the sequence c = A000045 has the property that c(k+1) - c(k) = c(k-1), so the number of integers {1, 2, 3, ...} to be filled in from index n = c(k) to n = c(k+1)-1 is equal to c(k-1); see also the first EXAMPLE. - M. F. Hasler, Apr 23 2022

Examples

			The sequence (1, 2, 3, 5, 8, 13, ...) is used to place '1's in positions numbered 1, 2, 3, 5, 8, 13, ...  Then gaps are filled in with consecutive counting numbers:
  1, 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 5, 1, ...
From _Omar E. Pol_, May 28 2012: (Start)
Written as an irregular triangle the sequence begins:
  1;
  1;
  1, 2;
  1, 2, 3;
  1, 2, 3, 4, 5;
  1, 2, 3, 4, 5, 6, 7, 8;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13;
  1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21; ...
The row lengths are A000045(n).
(End)
		

References

• Clark Kimberling, "Fractal sequences and interspersions," Ars Combinatoria 45 (1997) 157-168.

Links

• Alois P. Heinz, Rows n = 1..20, flattened
• Clark Kimberling, Numeration systems and fractal sequences, Acta Arithmetica 73 (1995) 103-117.

Crossrefs

Cf. A000045 (Fibonacci numbers).

Cf. A066628, A194030, A194031 (natural interspersion of A000045 and inverse permutation).

Cf. A130853.

Programs

Maple

T:= n-> $1..(<<0|1>, <1|1>>^n)[1, 2]:
seq(T(n), n=1..10);  # Alois P. Heinz, Dec 11 2024

Mathematica

z = 40;
c[k_] := Fibonacci[k + 1];
c = Table[c[k], {k, 1, z}]  (* A000045 *)
f[n_] := If[MemberQ[c, n], 1, 1 + f[n - 1]]
f = Table[f[n], {n, 1, 800}]  (* A194029 *)
r[n_] := Flatten[Position[f, n]]
t[n_, k_] := r[n][[k]]
TableForm[Table[t[n, k], {n, 1, 8}, {k, 1, 7}]]
p = Flatten[Table[t[k, n - k + 1], {n, 1, 13}, {k, 1, n}]]  (* A194030 *)
q[n_] := Position[p, n]; Flatten[Table[q[n], {n, 1, 80}]]  (* A194031 *)
Flatten[Range[Fibonacci[Range[66]]]] (* Birkas Gyorgy, Jun 30 2012 *)

Formula

a(n) = A066628(n)+1. - Alan Michael Gómez Calderón, Oct 30 2023

Extensions

Edited by M. F. Hasler, Apr 23 2022