f(x) = ( f([x/2]) + f([x/3]) ) / 2

[Dean Hickerson]

Zak Seidov wrote:

> Max, Roger, SeqFans,
> what's known about 
> f(x) = p_1*f([x/q_1]) + ... + p_k*f([x/q_k])
> in cases of (some)  q_i<1?
> I refer to A119565.
> Thanks, Zak

Note that A119565 doesn't actually satisfy the equation by which it's
supposed to be defined:

> %S A119565 1,2,3,5,7,10,12,14,17,20,23,27,31,36,42,49,57,66,76,88,101
> %N A119565 a(n) = Floor[a[n - 1] + 1 + (a[n - 2] + a[n - 3 + a[n - 4]])/6]

 From the Mathematica program it's clear that the values were computed by
first initializing all values of a(n) to 0, setting a(0)=1, ..., a(3)=5,
and then replacing a(n) by

    floor(a(n-1) + 1 + (a(n-2) + a(n-3 + a(n-4)))/6)

for n=4, 5, 6, ...  But look at what happens for n = 6:  We replace a(6)
by

    floor(a(5) + 1 + (a(4) + a(3 + a(2)))/6)

    = floor(10 + 1 + (7 + a(3 + 3))/6)

    = floor(11 + (7 + a(6))/6)

Since a(6) was initialized to 0, this is just

    floor(11 + 7/6) = 12.

And from this point on, the value of  a(n-3 + a(n-4))  that we use is
always 0, since  n-3 + a(n-4)  is >= n.  So the computed sequence
actually satisfies the simpler recurrence

    a(n) = floor(a(n-1) + 1 + a(n-2)/6)  for n>=6.                    (*)

If the sequence is to be kept in the OEIS then someone should fix the
definition and replace the Mathematica code by something simpler, like:

    a[0]=1;a[1]=2;a[2]=3;a[3]=5;a[4]=7;a[5]=10;

    a[n_]:=a[n]=Floor[a[n-1]+1+a[n-2]/6];

> %C A119565 A chaotic recursive sequence with prime like behavior.

What's prime-like about it?

> %C A119565 Sequence was translated into Mathematica by Don Taylor from
>            True Basic: an older sequence that worked in True Basic but
>            not in Mathematica

My guess is that this is because True Basic automatically initializes
arrays to 0, but Mathematica doesn't.


Perhaps the intent really was to have the sequence satisfy

    a(n) = floor(a(n-1) + 1 + (a(n-2) + a(n-3 + a(n-4)))/6)           (**)

for all n.  If so, then we must have

    a(6) = floor(11 + (7 + a(6))/6),

which implies a(6) = 14.  Next:

    a(7) = floor(15 + (10 + a(9))/6)

    a(8) = floor(a(7) + 1 + (14 + a(12))/6)

    a(9) = floor(a(8) + 1 + (a(7) + a(16))/6)

    a(10) = floor(a(9) + 1 + (a(8) + a(21))/6)
   
    a(11) = floor(a(10) + 1 + (a(9) + a(8 + a(7)))/6)

    ...

It appears that we can pick a(7) arbitrarily and then have 6 possible
values for a(9).  Then we can pick a(8) arbitrarily and have 6 choices
for a(12).  And so on.  (There may be bounds on what some of the values
can be, to guarantee that  a(n-3 + a(n-4))  hasn't already been given a
value.)  I'm not certain, but I think there are infinitely many sequences
that satisfy (**).


Roger, what sequence did you have in mind?  The one that the original
programs computed, which satisfies the simpler recurrence (*)?  Or some
sequence that satisfies (**), and, if so, which one?

Dean Hickerson
dean at math.ucdavis.edu