/*********************************************************************************
 ***   FILE: sequence.cpp
 ***   DATE: Sep 25, 2003
 *** Author: Daniel Dementiev
 ***  Descr: This program is written for IST238-Algorithm class to illustrate how
 ***         to work with non-trivial sequences for the Shell sorting method.
 ***         This program takes one argument - the size of the imaginary array
 ***         to work with, and searches for the starting value of the sequence.
 ***         It prints the initial value and all previous elements of the sequence.
 ***         To run the program type something like:
 ***         ...> sequence 160000
 ***         where 160000 is the size of the array you want to see the sequence for.
 ***         The default array size is 80000.
 *********************************************************************************/

#include <iostream>
#include <iomanip>
#include <cstdlib>
using namespace std;

/* --------------------------------------
   This functions returns the i-th element
   of the Shell sort sequence. The general
   formula for sequence elements is:
   beginning
   h[0] = 1
   h[i] = 4^i + 3*2^(i-1) + 1  (for h>0)
   That is, this sequence has elements:
   1 8 23 77 281 ...
   -------------------------------------- */
unsigned int H(int i)
{
	if( i < 0 ) return -1;
	if( i == 0 ) return 1;
	unsigned int p4=4, p2=1;
	while( --i ){
		p4 *= 4;
		p2 *= 2;
	}
	return p4+3*p2+1;
}

void main(int argc, char *argv[])
{
	int N, h, i;
	N = ((argc>1)&&(atoi(argv[1])>0)) ? atoi(argv[1]) : 80000;

	cout<<"For an array of "<<N<<" elements ";
	for(i=0, h=1;h<N/9;h=H(++i));
	cout<<"we start with h = "<<setw(5)<<h<<" (ind="<<i<<")\n\n";
	while( h >= 1 ){
		cout<<"h = "<<setw(5)<<h<<" (ind="<<i<<")\n";
		h = H(--i);
	}
}