A352747 -id:A352747 - cp's OEIS frontend

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

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 2, 1, 4, 4, 5, 5, 3, 1, 5, 5, 7, 8, 8, 5, 1, 6, 6, 9, 11, 13, 13, 8, 1, 7, 7, 11, 14, 18, 21, 21, 13, 1, 8, 8, 13, 17, 23, 29, 34, 34, 21, 1, 9, 9, 15, 20, 28, 37, 47, 55, 55, 34, 1, 10, 10, 17, 23, 33, 45, 60, 76, 89, 89, 55

Offset: 0

Peter Luschny, Apr 01 2022

The definition declares the Fibonacci numbers for all integers n and k. An alternative version is A353595.
The identity F(n, k) = (-1)^k*F(1 - n, -k) holds for all integers n, k. Proof:
     F(n, k)*(2+phi) = (phi^k*(n*phi + 1) - (-phi)^(-k)*((n-1)*phi - 1))
                     = (-1)^k*(phi^(-k)*((1-n)*phi+1) - (-phi)^k*(-n*phi-1))
                     = (-1)^k*F(1-n, -k)*(2+phi).
This identity can be seen as an extension of Cassini's theorem of 1680 and of an identity given by Graham, Knuth and Patashnik in 'Concrete Mathematics' (6.106 and 6.107). The beginning of the full array with arguments in Z x Z can be found in the linked note.
The enumeration is the result of the simple form of the chosen definition. The classical positive Fibonacci numbers starting with 1, 1, 2, 3,... are in row n = 1 with offset 0. The nonnegative Fibonacci numbers starting 0, 1, 1, 2, 3,... are in row 0 with offset 1. They prolong towards -infinity with an index shifted by 1 compared to the enumeration used by Knuth. A characteristic of our enumeration is F(n, 0) = 1 for all integer n.
Fibonacci numbers vanish only for (n,k) in {(-1,2), (0,1), (1,-1), (2,-2)}. The zeros correspond to the identities (phi + 1)*psi^2 = (psi + 1)*phi^2, psi*phi = phi*psi, (phi - 1)*phi = (psi - 1)*psi and (phi - 2)*phi^2 = (psi - 2)*psi^2.
For divisibility properties see A352747.
For any fixed k, the sequence F(n, k) is a linear function of n. In other words, an arithmetic progression. This implies that F(n+1, k) = 2*F(n, k) - F(n-1, k) for all n in Z. Special case of this is Fibonacci(n+1) = 2 *Fibonacci(n) - Fibonacci(n-2). - Michael Somos, May 08 2022

			Array starts:
n\k 0, 1,  2,  3,  4,  5,  6,   7,   8,   9, ...
---------------------------------------------------------
[0] 1, 0,  1,  1,  2,  3,  5,   8,  13,  21, ... A212804
[1] 1, 1,  2,  3,  5,  8, 13,  21,  34,  55, ... A000045 (shifted once)
[2] 1, 2,  3,  5,  8, 13, 21,  34,  55,  89, ... A000045 (shifted twice)
[3] 1, 3,  4,  7, 11, 18, 29,  47,  76, 123, ... A000032 (shifted once)
[4] 1, 4,  5,  9, 14, 23, 37,  60,  97, 157, ... A000285
[5] 1, 5,  6, 11, 17, 28, 45,  73, 118, 191, ... A022095
[6] 1, 6,  7, 13, 20, 33, 53,  86, 139, 225, ... A022096
[7] 1, 7,  8, 15, 23, 38, 61,  99, 160, 259, ... A022097
[8] 1, 8,  9, 17, 26, 43, 69, 112, 181, 293, ... A022098
[9] 1, 9, 10, 19, 29, 48, 77, 125, 202, 327, ... A022099

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, sec. 6.6.
Donald Ervin Knuth, The Art of Computer Programming, Third Edition, Vol. 1, Fundamental Algorithms. Chapter 1.2.8 Fibonacci Numbers. Addison-Wesley, Reading, MA, 1997.

Alexander Bogomolny, Cassini's Identity.
Edsger W. Dijkstra, In honour of Fibonacci, in: F. L. Bauer, M. Broy, & E. W. Dijkstra (editors), Program Construction, 1979, Lecture Notes in Computer Science, Vol. 69.
Peter Luschny, The Fibonacci Function.

Rows: A212804, A000045, A000032, A000285, A022095, A022096, A022097, A022098, A022099.
Columns: A000012, A001477, A000027, A005408, A016789, A016885, A004770.
Diagonals: A088209 (main), A007502, A066982 (antidiagonal sums).
Cf. A352747, A353595 (alternative version), A354265 (generalized Lucas numbers).
Similar arrays based on the Catalan and the Bell numbers are A352680 and A352682.

# Time complexity is O(lg n).
function fibrec(n::Int)
    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
function Fibonacci(n::Int, k::Int)
    k == 0 && return BigInt(1)
    k  < 0 && return (-1)^k*Fibonacci(1 - n, -k)
    a, b = fibrec(k - 1)
    a + b*n
end
for n in -6:6
    println([Fibonacci(n, k) for k in -6:6])
end

f := n -> combinat:-fibonacci(n + 1): F := (n, k) -> (n-1)*f(k-1) + f(k):
seq(seq(F(n-k, k), k = 0..n), n = 0..9);
# The next implementation is for illustration only but is not recommended
# as it relies on floating point arithmetic.
phi := (1 + sqrt(5))/2: psi := (1 - sqrt(5))/2:
F := (n, k) -> (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi):
for n from -6 to 6 do lprint(seq(simplify(F(n, k)), k = -6..6)) od;

Table[LinearRecurrence[{1, 1}, {1, n}, 10], {n, 0, 9}] // TableForm
F[ n_, k_] := (MatrixPower[{{0, 1}, {1, 1}}, k].{{1}, {n}})[[1, 1]]; (* Michael Somos, May 08 2022 *)
c := Pi/2 - I*ArcSinh[1/2]; (* Based on a remark from Bill Gosper. *)
F[n_, k_] := 2 (I (n-1) Sin[k c] + Sin[(k+1) c]) / (I^k Sqrt[5]);
Table[Simplify[F[n, k]], {n, -6, 6}, {k, -6, 6}] // TableForm (* Peter Luschny, May 10 2022 *)

F(n, k) = ([0, 1; 1, 1]^k*[1; n])[1, 1]

{F(n, k) = n*fibonacci(k) + fibonacci(k-1)}; /* Michael Somos, May 08 2022 */

F(n, k) = F(n, k-1) + F(n, k-2) for k >= 2, otherwise 1, n for k = 0, 1.
F(n, k) = (n-1)*f(k-1) + f(k) where f(n) = A000045(n+1), the Fibonacci numbers starting with f(0) = 1.
F(n, k) = ((phi^k*(n*phi + 1) - (-phi)^(-k)*((n - 1)*phi - 1)))/(2 + phi).
F(n, k) = [x^k] (1 + (n - 1)*x)/(1 - x - x^2) for k >= 0.
F(k, n) = [x^k] (F(0, n) + F(0, n-1)*x)/(1 - x)^2 for k >= 0.
F(n, k) = (k!/sqrt(5))*[x^k] ((n-psi)*exp(phi*x) - (n-phi)*exp(psi*x)) for k >= 0.
F(n, k) - F(n-1, k) = sign(k)^(n-1)*f(k) for all n, k in Z, where A000045 is extended to negative integers by f(-n) = (-1)^(n-1)*f(n) (CMath 6.107). - Peter Luschny, May 09 2022
F(n, k) = 2*((n-1)*i*sin(k*c) + sin((k+1)*c))/(i^k*sqrt(5)) where c = Pi/2 - i*arcsinh(1/2), for all n, k in Z. Based on a remark from Bill Gosper. - Peter Luschny, May 10 2022

A353280 n is a term if n = 0 or n does not divide F(n, k) for all k >= 0, where F(n, k) are the Fibonacci numbers A352744.

Original entry on oeis.org

0, 5, 6, 10, 12, 15, 18, 20, 24, 25, 30, 35, 36, 40, 42, 45, 48, 50, 54, 55, 56, 60, 65, 66, 70, 72, 75, 78, 80, 84, 85, 90, 91, 95, 96, 100, 102, 105, 108, 110, 112, 114, 115, 120, 125, 126, 130, 132, 135, 138, 140, 144, 145, 150, 153, 155, 156, 160, 162, 165

Offset: 1

Peter Luschny, Apr 09 2022

nonn

n is a term if 0 is not a term of the sequence A352747(n, .). Since A352747(n, .) is for all n a pure periodic sequence, it is sufficient to require that 0 is not a term of period(A352747(n, .)). Since the length of the period is <= n, the condition can be checked in a finite number of steps.

The multiples of 5 and 6 (A093509) are a subsequence. The terms not of this form start 56, 91, 112, ..., and are in A353281.

			period(A352747(6, .)) = (5, 1, 3) is zero-free, therefore 6 is a term of a.
period(A352747(7, .)) = (1, 0, 6, 5, 4, 3, 2), thus 7 is not a term of a.

a = A093509 union A353281.

Cf. A352744, A352747.

f := n -> combinat:-fibonacci(n): F := (n, k) -> (n-1)*f(k) + f(k+1):
df := n -> denom(f(n)/n) - 1: period := n -> [seq(modp(F(k,n), n), k = 0..df(n))]:
isA353280 := n -> n = 0 or not member(0, period(n)):
select(isA353280, [$(0..166)]);

def F(n, k): return (n - 1)*fibonacci(k) + fibonacci(k + 1)
def df(n): return denominator(fibonacci(n) / n)
def period(n): return (Integer(n).divides(F(k, n)) for k in range(df(n)))
def isA353280(n): return n == 0 or not any([k == True for k in period(n)])
def A353280List(upto): return [n for n in range(upto + 1) if isA353280(n)]
print(A353280List(165))

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Julia

Maple

Mathematica

PARI

PARI

Formula

A002752 a(n) = Fibonacci(n-1) mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Sage

A353280 n is a term if n = 0 or n does not divide F(n, k) for all k >= 0, where F(n, k) are the Fibonacci numbers A352744.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

SageMath

A353281 k is a term if 5 and 6 do not divide k and k does not divide F(n, j) for all j >= 0, where F(n, j) are the Fibonacci numbers.

Views

Author

Keywords

Examples

Crossrefs

Programs

Sage

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