A206420 -id:A206420 - cp's OEIS frontend

A230871 Construct a triangle as in the Comments, read nodes from left to right starting at the root and proceeding downwards.

0, 1, 1, 3, 2, 2, 4, 8, 3, 5, 3, 5, 7, 9, 11, 21, 5, 7, 7, 13, 5, 7, 7, 13, 11, 17, 13, 23, 19, 25, 29, 55, 8, 12, 10, 18, 12, 16, 18, 34, 8, 12, 10, 18, 12, 16, 18, 34, 18, 26, 24, 44, 22, 30, 32, 60, 30, 46, 36, 64, 50, 66, 76, 144, 13, 19, 17, 31, 17, 23

Offset: 0

Philippe Deléham, Nov 06 2013

The rule for constructing the tree is the following:
.....x
.....|
.....y
..../ \
..y+x..3y-x
and the tree begins like this:
.........0......
.........|......
.........1......
......./   \....
......1.....3....
...../ \.../ \...
....2...2.4...8..
and so on.
Column 1 :  0,  1,  1,  2,  3,   5,   8, ... = A000045 (Fibonacci numbers).
Column 2 :  3,  2,  5,  7, 12,  19,  31, ... = A013655.
Column 3 :  4,  3,  7, 10, 17,  27,  44, ... = A022120.
Column 4 :  8,  5, 13, 18, 31,  49,  80, ... = A022138.
Column 5 :  7,  5, 12, 17, 29,  46,  75, ... = A022137.
Column 6 :  9,  7, 16, 23, 39,  62, 101, ... = A190995.
Column 7 : 11,  7, 18, 25, 43,  68, 111, ... = A206419.
Column 8 : 21, 13, 34, 47, 81, 128, 209, ... = ?
Column 9 : 11,  8, 19, 27, 46,  73, 119, ... = A206420.
The lengths of the rows are 1, 1, 2, 4, 8, 16, 32, 64, 128, 256, ... = A011782 .
The final numbers in the rows are 0, 1, 3, 8, 21, 55, 144, ... = A001906.
The middle numbers in the rows are 1, 2, 5, 13, 34, 89, ... =  A001519 .
Row sums for n>=1: 1, 4, 16, 64, 256, 1024, ... = 4^(n-1).

			The successive rows are:
  0
  1
  1, 3
  2, 2, 4, 8
  3, 5, 3, 5, 7, 9, 11, 21
  5, 7, 7, 13, 5, 7, 7, 13, 11, 17, 13, 23, 19, 25, 29, 55
  ...

Reinhard Zumkeller, Rows n = 0..13 of triangle, flattened

Cf. A230872, A230873.

Cf. A231330, A231331, A231335.

data Dtree = Dtree Dtree (Integer, Integer) Dtree
a230871 n k = a230871_tabf !! n !! k
a230871_row n = a230871_tabf !! n
a230871_tabf = [0] : map (map snd) (rows $ deleham (0, 1)) where
   rows (Dtree left (x, y) right) =
        [(x, y)] : zipWith (++) (rows left) (rows right)
   deleham (x, y) = Dtree
           (deleham (y, y + x)) (x, y) (deleham (y, 3 * y - x))
-- Reinhard Zumkeller, Nov 07 2013

T:= proc(n, k) T(n, k):= `if`(k=1 and n<2, n, (d->(1+2*d)*
      T(n-1, r)+(1-2*d)*T(n-2, iquo(r+1, 2)))(irem(k+1, 2, 'r')))
    end:
seq(seq(T(n, k), k=1..max(1, 2^(n-1))), n=0..7); # Alois P. Heinz, Nov 07 2013

T[n_, k_] := T[n, k] = If[k==1 && n<2, n, Function[d, r = Quotient[k+1, 2]; (1+2d) T[n-1, r] + (1-2d) T[n-2, Quotient[r+1, 2]]][Mod[k+1, 2]]];
Table[T[n, k], {n, 0, 7}, {k, 1, Max[1, 2^(n-1)]}] // Flatten (* Jean-François Alcover, Apr 11 2017, after Alois P. Heinz *)

Incorrect formula removed by Michel Marcus, Sep 23 2023

A354265 Array read by ascending antidiagonals for n >= 0 and k >= 0. Generalized Lucas numbers, L(n, k) = (psi^(k - 1)(phi + n) - phi^(k - 1)(psi + n)), where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2.

Original entry on oeis.org

2, 3, 1, 4, 4, 3, 5, 7, 7, 4, 6, 10, 11, 11, 7, 7, 13, 15, 18, 18, 11, 8, 16, 19, 25, 29, 29, 18, 9, 19, 23, 32, 40, 47, 47, 29, 10, 22, 27, 39, 51, 65, 76, 76, 47, 11, 25, 31, 46, 62, 83, 105, 123, 123, 76, 12, 28, 35, 53, 73, 101, 134, 170, 199, 199, 123

Offset: 0

Peter Luschny, May 29 2022

The definition declares the Lucas numbers for all integers n and k. It gives the classical Lucas numbers as L(0, n) = Lucas(n), where Lucas(n) = A000032(n) is extended in the usual way for negative n.

			Array starts:
[0]  2,  1,  3,  4,   7,  11,  18,  29,  47,   76, ... A000032
[1]  3,  4,  7, 11,  18,  29,  47,  76, 123,  199, ... A000032 (shifted)
[2]  4,  7, 11, 18,  29,  47,  76, 123, 199,  322, ... A000032 (shifted)
[3]  5, 10, 15, 25,  40,  65, 105, 170, 275,  445, ... A022088
[4]  6, 13, 19, 32,  51,  83, 134, 217, 351,  568, ... A022388
[5]  7, 16, 23, 39,  62, 101, 163, 264, 427,  691, ... A190995
[6]  8, 19, 27, 46,  73, 119, 192, 311, 503,  814, ... A206420
[7]  9, 22, 31, 53,  84, 137, 221, 358, 579,  937, ... A206609
[8] 10, 25, 35, 60,  95, 155, 250, 405, 655, 1060, ...
[9] 11, 28, 39, 67, 106, 173, 279, 452, 731, 1183, ...

Peter Luschny, The Fibonacci Function.

Cf. A000032, A000204, A022088, A022388, A190995, A206420, A206609.

Cf. A352744.

const FibMem = Dict{Int,Tuple{BigInt,BigInt}}()
function FibRec(n::Int)
    get!(FibMem, n) do
        n == 0 && return (BigInt(0), BigInt(1))
        a, b = FibRec(div(n, 2))
        c = a * (b * 2 - a)
        d = a * a + b * b
        iseven(n) ? (c, d) : (d, c + d)
    end
end
function Lucas(n, k)
    k ==  0 && return BigInt(n + 2)
    k == -1 && return BigInt(2 * n - 1)
    k <   0 && return (-1)^k * Lucas(1 - n, -k - 2)
    a, b = FibRec(k)
    c, d = FibRec(k - 1)
    n * (2 * a + b) + 2 * c + d
end
for n in -6:6
    println([Lucas(n, k) for k in -6:6])
end

phi := (1 + sqrt(5))/2: psi := (1 - sqrt(5))/2:
L := (n, k) -> phi^(k+1)*(n - psi) + psi^(k+1)*(n - phi):
seq(seq(simplify(L(n-k, k)), k = 0..n), n = 0..10);

L[n_, k_] := With[{c = Pi/2 + I*ArcCsch[2]},
             I^k Sec[c] (n Cos[c (k + 1)] - I Cos[c k]) ];
Table[Simplify[L[n, k]], {n, 0, 6}, {k, 0, 6}] // TableForm
(* Alternative: *)
L[n_, k_] := n*LucasL[k + 1] + LucasL[k];
Table[Simplify[L[n, k]], {n, 0, 6}, {k, 0, 6}] // TableForm

Functional equation extends Cassini's theorem:
L(n, k) = (-1)^k*L(1 - n, -k - 2).
L(n, k) = n*Lucas(k + 1) + Lucas(k).
L(n, k) = L(n, k-1) + L(n, k-2).
L(n, k) = i^k*sec(c)*(n*cos(c*(k + 1)) - i*cos(c*k)), where c = Pi/2 + i*arccsch(2), for all n, k in Z.
Using the generalized Fibonacci numbers F(n, k) = A352744(n, k),
L(n, k) = F(n, k+1) + F(n, k) + F(n, k-1) + F(n, k-2).

A347351 Triangle read by rows: T(n,k) is the number of links of length k in a set of all necklaces A000358 of length n, 1 <= k <= n.

Original entry on oeis.org

1, 2, 1, 3, 0, 1, 4, 2, 0, 1, 5, 1, 1, 0, 1, 6, 4, 2, 1, 0, 1, 7, 3, 2, 1, 1, 0, 1, 8, 8, 3, 3, 1, 1, 0, 1, 9, 8, 7, 3, 2, 1, 1, 0, 1, 10, 18, 9, 5, 4, 2, 1, 1, 0, 1, 11, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1, 12, 40, 24, 16, 8, 6, 3, 2, 1, 1, 0, 1, 13, 55, 34, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1

Offset: 0

Maxim Karimov and Vladislav Sulima, Aug 28 2021

Definitions:
1. A link is any 0 in any necklace from A000358 and all 1s following this 0 in this necklace to right until another 0 is encountered.
2. Length of the link is the number of elements in the link.
Sum of all elements n-row is Fibonacci(n-1)+n iff n=1 or n=p (follows from the identity for the sum of the Fibonacci numbers and the formula for the triangle T(n,k)).

			For k > 0:
   n\k |  1   2   3   4   5   6   7   8   9  10  ...
  -----+---------------------------------------
   1   |  1
   2   |  2   1
   3   |  3   0   1
   4   |  4   2   0   1
   5   |  5   1   1   0   1
   6   |  6   4   2   1   0   1
   7   |  7   3   2   1   1   0   1
   8   |  8   8   3   3   1   1   0   1
   9   |  9   8   7   3   2   1   1   0   1
  10   | 10  18   9   5   4   2   1   1   0   1
  ...
If we continue the calculation for nonpositive k, we get a table in which each row is a Fibonacci sequence, in which term(0) = A113166, term(1) = A034748.
For k <= 0:
   n\k |  0   -1   -2   -3   -4   -5   -6   -7   -8   -9 ...
  -----+------------------------------------------------
   1   |  0    1    1    2    3    5    8   13   21   34 ... A000045
   2   |  1    2    3    5    8   13   21   34   55   89 ... A000045
   3   |  1    4    5    9   14   23   37   60   97  157 ... A000285
   4   |  3    6    9   15   24   39   63  102  165  267 ... A022086
   5   |  3    9   12   21   33   54   87  141  228  369 ... A022379
   6   |  8   14   22   36   58   94  152  246  398  644 ... A022112
   7   |  8   19   27   46   73  119  192  311  503  814 ... A206420
   8   | 17   30   47   77  124  201  325  526  851 1377 ... A022132
   9   | 23   44   67  111  178  289  467  756 1223 1979 ... A294116
  10   | 41   68  109  177  286  463  749 1212 1961 3173 ... A022103
  ...

Cf. A000010, A000027, A000045, A000358, A113166, A034748.

function [res] = calcLinks(n,k)
if k==1
    res=n;
else
    d=divisors(n);
    res=0;
    for i=1:length(d)
        if d (i) >= k
            res=res+eulerPhi(n/d(i))*fiboExt(d(i)-k-1);
        end
    end
end
function [s] = fiboExt(m) % extended fibonacci function (including negative arguments)
m=sym(m); % for large fibonacci numbers
if m>=0 || mod(m,2)==1
    s=fibonacci(abs(m));
else
    s=fibonacci(abs(m))*(-1);
end

T(n, k) = if (k==1, n, sumdiv(n, d, if (d>=k, eulerphi(n/d)*fibonacci(d-k-1)))); \\ Michel Marcus, Aug 29 2021

If k=1, T(n,k)=n, otherwise T(n,k) = Sum_{d>=k, d|n} Phi(n/d)*Fibonacci(d-k-1), where Phi=A000010.

cp's OEIS Frontend

A230871 Construct a triangle as in the Comments, read nodes from left to right starting at the root and proceeding downwards.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Extensions

A354265 Array read by ascending antidiagonals for n >= 0 and k >= 0. Generalized Lucas numbers, L(n, k) = (psi^(k - 1)(phi + n) - phi^(k - 1)(psi + n)), where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

A347351 Triangle read by rows: T(n,k) is the number of links of length k in a set of all necklaces A000358 of length n, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

PARI

Formula

cp's OEIS Frontend

A230871 Construct a triangle as in the Comments, read nodes from left to right starting at the root and proceeding downwards.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Extensions

A354265 Array read by ascending antidiagonals for n >= 0 and k >= 0. Generalized Lucas numbers, L(n, k) = (psi^(k - 1)*(phi + n) - phi^(k - 1)*(psi + n)), where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Julia

Maple

Mathematica

Formula

A347351 Triangle read by rows: T(n,k) is the number of links of length k in a set of all necklaces A000358 of length n, 1 <= k <= n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

MATLAB

PARI

Formula

A354265 Array read by ascending antidiagonals for n >= 0 and k >= 0. Generalized Lucas numbers, L(n, k) = (psi^(k - 1)(phi + n) - phi^(k - 1)(psi + n)), where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2.