/*-------------------------------------------------------------------------------
File : seqfan.n
OEIS
On-line Encyclopedy Of Integer Sequences
http://www.research.att.com/~njas/sequences/
--------------------------------------------------------------------------------*/

 /*-------------------------------------------------------------------------------
A005132  Recaman's sequence:
a(0) = 0;
for n > 0, a(n) = a(n-1)-n if that number is positive and not already in the sequence,
otherwise a(n) = a(n-1)+n.
---------------------------------------------------------------------------------*/

/*-------------------------------------------
GBnums function : A005132()
compute 'dim' first terms of sequence
remember 'store' terms in a[]
easy to compute up to 100 000 000 terms (3 minutes)
--------------------------------------------*/

void	A005132(/*into*/ uint a[], dim = 100000, store = 100)
{
mpz n;
mpz a_n;	// a[n]
mpz a_n_1 = 0; // a[n-1]

map_init(0,dim*8,0); //ask GBnums for a bit-map
vdim(a,store); //dynamic vector dimension
vinit(a,0); //initialize vector
map_set(0,1); //mark bit 0 in bit map (a[0]=0)

for(n=1;n<dim;n++)
	{
// sequence definition
	a_n = a_n_1 -n ;
	if(a_n <=  0 ||  map_get(a_n)) a_n = a_n_1 + n;
// end of sequence definition
	map_set(a_n,1); // mark bit a_n in bit-map
	if(n < store) a[n] = a_n; // remember sequence
	a_n_1 = a_n;
	} // n loop

map_init(0,0,0); // clean
} // A005132

/*---------------------------------------------------------------
main
-----------------------------------------------------------------*/
void	main ()
{
uint a[];
	A005132(a,1000,1000); // build sequence
#ifdef _GNUPLOT
	TITLE = '*** A005132 ***';
	vplotui(a); // gives the above graph
#endif
}