/* powers.q: stream of kth powers without using multiplication */

/* written by Klaus Barthelmann, 04-03-1993
   revised 11-07-1993 AG, 07-05-1994 KB, 11-26-99 AG */

/* to print the fifth powers, say `print (powers 5)' */

include print;

ints N		= bin N (ints (N+1));

dropmod K I (bin X Xs)
		= dropmod K (I+1) Xs if I mod K = 0;
		= bin X (dropmod K (I+1) Xs) otherwise;

sieve K Xs	= Xs if K=1;
		= sieve (K-1) (scanl (+) 0 (dropmod K 0 Xs)) if K>1;

powers K	= sieve K (ints 0) if K>=1;