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
ALGOL 68
<lang algol>PROC non square = (INT n)INT: n + ENTIER(0.5 + sqrt(n));
main: (
# first 22 values (as a list) has no squares: # FOR i TO 22 DO print((whole(non square(i),-3),space)) OD; print(new line); # The following check shows no squares up to one million: # FOR i TO 1 000 000 DO REAL j = sqrt(non square(i)); IF j = ENTIER j THEN put(stand out, ("Error: number is a square:", j, new line)); stop FI OD
)</lang> 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>
Bc
Since BC is an arbitrary precision calculator, there are no issues in sqrt (it is enough to increase the scale variable upto the desired precision), nor there are limits (but time) to how many non-squares we can compute.
<lang bc>#! /usr/bin/bc
scale = 20
define int(x) {
auto old_scale, ret old_scale=scale scale=0 ret=x/1 scale=old_scale return ret
}
define round(x) {
if (x<0) x-=.5 else x+=.5 return int(x)
}
define nonsqr(n)
{
return n + round(sqrt(n))
}
for(i=1; i < 23; i++) {
print nonsqr(i), "\n"
}
for(i=1; i < 1000000; i++) {
j = sqrt(nonsqr(i)) if ( j == floor(j) ) { print i, " square in the seq\n" }
}
quit</lang>
The function int and round are taken from here (int is slightly modified) (Here he states the license is GPL).
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
<lang 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</lang>
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>