Home

This is a short follow-up on the last post about rhythmic canon mod $p$. You may recall I mentionned that Hélianthe had found a greedy algorithm which could find compact rhythmic canons mod $p$, and I explained how this algorithm works. If you like coding, you should have no problem implementing it in the language of your choice. And if you don’t, here’s my version in C:

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char *argv[])
{
int N;
int* U;
int i,mark=0,flag=0;
unsigned long long L,entry=0;
FILE* output_file=NULL;

if(argc<2) {
printf("Length of the motive is required !\n");
exit(1);
}
N = atoi(argv[1]);
if(argc==3)
output_file=fopen(argv[2],"w");
if (output_file!=NULL)
fprintf(output_file,"Entries for canon with motive {0,1,%d}\n",N);

U = calloc(N+1,sizeof(int));
if (U==NULL) {
printf("Error during memory allocation...exiting now !\n");
exit(1);
}

L=N+1;

while(flag==0) {

L+=mark;
entry+=mark;
if (output_file!=NULL)
fprintf(output_file,"%llu\n",entry);

U[0]=1-U[0];
U[1]=1-U[1];
U[N]=1-U[N];

flag=1;
for (mark=0; mark<N+1; mark++) {
if (U[mark]==0) {
flag=0;
break;
}
}

for (i=mark; i<N+1; i++)
U[i-mark]=U[i];
for (i=(N+1-mark); i<N+1; i++)
U[i]=0;
}
printf("Final length of canon with motive {0,1,%d}: %llu \n",N,L);
if (output_file!=NULL)
fclose(output_file);
free(U);
}
```

The program takes one mandatory argument which is the parameter $k$ for determining the length of a $\{0,1,k\}$ canon mod 2, and one optional argument which is the name of a file where the entries of the canon should be written (i.e. the term $B$ in the decomposition $A \bigoplus_N B$).

Of course, you can modify the above program to implement any motive $A$ you want, for example $\{0,2,k\}$ or $\{0,1,2,k\}$ instead of $\{0,1,k\}$.

To finish, here is a graph of the logarithm of the length of the canons with $A=\{0,1,k\}$, with respect to $k$, for $k$ from 2 up to 41 (this last one took two days and a half to compute on my Mac…):

You can clearly see the particular cases $A=\{0,1,k=2^p\}$ and $A=\{0,1,k=2^p+1\}$. Starting from $k=18$, things get interesting as we don’t necessarily have an exponential growth of the length of the canon with k. More on that in a later post…