Task

Show that the following remarkable formula gives the sequence of non-square natural numbers:

            n + floor(1/2 + sqrt(n)) 

 Print out the values for    n    in the range   1   to   22
 Show that no squares occur for    n    less than one million


This is sequence   A000037   in the OEIS database.




(defun non-square-sequence ()
  (flet ((non-square (n)
	   "Compute the N-th number of the non-square sequence"
	   (+ n (floor (+ 1/2 (sqrt n)))))
	 (squarep (n)
	   "Tests, whether N is a square"
	   (let ((r (floor (sqrt n))))
	     (= (* r r) n))))
    (loop
       :for n :upfrom 1 :to 22
       :do (format t "~2D -> ~D~%" n (non-square n)))
    (loop
       :for n :upfrom 1 :to 1000000
       :when (squarep (non-square n))
       :do (format t "Found a square: ~D -> ~D~%" 
		   n (non-square n)))))