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
<lang 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; </lang> Sample output:
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27
BASIC
<lang freebasic> 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" </lang>
C
<lang 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;
} </lang>
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
Fortran
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
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
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
<lang 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); } }
} </lang>
OCaml
<lang 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 = ()</lang>
Python
<lang 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
>>>
</lang>