Guy's "Add the greatest whatever"

[John Layman]

Recently (May 11), Richard Guy communicated some results found when
playing the following game: Start with a heap of 1 and successively add
the largest term of a specified sequence that is not greater than the
present size of the heap.  This process can be considered as a transform
of the sequence, which we call the G-transform.  Among the results
presented were iterations of the G-transform of the Fibonacci sequence:

  F(n)= 1,2,3,5,8,13,21,34,55,89,144,233,377,610,..., n=1,2,3,...

If these results are extended and presented in an appropriate way, they
lead to an interesting generalization regarding the differences between
the Fibonacci numbers and the successive G-iterates of F.

We will use the following notation:

  Fk = the k-fold iterate of the G-transform of F,
  Hk = the difference between Fk and a shifted Fibonacci sequence,
  GNHk = the sequence of Gregory-Newton interpolation coefficients for Hk,

Results for the first four G-iterates of F were given by Guy and, in our
notation, take the following forms.

  F1(n)= 1,2,4,7,12,20,33,54,88,143,232,376,609,..., n=1,2,3,...
  => H1(n)=F(n+1)-F1(n)=1,1,1,1,1,1,1,1,..., n=1,2,3,...
  => GNH1(n)= 1,0,0,0,0,0,0,0,..., n=1,2,3,...
  => H1(n)=1, n=1,2,3,...
  => F1(n)=F(n+1)-1, n=1,2,3,...

  F2(n)= 1,2,4,8,15,27,47,80,134,222,365,597,973,..., n=1,2,3,...
  => H2(n)=F(n+2)-F2(n)= 2,3,4,5,6,7,8,9,..., n=1,2,3,...
  => GNH2(n)=2,1,0,0,0,0,0,0,0,..., n=1,2,3,...
  => H2(n)=2+(n-1)= n+1, n=1,2,3,...
  => F2(n)=F(n+2)-(n+1), n=1,2,3,...
  If one uses different offsets in each term of this expression,
   as Guy apparently did, we get his form:
     F2(n-2)=F(n)-[2+(n-3)]=F(n)-(n-1), n=3,4,5,6,...

  F3(n)= 1,2,4,8,16,31,58,105,185,319,541,906,...
  => H3(n)=F(n+3)-F3(n)= 4,6,9,13,18,24,31,39,48,58,69,81,...
  => GNH3(n)=4,2,1,0,0,0,0,0,0,0,...
  => H3(n)=4+2(n-1)+(n-1)(n-2)/2= (n^2+n+6)/2
  => F3(n)=F(n+3)-[4+2(n-1)+(n-1)(n-2)/2] = F(n+3)-(n^2+n+6)/2, n=1,2,3,...
  If one changes the offsets (but not consistently with the F2 case),
   one can get Guy's form:
   F3(n-4)=F(n-1)-[4+2(n-5)+(n-5)(n-6)/2]=F(n-1)-(n^2-7n+18)/2, n=5,6,7,8,...

  F4(n)=1,2,4,8,16,32,63,121,226,411,730,1271,2177,3680,6156,10214,...
  => H4=F(n+4)-F4(n)=7,11,17,26,39,57,81,112,151,199,257,326,...
  => GNH4(n)=7,4,2,1,0,0,0,0,0,0,...
  => H4(n)=7+4(n-1)+2(n-1)(n-2)/2+(n-1)(n-2)(n-3)/6=(n^3+17n+24)/6
  => F4(n)=F(n+4)-[7+4(n-1)+2(n-1)(n-2)/2+(n-1)(n-2)(n-3)/6)
          =(n^3+17n+24)/6, n=1,2,3,...
  Here, Guy gave the equivalent form:
  F4(n-5)=F(n-1)-(n^3-15n^2+92n-186)/6, n=6,7,8,9,...

The key to observing the correct generalization of this process is to
notice that the non-zero Gregory-Newton coeficients (i.e, the inverse
binomial transform of Hk) are precisely the terms of F1(n) in reverse
order, beginning with F1(k), when the the expansion is made about n=1.
Continuing, we present the results for the 5th G-iterate and, in
abbreviated form, the 6th iterate:


  F5(n)=1,2,4,8,16,32,64,127,248,474,885,1615,2886,5063,8743,...
  => H5(N)=F(n+5)-F5(n)=12,19,30,47,73,112,169,250,362,513,712,969,...
  => GNH5(n)=12,7,4,2,1,0,0,0,0,0,0,...
  => H5(n)=12+7(n-1)+4(n-1)(n-2)+2(n-1)(n-2)(n-3)/2+(n-1)(n-2)(n-3)(n-4)/6
  => F5(n)=F(n+5)-[12+7(n-1)~1+4(n-1)~2/2+2(n-1)~3/6+(n-1)~4/24]
          =F(n+5)-[F1(5)p(0,n)+F1(4)p(1,n)+F1(3)p(2,n)+F1(2)p(3,n)+F1(1)p(4,n)],
     for n=1,2,3,...


  F6(n)=1,2,4,8,16,32,64,128,255,503,977,1862,3477,6363,11426,...
  => GNH6(n)=20,12,7,4,2,1,0,0,0,0,0,...
  => F6(n)=F(n+6)-Sum[F1(6-i)p(i,n), i=0,1,2,...,5], n:=1,2,3,...,
  where p(i,n)=(n-1)(n-2)...(n-i)/(i!).


Notice that the non-zero Gregory-Newton coeffs. are 20,12,7,4,2,1, the
first 6 terms of F1(n), 1,2,4,7,12,20, in reverse order.

This trend has been confirmed through the first 15-20 G-iterates of F
and suggests the following

CONJECTURE:

    Fk(n)=F(n+k)-Sum[F1(k-i)p(i,n), i=0,1,2,...,k-1], n=1,2,3,...,

where p(i,n) is as previously noted.


In order to stimulate interest in this problem, I am hereby offering a PRIZE
of $25 to the first person who communicates a proof of this conjecture (or a
disproof).  JWL



Turning now to another aspect suggested by Guy's note, the question of
which known sequences have a known G-transform, the following are some
of the results obtained by examining the M-sequences (i.e., those in the
printed encyclopedia).  The numbers in brackets indicate where the
coincidence begins.  Computational work was done using at most 25 terms,
so these results only suggest likely relationships.

    G(M709)[1] = M1059[4] (M1059 is tribonacci)
    G(M784)[1] = M1074[4] (Both tribonacci)
    G(M785)[1] = M1075[1] (Stern's and Conway-Guy sequences)
    G(M787)[1] = M1076[1] (M787 is Narayana-Zidek-Capell seq.)
    G(M1081)[1] = M1108[5] (Both tetranacci)
    G(M2419)[1] = M781[1]