A226080 -id:A226080 - cp's OEIS frontend

A226209 Zeckendorf distance between n and n+2.

2, 1, 1, 3, 4, 3, 5, 4, 6, 6, 7, 7, 4, 6, 6, 8, 8, 4, 9, 9, 4, 6, 6, 8, 8, 4, 10, 10, 4, 6, 6, 11, 11, 4, 6, 6, 8, 8, 4, 10, 10, 4, 6, 6, 12, 12, 4, 6, 6, 8, 8, 4, 13, 13, 4, 6, 6, 8, 8, 4, 10, 10, 4, 6, 6, 12, 12, 4, 6, 6, 8, 8, 4, 14, 14, 4, 6, 6, 8, 8, 4

Offset: 1

Clark Kimberling, May 31 2013

Zeckendorf distance is defined at A226207.

			7 = 5 + 2 -> 3 + 1 -> 2, and 9 = 8 + 1 -> 5 -> 3 -> 2.  The total number of Zeckendorf downshifts (i.e., arrows) is 5, so that a(7) = D(7,9) = 5.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A226080, A226207, A226208.

zeck[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n*Sqrt[5]]], t = n, z = {}},    While[k > 1, If[t >= Fibonacci[k], AppendTo[z, 1]; t = t - Fibonacci[k], AppendTo[z, 0]]; k--]; If[n > 0 && z[[1]] == 0, Rest[z], z]]; d[n1_, n2_] := Module[{z1 = zeck[n1], z2 = zeck[n2]}, Length[z1] + Length[z2] - 2 (NestWhile[# + 1 &, 1, z1[[#]] == z2[[#]] &, 1, Min[{Length[z1], Length[z2]}]] - 1)]; lst = Map[d[#, # + 2] &, Range[100]] (* Peter J. C. Moses, May 30 2013 *)

A226210 a(n) is the Zeckendorf distance between n and Fibonacci(n).

Original entry on oeis.org

0, 1, 1, 2, 0, 3, 6, 2, 5, 8, 11, 12, 6, 9, 12, 15, 16, 19, 20, 21, 13, 16, 19, 22, 23, 26, 27, 28, 31, 32, 33, 34, 35, 25, 28, 31, 34, 35, 38, 39, 40, 43, 44, 45, 46, 47, 50, 51, 52, 53, 54, 55, 56, 57, 45, 48, 51, 54, 55, 58, 59, 60, 63, 64, 65, 66, 67, 70

Offset: 1

Clark Kimberling, May 31 2013

Zeckendorf distance is defined at A226207.

			7 = 5 + 2 -> 3 + 1 -> 2, and 13 -> 8 -> 5 -> 3 -> 2. The total number of Zeckendorf downshifts (i.e., arrows) is 6, so that a(7) = D(7,F(7)) = 6.

Clark Kimberling, Table of n, a(n) for n = 1..150

Cf. A226080, A226207, A000045.

zeck[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n*Sqrt[5]]], t = n, z = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[z, 1]; t = t - Fibonacci[k], AppendTo[z, 0]]; k--]; If[n > 0 && z[[1]] == 0, Rest[z], z]]; d[n1_, n2_] := Module[{z1 = zeck[n1], z2 = zeck[n2]}, Length[z1] + Length[z2] - 2 (NestWhile[# + 1 &, 1, z1[[#]] == z2[[#]] &, 1, Min[{Length[z1], Length[z2]}]] - 1)];
lst = Map[d[#, Fibonacci[#]] &, Range[100]] (* Peter J. C. Moses, May 30 2013 *)

A226213 Zeckendorf distance between n and 2^n.

Original entry on oeis.org

1, 1, 2, 5, 7, 7, 6, 7, 12, 14, 17, 12, 17, 22, 20, 25, 25, 28, 30, 31, 33, 31, 36, 34, 39, 39, 32, 42, 45, 42, 48, 45, 51, 51, 43, 54, 57, 55, 60, 52, 63, 63, 60, 66, 63, 70, 72, 67, 75, 70, 78, 79, 81, 82, 84, 82, 87, 83, 88, 86, 91, 94, 88, 97, 89, 100

Offset: 1

Clark Kimberling, May 31 2013

Zeckendorf distance is defined at A226207.

			6 = 5 + 1 -> 3, and 2^6 = 55 + 8 + 1 -> 34 + 5 -> 21 + 3 -> 13 + 2 -> 8 + 1 -> 5 -> 3. The total number of Zeckendorf downshifts (i.e., arrows) is 7, so that a(6) = D(6,64) = 7.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A226080, A226207.

zeck[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n*Sqrt[5]]], t = n, z = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[z, 1]; t = t - Fibonacci[k], AppendTo[z, 0]]; k--]; If[n > 0 && z[[1]] == 0, Rest[z], z]]; d[n1_, n2_] := Module[{z1 = zeck[n1], z2 = zeck[n2]}, Length[z1] + Length[z2] - 2 (NestWhile[# + 1 &, 1, z1[[#]] == z2[[#]] &, 1, Min[{Length[z1], Length[z2]}]] - 1)];
lst = Map[d[#, 2^#] &, Range[100]] (* Peter J. C. Moses, May 30 2013 *)

A226214 Zeckendorf distance between n and n^2.

Original entry on oeis.org

0, 1, 2, 5, 3, 6, 4, 6, 10, 9, 11, 12, 9, 11, 13, 12, 8, 6, 10, 15, 12, 14, 16, 16, 13, 15, 15, 11, 17, 11, 13, 18, 18, 15, 17, 17, 19, 19, 19, 16, 16, 18, 18, 18, 14, 14, 8, 12, 14, 16, 21, 21, 21, 21, 18, 18, 20, 20, 20, 22, 22, 22, 22, 22, 19, 19, 19, 21

Offset: 1

Clark Kimberling, May 31 2013

Zeckendorf distance is defined at A226207.

			7 = 5 + 2, and 7^2 = 34 + 13 + 2 -> 21 + 8 + 1 -> 13 + 5 -> 8 + 3 -> 5 + 2. The total number of Zeckendorf downshifts (i.e., arrows) is 4, so that a(7) = D(7,49) = 4.

Clark Kimberling, Table of n, a(n) for n = 1..1000

Cf. A226080, A226207.

zeck[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n*Sqrt[5]]], t = n, z = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[z, 1]; t = t - Fibonacci[k], AppendTo[z, 0]]; k--]; If[n > 0 && z[[1]] == 0, Rest[z], z]]; d[n1_, n2_] := Module[{z1 = zeck[n1], z2 = zeck[n2]}, Length[z1] + Length[z2] - 2 (NestWhile[# + 1 &, 1, z1[[#]] == z2[[#]] &, 1, Min[{Length[z1], Length[z2]}]] - 1)];
lst = Map[d[#, #^2] &, Range[100]] (* Peter J. C. Moses, May 30 2013 *)

A226215 Zeckendorf distance between n! and (n+1)!.

Original entry on oeis.org

1, 2, 5, 11, 18, 20, 36, 45, 49, 53, 69, 83, 94, 105, 116, 122, 122, 146, 164, 178, 191, 204, 217, 229, 244, 253, 265, 263, 293, 309, 328, 339, 357, 372, 385, 400, 415, 430, 447, 462, 476, 490, 504, 516, 541, 536, 573, 580, 600, 618, 636, 654, 671, 686, 704

Offset: 1

Clark Kimberling, May 31 2013

Zeckendorf distance is defined at A226207. For n = 100, the Zeckendorf distance between n! and (n+1)! is 704, compared to the linear distance which exceeds 10^150; in general, the Zeckendorf distance between two large integers tends to be notably less than the ordinary distance.

			4! = 21 + 3 -> 13 + 2 -> 8 + 1 -> 5 -> 3, and 5! = 89 + 21 + 8 + 2 -> 55 + 13 + 5 + 1 -> 34 + 8 + 3 -> 21 + 5 + 2 -> 13 + 3 + 1 -> 8 + 2 -> 5 + 1 -> 3. The total number of Zeckendorf downshifts (i.e., arrows) is 4 + 7, so that a(4) = D(24,120) = 11.

Clark Kimberling, Table of n, a(n) for n = 1..200

Cf. A226080, A226207.

zeck[n_Integer] := Block[{k = Ceiling[Log[GoldenRatio, n*Sqrt[5]]], t = n, z = {}}, While[k > 1, If[t >= Fibonacci[k], AppendTo[z, 1]; t = t - Fibonacci[k], AppendTo[z, 0]]; k--]; If[n > 0 && z[[1]] == 0, Rest[z], z]]; d[n1_, n2_] := Module[{z1 = zeck[n1], z2 = zeck[n2]}, Length[z1] + Length[z2] - 2 (NestWhile[# + 1 &, 1, z1[[#]] == z2[[#]] &, 1, Min[{Length[z1], Length[z2]}]] - 1)];
lst = Map[d[#!, (#+1)!] &, Range[100]] (* Peter J. C. Moses, May 30 2013 *)

A226275 Number of new rationals produced at the n-th iteration by applying the map t -> {t+1, -1/t} to nonzero terms, starting with S[0] = {1}.

Original entry on oeis.org

1, 2, 3, 3, 5, 7, 10, 15, 22, 32, 47, 69, 101, 148, 217, 318, 466, 683, 1001, 1467, 2150, 3151, 4618, 6768, 9919, 14537, 21305, 31224, 45761, 67066, 98290, 144051, 211117, 309407, 453458, 664575, 973982, 1427440, 2092015, 3065997, 4493437, 6585452, 9651449

Offset: 0

M. F. Hasler, Jun 01 2013

nonn

The sequence produced by repeatedly applying t->(1+t,-1/t), starting from {1} and discarding numbers produced earlier, might be called Fibonacci or rabbit ordering of the rationals, in analogy to that ordering of the positive rationals, with t -> (1+t,1/t).

			The terms produced as described above are (grouped by iteration, including the starting value 1 = iteration 0): [1], [2, -1], [3, -1/2, 0], [4, -1/3, 1/2], [5, -1/4, 2/3, 3/2, -2], [6, -1/5, 3/4, 5/3, -3/2, 5/2, -2/3],[7, -1/6, 4/5, 7/4, -4/3, 8/3, -3/5, 7/2, -2/5, 1/3],[8, -1/7, 5/6, 9/5, -5/4, 11/4, -4/7, 11/3, -3/8, 2/5, 9/2, -2/7, 3/5, 4/3, -3], ...

Cf. A226271, A226274, A226080, A226081, A226130.

Essentially (up to initial terms) the same as A003410, A058278, A097333 and, in particular, A226136.

o.g.f. = (1 + x + x^2 - x^3 - x^5)/(1 - x - x^3)

A226456 Array by antidiagonals: D(m,n) = binary distance between m and n.

Original entry on oeis.org

0, 1, 1, 1, 0, 1, 2, 2, 2, 2, 2, 1, 0, 1, 2, 2, 1, 3, 3, 1, 2, 2, 3, 3, 0, 3, 3, 2, 3, 3, 1, 2, 2, 1, 3, 3, 3, 2, 1, 4, 0, 4, 1, 2, 3, 3, 2, 4, 4, 4, 4, 4, 4, 2, 3, 3, 2, 4, 1, 4, 0, 4, 1, 4, 2, 3, 3, 2, 4, 1, 3, 2, 2, 3, 1, 4, 2, 3, 3, 4, 4, 3, 3, 5, 0, 5

Offset: 1

Clark Kimberling, Jun 08 2013

Method 1.  In base 2, write m = m(0) + m(1)*2 + ... + m(i)*2^i and n = n(0) + n(1)*2 + ... + n(j)*2^j.  Let c be the greatest h such that m(h) = n(h) for h = 0,...,c, and let r(m,n) = m(0) + m(1)*2 + ... + m(c)*2^c.  For every positive integer k, let g(k) be the number of binary digits of k.  Then D(m,n) = g(m) + g(n) - 2*g(r(m,n)).
Method 2.  Let S be the set determined by these rules:  1 is in S, and if x is in S, then x+1 and 1/(x+1) are in S.  As in A226080, grow the tree from the root 1, and then replace each number by the order in which it was generated.  In the resulting tree, D(m,n) is the number of edges from m to n; i.e., D is the graph metric of the tree.  The tree is also determined by the condition that if m < n, then m and n are connected by an edge if and only if m = floor(n/2).
The set S consists of all the positive rationals, of which the first 15 are indicated in generations by (1), (2, 1/2), (3 ,1/3, 3/2, 2/3), (4, 1/4, 4/3, 3/4, 5/2, 2/5, 5/3, 3/5).  One outermost branch of the tree consists of 1,2,3,4,... and the other involves Fibonacci numbers: 1, 1/2, 2/3, 3/5,...
D(n,1)+1 is the number of digits in (n base 2); D(n,n+1) = A101688(n) for n>=1.

			Northwest corner of the distance table:
0 1 1 2 2 2 2 3 3 3
1 0 2 1 1 3 3 2 2 2
1 2 0 3 3 1 1 4 4 4
2 1 3 0 2 4 4 1 1 3
2 1 3 2 0 4 4 3 3 1
2 3 1 4 4 0 2 5 5 5
2 3 1 4 4 2 0 5 5 5
3 2 4 1 3 5 5 0 2 4
3 2 4 1 3 5 5 2 0 4
3 2 4 3 1 5 5 4 4 0
Row 9, column 6 is occupied by 5, meaning that D(9,6) = 5, a count of edges in the subgraph 9 -> 4 -> 2 -> 1 -> 3 ->6.

Clark Kimberling, Antidiagonals n=1..60, flattened

Cf. A226080, A226207, A226247, A101688.

r = 1/2; f[x_] := Floor[r*x]; z = 20; g[x_] := FixedPointList[f, x]; u[x_] := Length[g[x]];  v[x_, y_] := Max[Intersection[g[x], g[y]]]; d[x_, y_] := u[x] + u[y] - 2*Length[g[v[x, y]]]; TableForm[Table[d[m, n], {m, 1, z}, {n, 1, z}]] (* A226456 array *)
Flatten[Table[d[k, n + 1 - k], {n, 1, z}, {k, 1, n}]] (* A226456 sequence *)
Table[d[n, n + 1], {n, 1, 100}] (* A101688 *)
Table[d[n, 2^n], {n, 1, 100}]   (* A226457 *)

A264799 Tree T generated by these rules: 0 is in T, and if x is in T, then x+1 and -2x are in T, with duplicates deleted as they occur.

Original entry on oeis.org

0, 1, -2, 2, -4, -1, 3, 4, -8, -6, -3, 5, 8, -16, -10, -7, -5, 6, 9, 12, 16, -32, -24, -18, -15, -12, -9, 7, 10, 13, 14, 17, 20, 32, -64, -40, -34, -31, -28, -26, -23, -20, -17, -14, -11, 11, 15, 18, 21, 24, 30, 33, 36, 48, 64, -128, -96, -72, -66, -63, -60

Offset: 0

Clark Kimberling, Nov 25 2015

Every integer occur in T exactly once, so that this is a permutation of the integers. Let g(0) = {0}, g(1) = {1}, g(2) = {-2,2}, g(3) = {-4,-1,3,4}, etc. The number |g(n)| of numbers in the n-th generation is a Fibonacci number except for g(3); see A264800.

			Generations begin with
    0
    1
   -2   2
   -4  -1   3   4
   -8  -6  -3   5   8
  -16 -10  -7  -5   6   9  12  16

Clark Kimberling, Table of n, a(n) for n = 0..10000

Cf. A000045, A226080, A264800.

z = 10; t = Expand[NestList[DeleteDuplicates[Flatten[Map[{# + 1, -2*#} &, #], 1]] &, {0}, z]]; s[0] = t[[1]]; s[n_] := s[n] = Union[t[[n]], s[n - 1]];
g[n_] := Complement[s[n], s[n - 1]]; g[1] = {0};
Table[Length[g[k]], {k, 1, z}]  (* A264800 *)
u = Table[g[k], {k, 1, z}]
Flatten[u] (* A264799 *)

A371280 Irregular triangular array of denominators of the set T of fractions generated by these rules: g(1) = (1), and if x and y are in T, then x/(y+1) is in T; see Comments.

Original entry on oeis.org

1, 2, 3, 4, 3, 5, 5, 4, 10, 5, 8, 9, 15, 8, 6, 20, 5, 16, 9, 15, 8, 9, 7, 13, 7, 11, 13, 23, 9, 7, 23, 6, 19, 11, 19, 16, 18, 7, 13, 14, 11, 26, 46, 7, 23, 12, 19, 22, 38, 27, 21, 39, 21, 33, 13, 27, 69, 57, 11, 19, 32, 36, 7, 26, 28, 11, 52, 92, 14, 23, 24

Offset: 1

Clark Kimberling, Mar 18 2024

Starting with g(1) = (1), write the numbers in the ordered union of g(1), g(2),…, g(n) as (x(1),x(2),…,x(m)). Then for i = 1..m, write x(i)/(1 + x(j)) for j = 1..m, and expel all the numbers that have previously occurred. The result is ordered union of g(1), g(2),..., g(n+1). The cardinalities of the first 7 unions are 1, 2, 5, 20, 245, 38179, 1032578826.

Conjecture: every rational number in the interval (0,1] occurs exactly once in T.

			Successive generations:
g(1) = (1)
g(2) = (1/2)
g(3) = (2/3, 1/4, 1/3)
g(4) = (3/5, 4/5, 3/4, 3/10, 2/5, 3/8, 4/9, 8/15, 1/8, 1/6, 3/20, 1/5, 3/16, 2/9, 4/15)
Let U(n) = ordered union of g(1), g(2), ..., g(n).
U(1) = (1)
U(2) = (1, 1/2)
U(3) = (1, 1/2, 2/3, 1/4, 1/3)
U(4) = (1, 1/2, 2/3, 1/4, 1/3, 3/5, 4/5, 3/4, 3/10, 2/5, 3/8, 4/9, 8/15, 1/8, 1/6, 3/20, 1/5, 3/16, 2/9, 4/15)
Denominators U(4): 1, 2, 3, 4, 3, 5, 5, 4, 10, 5, 8, 9, 15, 8, 6, 20, 5, 16, 9, 15

Cf. A226080, A371279, A371353.

(* In the remarks below, U(n) = ordered union of generations g(1), g(2),...g(n) *)
x = {1};
x = DeleteDuplicates[Join[x, Map[x[[#[[1]]]]/(1 + x[[#[[2]]]]) &, Tuples[Range[Length[x]], {2}]]]] (* U(2) *)
x = DeleteDuplicates[Join[x, Map[x[[#[[1]]]]/(1 + x[[#[[2]]]]) &, Tuples[Range[Length[x]], {2}]]]] (* U(3) *)
x = DeleteDuplicates[Join[x, Map[x[[#[[1]]]]/(1 + x[[#[[2]]]]) &, Tuples[Range[Length[x]], {2}]]]] (* U(4) *)
Numerator[x]  (* A371279 *)
Denominator[x]  (* this sequence *)
(* Peter J. C. Moses, Mar 16 2024 *)

A226274 Position of 1/n in the ordering of the rationals given by application of the map t -> (1+t,-1/t), cf. A226130.

Original entry on oeis.org

1, 9, 31, 100, 317, 1000, 3150, 9918, 31223, 98289, 309406, 973981, 3065996, 9651448, 30381786, 95638797, 301061279, 947710512, 2983297009, 9391117780, 29562290606, 93059106094, 292940670339, 922147653681, 2902827709802, 9137808548505, 28764898718296, 90548996937472

Offset: 1

M. F. Hasler, Jun 01 2013

nonn

An analog of the Fibonacci ordering of the positive rationals (cf. A226080) is the sequence of rationals produced from the initial vector [1] by appending iteratively the new rationals obtained by applying the map t-> (t+1, -1/t) to each term of the vector (cf. example).

It is seen that the unit fraction 1/n appears as the last term produced in the (3n-3)th iteration, therefore the indices a(n) equal every third terms in the partial sums of A226275 (= new terms produced during the respective iteration), cf. formula.

			Starting with [1], applying the map t->(1+t,-1/t) to the (most recently obtained) vector and discarding the numbers occurring earlier, one gets the sequence (grouped by "generation"): [1], [2, -1], [3, -1/2, 0], [4, -1/3, 1/2], [5, -1/4, 2/3, 3/2, -2], [6, -1/5, 3/4, 5/3, -3/2, 5/2, -2/3], [7, -1/6, 4/5, 7/4, -4/3, 8/3, -3/5, 7/2, -2/5, 1/3], [8, -1/7, 5/6, 9/5, -5/4, 11/4, -4/7, 11/3, -3/8, 2/5, 9/2, -2/7, 3/5, 4/3, -3],...
The unit fractions 1/1, 1/2, 1/3, 1/4,... occur at positions 1, 9(=1+2+3+3), 31(=9+5+7+10), 100(=31+15+22+32), ...

Cf. A226271, A226275, A226080, A226081, A226130.

{print1([s=1]", ");U=Set(g=[1]); for(n=1,29,U=setunion(U,Set(g=select(f->!setsearch(U,f), concat(apply(t->[t+1,if(t,-1/t)],g))))); for(i=1,#g, numerator(g[i])==1&&print1(s+i/*",g[i],*/","));s+=#g)} /* illustrative purpose only */

a(n) = s(3n-3) where s(k) = Sum_{j=0..k} A226275(j).

O.g.f.: x(1 + 4*x - 7*x^2 + 4*x^3 - x^4)/((1 - x)(1 - 4*x + 3*x^2 - x^3)).

cp's OEIS Frontend

A226209 Zeckendorf distance between n and n+2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A226210 a(n) is the Zeckendorf distance between n and Fibonacci(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A226213 Zeckendorf distance between n and 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A226214 Zeckendorf distance between n and n^2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A226215 Zeckendorf distance between n! and (n+1)!.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A226275 Number of new rationals produced at the n-th iteration by applying the map t -> {t+1, -1/t} to nonzero terms, starting with S[0] = {1}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A226456 Array by antidiagonals: D(m,n) = binary distance between m and n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A264799 Tree T generated by these rules: 0 is in T, and if x is in T, then x+1 and -2x are in T, with duplicates deleted as they occur.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A371280 Irregular triangular array of denominators of the set T of fractions generated by these rules: g(1) = (1), and if x and y are in T, then x/(y+1) is in T; see Comments.