HW 2.

Tasks 1 and 2.

#include <iostream>
#include <cstdlib>

using namespace std;

// Middle Square Pseudo-random number generator
// for a 4 digit long seed
int state = 1111;
// set the seed
void seed(int);
// generate the next number
int gen();


const int N = 10000;
void find_cycles(int len); 

int main() {
  for (int i = 1; i < 10; i++) {
    cout << "Cycles of length " << i << ":" << endl;
    find_cycles(i);
    cout << endl;
  }
}

void find_cycles(int len){
  bool found[N] = {false};

  for(int s = 0; s < N; s++) {
    bool mark[N] = {false};

    seed(s);
    int x = s;
   
    int step = 0;
    for(step = 0; step < len; step++) {
      if (mark[x] || found[x]) break;
      mark[x] = true;
      x = gen();
    }

    if (step == len && x == s) {
      // found a cycle of length len, print it out
      seed(s);
      x = s;
      for(int i = 0; i < len+1; i++) {
        found[x] = true;
        cout << x;
        if (i < len) cout << " -> "; 
        x = gen();
      }
      cout << endl;
    }
  }
}

void seed(int n) {
  state = n;
}

int gen() {
  int v = state * state; 
  state = ((v%1000000) / 100);
  return state;
}

Cycles of length 1:
0 -> 0
100 -> 100
2500 -> 2500
3792 -> 3792
7600 -> 7600

Cycles of length 2:

Cycles of length 3:

Cycles of length 4:
540 -> 2916 -> 5030 -> 3009 -> 540
1600 -> 5600 -> 3600 -> 9600 -> 1600
2100 -> 4100 -> 8100 -> 6100 -> 2100

Cycles of length 5:

Cycles of length 6:

Cycles of length 7:

Cycles of length 8:

Cycles of length 9: