#include <iostream>
using namespace std;
void initializeSequence(int sequence[], int size); // fill the array with numbers 1-size
void createSequence(int sequence[],int sequnceArraySize, int divisor[], int divisorArraySize); //modifies the squence array to contain the hamming sequence
void printSequence(int sequence[],int size); //prints out the array
int findNextTerm(int sequence[], int sequenceIndex, int divisor[], int divisorArraySize, int& testNum); // reutrns true if the test num is part of the hammin sequence
int findDivisor(int divisorArray[], int divisorSize, int testNumber); // returns the divisor of the testNumber if one is found in the divisor array else reutrns 0
bool canFindQuotient(int sequence[], int sequenceIndex, int numToFind); // returns true if the numToFind is in the sequence array in a index below the sequence index
int main()
{
char letter;
// initialize
// divisor array
const int DIVISORSIZE = 3;
int divisors[DIVISORSIZE] = {2,3,5};
// sequence array
const int SEQUENCESIZE = 1000;
int hammingSequence[SEQUENCESIZE];
initializeSequence(hammingSequence,SEQUENCESIZE);
// ask the user for the seed number
// create the hamming sequence
createSequence(hammingSequence,SEQUENCESIZE,divisors,DIVISORSIZE);
// print the sequence
printSequence(hammingSequence,SEQUENCESIZE);
cin >> letter;
return(-1);
}
// fill the array with numbers 1 through size
void initializeSequence(int sequence[], int size)
{
// loops through the array
for(int i = 0; i < size; i++)
// sets the value of the array to the index value +1
sequence[i] = i+1;
}
//modifies the squence array to contain the hamming sequence
void createSequence(int sequence[],int sequenceArraySize, int divisor[], int divisorArraySize)
{
int testNum = 2;
// loops through each index in the array
for(int index = 1; index < sequenceArraySize; index++)
{
// tests all integers until the array is full
// adds it to the next position in the array
sequence[index] = findNextTerm(sequence,index,divisor,divisorArraySize,testNum);
testNum++;
cout << index << "\t" <<sequence[index] << endl; // shows the next term as it is found
}
}
//prints out the array
void printSequence(int sequence[],int size)
{
//loop through the array
for(int i = 0; i < size; i++)
// prints out the value of the array and it's position
cout << sequence[i] << "\t";
}
// reutrns true if the test num is part of the hammin sequence
int findNextTerm(int sequence[], int sequenceIndex, int divisor[], int divisorArraySize, int& testNum)
{
int flag = -1;
// if the test num is divisible by a number in the divisible array
int divisorNum = 0;
divisorNum = findDivisor(divisor,divisorArraySize,testNum);
while(flag == -1 ) // catch flag
{
if(flag != divisorNum)
// check to see if the quotient can be found in the sequence array
if(canFindQuotient(sequence,testNum/divisorNum,sequenceIndex))
// if so return the test num.
return(testNum);
// else set increment the test num and try again
else
{
testNum++;
flag = -1;
}
else
testNum++;
divisorNum = findDivisor(divisor,divisorArraySize,testNum);
}
return(-1);//will never happen
}
// returns the divisor of the testNumber if one is found in the divisor array else reutrns 0
int findDivisor(int divisorArray[], int divisorSize, int testNumber)
{
//loop through the divisor array
for(int index = 0; index < divisorSize; index++)
{
// if the test num is divisible by one
if(testNumber % divisorArray[index] == 0)
//return the divisor
return(divisorArray[index]);
}
// else reuturn -1
return(-1);
}
// returns true if the numToFind is in the sequence array in a index below the sequence index
bool canFindQuotient(int sequence[], int numToFind, int sequenceIndex)
{
//loop through the sequence array up to the currentIndex
for(int index = 0; index < sequenceIndex; index++)
{
// if the numtoFind is in the array return true
if(numToFind == sequence[index])
{
return(true);
}
}
// return false
return(false);
}