A079734 n for which there is a chain (or permutation) of the numbers from 1 to n for which each adjacent pair sums to a Fibonacci number.

2, 3, 4, 5, 7, 8, 9, 11, 12, 13, 20, 21, 33, 34, 54, 55, 88, 89, 143, 144, 232, 233, 376, 377, 609, 610, 986, 987, 1596, 1597, 2583, 2584, 4180, 4181, 6764, 6765, 10945, 10946, 17710, 17711, 28656, 28657, 46367, 46368, 75024, 75025, 121392, 121393

Offset

1,1

Comments

There are no such necklaces (or cycles).

Theorem (Berlekamp & Guy) There exists such a chain just if n = 9 or 11 or F_k or F_k - 1 for k > 3.

References

B. Barwell, Problem 2732, Problems and conjectures, Journal of Recreational Mathematics 34 (2006), 220-223.

E. R. Berlekamp and R. K. Guy, Paper which MAY be called "Fibonacci plays Billiards" and which may be submitted to the Monthly (in preparation as of Jun 2011).

Links

Colin Barker, Table of n, a(n) for n = 1..1000

Andrii Arman, David S. Gunderson, Pak Ching Li, Properties of the Fibonacci-sum graph, arXiv:1710.10303 [math.CO], 2017.

Kyle Fox, William B. Kinnersley, Daniel McDonald, Nathan Orlow, Gregory J. Puleo, Spanning Paths in Fibonacci-sum Graphs, Fibonacci Quart. 52 (2014), 46-49.

Gregory Puleo, Fibsum Graphs, 2009.

Index entries for linear recurrences with constant coefficients, signature (0,2,0,0,0,-1).

Formula

G.f.: x*(3*x^13+2*x^12+3*x^11+3*x^10-4*x^9-2*x^8-2*x^7-3*x^6-2*x^5-x^4-x^3+3*x+2) / ((x-1)*(x+1)*(x^4+x^2-1)). - Colin Barker, Dec 02 2014

a(n) = 2*a(n-2) - a(n-6) for n>14. - Colin Barker, Dec 02 2014

Example

Examples: 1 2; 1 2 3; 4 1 2 3; 4 1 2 3 5; 4 1 7 6 2 3 5; ...

Maple

S := {9, 11}: for i from 3 to 50 do S := S union {fibonacci(i)}: S := S union {fibonacci(i)-1}: od: S := S minus {1}: S := convert(S, list): S := sort(S):for i from 1 to nops(S) do printf(`%d, `, S[i]) od: # James A. Sellers, Feb 25 2003

Prog

(PARI) Vec(x*(3*x^13+2*x^12+3*x^11+3*x^10-4*x^9-2*x^8-2*x^7-3*x^6-2*x^5-x^4-x^3+3*x+2)/((x-1)*(x+1)*(x^4+x^2-1)) + O(x^100)) \\ Colin Barker, Dec 02 2014
(PARI) lista(nn) = Set(concat([9, 11], concat(vector(nn, n, fibonacci(n+3)), vector(nn, n, fibonacci(n+3)-1)))) \\ Michel Marcus, Oct 31 2017

Crossrefs

Cf. A079735, A079736, A079737, A079738.

Sequence in context: A353833 A219301 A326155 * A050730 A288221 A346782

Adjacent sequences: A079731 A079732 A079733 * A079735 A079736 A079737

Keyword

easy,nonn

Author

R. K. Guy, Feb 18 2003

Extensions

More terms from James A. Sellers, Feb 25 2003

Changes due to offset=1 from Colin Barker, Oct 31 2017

Status

approved