OFFSET
1,2
COMMENTS
Define oo by 1/oo = 0 and 1/0 = oo, therefore f(0) = oo, f(1) = 0, f(oo) = 1. (0, oo, 1) is a period of length 3 in {b(n)}, but we dismiss it in a(3) because it's concerned with non-real numbers.
Define f_k(x) by f_0(x) = x and f_k(x) = f(f_(k-1)(x)), therefore b(n+1) = f_n(b(1)).
We observe that the function f_k(x) is a piecewise fractional function, and we can prove by induction that each subfunction has the following properties:
1. The y-coordinates of each pair of endpoints must be either (0,1), (1,oo) or (oo,0).
2. Each subfunction is monotonic and continuous.
If {b(n)} has a period of length k, the function f_(k-1)(x) must intersect the line y=x at x=b(1). Note that each subfunction can intersect y=x at most one time; they intersect iff the subfunction's domain is within (0,1) and the y-coordinate of its endpoints is (0,1); or the subfunction's domain is within (1,oo) and the y-coordinate of its endpoints is (1,oo). Those can be proved by induction.
Therefore, we need to study an array separately on (0,1) and (1,oo).
On (0,1), the initial array is (0,1). After each iteration, 0 -> oo, 1 -> 0, oo -> 1. If 0 and oo are adjacent in the resulting array, put an 1 between them. The number of possible b(1)'s for period of length no more than n is given by the number of adjacent (0,1)'s and (1,0)'s in the array iterated (n-1) times. Denote it by x(n). x(1) = 1, x(2) = 2, x(n+2) = x(n) + x(n+1).
On (1,oo), the initial array is (1,oo). After each iteration, 0 -> oo, 1 -> 0, oo -> 1. If 0 and oo are adjacent in the resulting array, put an 1 between them. The number of possible b(1)'s for period of length no more than n is given by the number of adjacent (1,oo)'s and (oo,1)'s in the array iterated (n-1) times. Denote it by y(n). y(1) = 0, y(2) = 1, y(n+2) = y(n) + y(n+1).
Therefore, the total number of possible b(1)'s for period of length no more than n is x(n) + y(n) = L(n), where L(n) is the Lucas number A000032(n), i.e. Sum{d|n} a(n) = L(n).
Lastly, using the Moebius inversion formula, we can get a(n) = Sum{d|n} mu(d)*L(n/d). This is the formula for a(n) for cases except n=3, since we can prove that invalid periods of length n != 3 does not exist.
The idea and general proof are from 73Dsi.
LINKS
Paolo Xausa, Table of n, a(n) for n = 1..1000
FORMULA
EXAMPLE
For n = 1, only b(1) = (sqrt(5)-1)/2 is possible, so a(1) = 1;
For n = 3, there are no possible b(1)'s.
MATHEMATICA
A378853[n_] := If[n == 3, 0, DivisorSum[n, MoebiusMu[#]*LucasL[n/#] &]];
Array[A378853, 50] (* Paolo Xausa, Dec 21 2024 *)
PROG
(PARI) L(n)=real((2+quadgen(5))*quadgen(5)^n);
a(n)=if(n==3, 0, sumdiv(n, d, moebius(d)*L(n/d)));
CROSSREFS
KEYWORD
nonn
AUTHOR
Yifan Xie, Dec 09 2024
STATUS
approved