A378853 - OEIS

%I #22 Dec 22 2024 09:29:26

%S 1,2,0,4,10,12,28,40,72,110,198,300,520,812,1350,2160,3570,5688,9348,

%T 15000,24444,39402,64078,103320,167750,270920,439128,709800,1149850,

%U 1859010,3010348,4868640,7880994,12748470,20633200,33379200,54018520,87394452,141421800

%N Define f(x) = abs(1-1/x) and sequence {b(n)} such that b(n+1) = f(b(n)). a(n) is the number of initial values b(1) such that {b(n)}'s period has length n.

%C 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.

%C 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)).

%C 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:

%C 1. The y-coordinates of each pair of endpoints must be either (0,1), (1,oo) or (oo,0).

%C 2. Each subfunction is monotonic and continuous.

%C 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.

%C Therefore, we need to study an array separately on (0,1) and (1,oo).

%C 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).

%C 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).

%C 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).

%C 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.

%C The idea and general proof are from 73Dsi.

%H Paolo Xausa, <a href="/A378853/b378853.txt">Table of n, a(n) for n = 1..1000</a>

%F a(3) = 0; a(n) = Sum{d|n} mu(d)*L(n/d) if n != 3, where mu(n) is the Moebius function A008683(n), and L(n) is the Lucas number A000032(n).

%e For n = 1, only b(1) = (sqrt(5)-1)/2 is possible, so a(1) = 1;

%e For n = 3, there are no possible b(1)'s.

%t A378853[n_] := If[n == 3, 0, DivisorSum[n, MoebiusMu[#]*LucasL[n/#] &]];

%t Array[A378853, 50] (* _Paolo Xausa_, Dec 21 2024 *)

%o (PARI) L(n)=real((2+quadgen(5))*quadgen(5)^n);

%o a(n)=if(n==3, 0, sumdiv(n, d, moebius(d)*L(n/d)));

%Y Cf. A008683 (Moebius function), A000032 (Lucas numbers).

%K nonn

%O 1,2

%A _Yifan Xie_, Dec 09 2024