Sequence of Non-squares

From Rosetta Code

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

[edit] 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'Rounding (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)))**2 then
         Put_Line ("Found a square:" & Positive'Image (N));
      end if;
   end loop;
end Sequence_Of_Non_Squares_Test;
 

Sample output:

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

[edit] BASIC

Works with: FreeBASIC

Works with: RapidQ

 
DIM i      AS Integer
DIM j      AS Double
DIM found  AS Integer
 
FUNCTION nonsqr (n AS Integer) AS Integer
    nonsqr = n + INT(0.5 + SQR(n))
END FUNCTION
 
' Display first 22 values
FOR i = 1 TO 22
    PRINT nonsqr(i); " ";
NEXT i
PRINT
 
' Check for squares up to one million
found = 0
FOR i = 1 TO 1000000
     j = SQR(nonsqr(i))
     IF j = INT(j) THEN 
	 found = 1
         PRINT "Found square: "; i
         EXIT FOR
     END IF
NEXT i
IF found=0 THEN PRINT "No squares found"
 

[edit] C

 
#include <math.h>
#include <stdio.h>
#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;
}
 

[edit] Forth

: u>f  0 d>f ;
: f>u  f>d drop ;

: fn ( n -- n ) dup u>f fsqrt fround f>u + ;
: test ( n -- ) 1 do i fn . loop ;
23 test    \ 2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27  ok

: square? ( n -- ? ) u>f fsqrt  fdup fround f-  f0= ;
: test ( n -- ) 1 do i fn square? if cr i . ." fn was square" then loop ;
1000000 test    \ ok

[edit] Fortran

Works with: Fortran version 90 and later

PROGRAM NONSQUARES

  IMPLICIT NONE

  INTEGER :: m, n, nonsqr
      
  DO n = 1, 22
    nonsqr =  n + FLOOR(0.5 + SQRT(REAL(n)))  ! or could use NINT(SQRT(REAL(n)))
    WRITE(*,*) nonsqr
  END DO

  DO n = 1, 1000000
    nonsqr =  n + FLOOR(0.5 + SQRT(REAL(n)))
    m = INT(SQRT(REAL(nonsqr)))
    IF (m*m == nonsqr) THEN
      WRITE(*,*) "Square found, n=", n
    END IF
  END DO

END PROGRAM NONSQUARES

[edit] Haskell

nonsqr :: Integral a => a -> a
nonsqr n = n + round (sqrt (fromIntegral n))

> map nonsqr [1..22]
[2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27]

> any (\j -> j == fromIntegral (floor j)) $ map (sqrt . fromIntegral . nonsqr) [1..1000000]
False

[edit] 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  

[edit] 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);
        }
    }
}
 

[edit] OCaml

# let nonsqr n = n + truncate (0.5 +. sqrt (float n));;
val nonsqr : int -> int = <fun>
# (* first 22 values (as a list) has no squares: *)
  for i = 1 to 22 do
    Printf.printf "%d " (nonsqr i)
  done;
  print_newline ();;
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27
- : unit = ()
# (* 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 = ()

[edit] Python

 
>>> from math import sqrt
>>> # (Using the fact that round(X) is equivalent to floor(0.5+X) for our range of X)
>>> 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
 
 
>>>