[seqfan] Help needed with Mathematica program for square array with two linked recurrences.

Mats Granvik mgranvik at abo.fi
Sat Jul 9 23:41:54 CEST 2011

Some time ago Jeffrey O. Shallit formulated this recurrence for me:

T(n,1)=1, k>1: T(n,k) = (sum from i = 1 to k-1 of T(n-i,k-1)) - (sum  
from i = 1 to k-1 of

which is the lower triangular matrix:
  T(n,k)=1 if k divides n, T(n,k)=0 otherwise.

A modified version of that recurrence will generate the
  Dirichlet inverse of the Euler totient as the main diagonal
  of a symmetric square array. https://oeis.org/A023900
  This was posted to sequence fan mailing list here:

By entering values in the first row of the spreadsheet
  while letting the recurrence formula remain in the rest
  of the spreadsheet we can see if a recognizable sequence
  comes out in the main diagonal. It then appears that when
  entering the Mertens function plus two in the first row
  we get https://oeis.org/A055615 which is the Mobius
function times the natural numbers in the main diagonal.
This new array can be described by the Excel cell formula:

=if(and(row()=1; column()=1); 1; if(or(and(row()=1; column()=2); and(row()=2;
column()=1)); 2; if(row()=1; (-indirect(address(row();
column()-1))-sum(indirect(address(2; column())&":"&address(column()-1;
column()))))/(column()+1)+indirect(address(row(); column()-1)); if(column()=1;
(-indirect(address(row()-1; column()))-sum(indirect(address(row();  
row()-1))))/(row()+1)+indirect(address(row()-1; column()));  
-sum(indirect(address(row()-column()+1; column())&":"&address(row()-1;  
-sum(indirect(address(column()-row()+1; row())&":"&address(column()-1;  

Above is the European version, the American version
uses "," instead of ";".

This array starts:

The problem when trying to translate it to Mathematica or Matlab
  is that there are two recurrences that are linked to each other which
  makes programming difficult. The first row and the first column
  have one recurrence and the rest of the table has another recurrence.

I made an attempt at this in Mathematica without success:
  Clear[t, n, k, i, nn];
  nn = 12;
  t[1, 1] = 3;
  t[1, 2] = 2;
  t[2, 1] = 2;
  t[2, 2] = -2;
  t[n_, k_] :=
    t[n, k] =
     If[And[n > 2, k > 2],
      If[n >= k, -Sum[t[n - i, k], {i, 1, k - 1}], -Sum[
         t[k - i, n], {i, 1, n - 1}]],
      If[n == 1,
       t[1, k -
          1] + (-t[1, k - 1] - Sum[t[n + i, k], {i, 1, k - 1}])/(n + 1),
       If[k == 1,
        t[n - 1,
          1] + (-t[n - 1, 1] - Sum[t[k + i, n], {i, 1, n - 1}])/(k + 1)
  MatrixForm[Table[Table[t[n, k], {k, 1, nn}], {n, 1, nn}]]

It was perhaps hasty of me but I started an entry here:

If anyone can correct it or write a new Mathematica program
  that describes the square array and add it to the entry,
  I would be happy.

Mats Granvik

More information about the SeqFan mailing list