Longest Lucas seq. from start to "n"

[Maximilian Hasler]

On 10/18/07, Maximilian Hasler <maximilian.hasler at gmail.com> wrote:
> >So, do you want a longest linear recurrent sequence with
> >u(n+2)=u(n)+u(n+1) with all terms non-negative and the
> >last term equalto the given number?
>
> I think this is what Eric wants. So it is sufficient to write the "backward" sequence
> v(n) = u(N-n) (where N is the final index if the given number)
> so that v(0) = given number ; v(1) = numbers to try such that the
> sequence defined by
> v(n+1) = v(n-1)-v(n) stays positive as long as possible.
> Clearly, for v(1) only values between 0 and v(0) are to be tried.

The following PARI program displays this sequence :

find(goal=17, mi=0, mx=0, new) =
for(j=mi,goal,a=[goal,new=j];while(mi<=new=a[#a-1]-new,a=concat(a,new));if(#a>mx,mx=#a;maxa=a););
[mx,maxa]

one finds that the longest sequence is obtained by taking

u(N-1) = round ( 2N / (sqrt(5)+1))

as second (resp. penultimate) term.

M.H.

gp > for(i=1,40,print(i":"find(i)))
1:[4, [1, 1, 0, 1]]
2:[5, [2, 1, 1, 0, 1]]
3:[6, [3, 2, 1, 1, 0, 1]]
4:[5, [4, 2, 2, 0, 2]]
5:[7, [5, 3, 2, 1, 1, 0, 1]]
6:[6, [6, 4, 2, 2, 0, 2]]
7:[5, [7, 4, 3, 1, 2]]
8:[8, [8, 5, 3, 2, 1, 1, 0, 1]]
9:[6, [9, 6, 3, 3, 0, 3]]
10:[7, [10, 6, 4, 2, 2, 0, 2]]
11:[6, [11, 7, 4, 3, 1, 2]]
12:[6, [12, 8, 4, 4, 0, 4]]
13:[9, [13, 8, 5, 3, 2, 1, 1, 0, 1]]
14:[6, [14, 9, 5, 4, 1, 3]]
15:[7, [15, 9, 6, 3, 3, 0, 3]]
16:[8, [16, 10, 6, 4, 2, 2, 0, 2]]
17:[6, [17, 11, 6, 5, 1, 4]]
18:[7, [18, 11, 7, 4, 3, 1, 2]]
19:[6, [19, 12, 7, 5, 2, 3]]
20:[7, [20, 12, 8, 4, 4, 0, 4]]
21:[10, [21, 13, 8, 5, 3, 2, 1, 1, 0, 1]]
22:[6, [22, 14, 8, 6, 2, 4]]
23:[7, [23, 14, 9, 5, 4, 1, 3]]
24:[8, [24, 15, 9, 6, 3, 3, 0, 3]]
25:[7, [25, 15, 10, 5, 5, 0, 5]]
26:[9, [26, 16, 10, 6, 4, 2, 2, 0, 2]]
27:[6, [27, 17, 10, 7, 3, 4]]
28:[7, [28, 17, 11, 6, 5, 1, 4]]
29:[8, [29, 18, 11, 7, 4, 3, 1, 2]]
30:[7, [30, 18, 12, 6, 6, 0, 6]]
31:[7, [31, 19, 12, 7, 5, 2, 3]]
32:[8, [32, 20, 12, 8, 4, 4, 0, 4]]
33:[7, [33, 20, 13, 7, 6, 1, 5]]
34:[11, [34, 21, 13, 8, 5, 3, 2, 1, 1, 0, 1]]
35:[7, [35, 21, 14, 7, 7, 0, 7]]
36:[7, [36, 22, 14, 8, 6, 2, 4]]
37:[8, [37, 23, 14, 9, 5, 4, 1, 3]]
38:[7, [38, 23, 15, 8, 7, 1, 6]]
39:[9, [39, 24, 15, 9, 6, 3, 3, 0, 3]]
40:[8, [40, 25, 15, 10, 5, 5, 0, 5]]

gp > find(2007)
%31 = [11, [2007, 1240, 767, 473, 294, 179, 115, 64, 51, 13, 38]]

gp > round(2007*(sqrt(5)/2-.5))
%32 = 1240