Sequence of non-squares

Sequence of non-squares
You are encouraged to solve this task according to the task description, using any language you may know.

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

Ada

<ada> with Ada.Numerics.Long_Elementary_Functions; with Ada.Text_IO; use Ada.Text_IO;

procedure Sequence_Of_Non_Squares_Test is

  use Ada.Numerics.Long_Elementary_Functions;
  
  function Non_Square (N : Positive) return Positive is
  begin
     return N + Positive (Long_Float'Floor (0.5 + Sqrt (Long_Float (N))));
  end Non_Square;
  
  I : Positive;

begin

  for N in 1..22 loop -- First 22 non-squares
     Put (Natural'Image (Non_Square (N)));
  end loop;
  New_Line;
  for N in 1..1_000_000 loop -- Check first million of
     I := Non_Square (N);
     if I = Positive (Sqrt (Long_Float (I))) then
        Put_Line ("Found a square:" & Positive'Image (N));
     end if;
  end loop;

end Sequence_Of_Non_Squares_Test; </ada> Sample output:

 2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27

C

<c>

1. include <math.h>
2. include <stdio.h>
3. include <assert.h>

int nonsqr(int n) {

   return n + (int)(0.5 + sqrt(n));
   /* return n + (int)round(sqrt(n)); in C99 */

}

int main() {

   int i;
   
   /* first 22 values (as a list) has no squares: */
   for (i = 1; i < 23; i++)
       printf("%d ", nonsqr(i));
   printf("\n");
   
   /* The following check shows no squares up to one million: */
   for (i = 1; i < 1000000; i++) {
       double j = sqrt(nonsqr(i));
       assert(j != floor(j));
   }
   return 0;

} </c>

J

   rf=:+ 0.5 <.@+ %:  NB.  Remarkable formula

   rf 1+i.22          NB.  Results from 1 to 22
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27

   +/ (= <.)@%:@rf i.&.<:1e6   NB.  Number of square RFs < 1e6
0  

Java

<java> public class SeqNonSquares {

   public static int nonsqr(int n) {
       return n + (int)Math.round(Math.sqrt(n));
   }
   
   public static void main(String[] args) {
       // first 22 values (as a list) has no squares:
       for (int i = 1; i < 23; i++)
           System.out.print(nonsqr(i) + " ");
       System.out.println();
       
       // The following check shows no squares up to one million:
       for (int i = 1; i < 1000000; i++) {
           double j = Math.sqrt(nonsqr(i));
           assert j != Math.floor(j);
       }
   }

} </java>

OCaml

<ocaml>

1. let nonsqr n = n + truncate (floor (0.5 +. sqrt (float n)));;

val nonsqr : int -> int = <fun>

1. (* first 22 values (as a list) has no squares: *)

 for i = 1 to 22 do
   Printf.printf "%d " (nonsqr i)
 done;
 print_newline ();;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 - : unit = ()

1. (* The following check shows no squares up to one million: *)

 for i = 1 to 1000000 do
   let j = sqrt (float (nonsqr i)) in
     assert (j <> floor j)
   done;;

- : unit = () </ocaml>

Python

<python> >>> from math import sqrt >>> def nonsqr(n): return n + int(round(sqrt(n)))

>>> # first 22 values (as a list) has no squares: >>> [nonsqr(i) for i in xrange(1,23)] [2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27] >>> # The following check shows no squares up to one million: >>> for i in xrange(1,1000000): j = sqrt(nonsqr(i)) assert j != int(j), "Found a square in the sequence: %i" % i

>>> </python>