login
Numbers satisfying an infinite nested recurrence relation.
2

%I #29 Oct 12 2022 13:53:21

%S 0,1,1,2,2,2,3,3,4,4,4,4,5,5,6,6,7,7,7,8,8,9,9,9,9,9,10,10,11,11,12,

%T 12,13,13,13,14,14,15,15,15,16,16,17,17,17,17,18,18,19,19,20,20,20,21,

%U 21,22,22,22,22,22,22,23,23,24,24,25,25,26,26,27,27,27

%N Numbers satisfying an infinite nested recurrence relation.

%C Conjecture: a(F_n) = F_{n-2} for n>1, where F_n is the n-th Fibonacci number.

%C Conjecture: a(n) ~ n*(3-sqrt(5))/2. -_Jeffrey Shallit_, Oct 12 2022

%H Alois P. Heinz, <a href="/A227145/b227145.txt">Table of n, a(n) for n = 1..10000</a>

%H Marcel Celaya and Frank Ruskey, <a href="http://arxiv.org/abs/1307.0153">Morphic words and nested recurrence relations</a>, arxiv 1307.0153 (Jun 29 2013), [math.CO] (see page 11).

%F a(n) = n - 1 - a(n-1) - a(a(n-2)) - a(a(a(n-3))) - a(a(a(a(n-4)))) - ... with a(n) = 0 if n <= 1.

%p a:= proc(n) option remember; local i, r, s;

%p if n<2 then 0 else r, s:= n, 1;

%p for i while s>0 do r, s:= r-s, (a@@i)(n-i) od: r

%p fi

%p end:

%p seq(a(n), n=1..100); # _Alois P. Heinz_, Jul 04 2013

%t a[n_] := a[n]= Which[n <= 1, 0,True, n - 1 -Sum[Nest[a, n - i, i], {i,1,n}]]; Table[a[i], {i, 0, 30}] (* _José María Grau Ribas_, Jul 10 2013 *)

%Y Cf. A060144.

%K nonn

%O 1,4

%A _Frank Ruskey_, Jul 04 2013