Mobius function code java

public class mobiusfunction {
public static void main(String args[]) {
int x = 32;
int triangle[][] = new int[x][x];
for (int i = 0; i < x; i++) {
for (int j = 0; j < x; j++) {
triangle[i][j] = 0;
}
}
for(int i = 0; i < x; i++) {
triangle[i][0] = 1 ;
}
for (int i = 1; i < x; i++) {
for (int j = 1; j <=i; j++) {
int sum = 0;
for (int k = 1; k <= j; k++) {
//recursive definition of divisibility no mod function
sum = sum + (triangle[i-k][j-1]) - (triangle[i-k][j]);
}
triangle[i][j] = sum;
}
}
System.out.println("The divisorplot, table A051731 in the OEIS: ");
for (int i = 0; i < x; i++) {
for(int j=0;j<x;j++) {System.out.print(triangle[i][j]+ " ");
}
System.out.println();
}

// modification of the matrix in order to perform matrix inversion by successive squaring:
// this method was discovered together with Gary W. Adamson
triangle[0][0]=-1;
for (int i = 1; i < x; i++) {
triangle[i][i]=0;
}

int power_of_two = 1; // initial value for the do while loop

//Successive squares (by matrix multiplication) of the matrix:
// copied from: http://www.roseindia.net/java/beginners/MatrixMultiply.shtml
do {

//  int n = triangle.length;
    int array2[][] = new int[x][x];

    int y= triangle.length;

      for(int i = 0; i < x; i++) {
      for(int j = 0; j < y-1; j++) {
        for(int k = 0; k < y; k++){
          
          array2[i][j] += triangle[i][k]*triangle[k][j];
        }
      }  
     }

// assign the values from the squared matrix to the original matrix	 
for (int i = 0; i < x; i++) {
for(int j=0;j<x;j++){ triangle[i][j]=array2[i][j];
}
}

power_of_two = power_of_two*2;
} while (power_of_two <= x);
// It should be possible to speed up this algorithm by changing the
// condition for the while statement

    System.out.println("The Mobius function: ");
    for(int i = 0; i < x; i++) {
        System.out.print(" "+triangle[i][0]);
    System.out.println();
    }

}
}
//Mats Granvik email: mats.granvik(at)abo.fi
Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.