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
AutoHotkey
ahk forum: discussion <lang AutoHotkey>Loop 22
t .= (A_Index + floor(0.5 + sqrt(A_Index))) " "
MsgBox %t%
s := 0 Loop 1000000
x := A_Index + floor(0.5 + sqrt(A_Index)), s += x = round(sqrt(x))**2
Msgbox Number of bad squares = %s% ; 0</lang>
AWK
<lang awk> $ awk 'func f(n){return(n+int(.5+sqrt(n)))}BEGIN{for(i=1;i<=22;i++)print i,f(i)}' 1 2 2 3 3 5 4 6 5 7 6 8 7 10 8 11 9 12 10 13 11 14 12 15 13 17 14 18 15 19 16 20 17 21 18 22 19 23 20 24 21 26 22 27
$ awk 'func f(n){return(n+int(.5+sqrt(n)))}BEGIN{for(i=1;i<100000;i++){n=f(i);r=int(sqrt(n));if(r*r==n)print n"is square"}}' $ </lang>
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 ceil(x) {
auto intx intx=int(x) if (intx<x) intx+=1 return intx
}
define floor(x) {
return -ceil(-x)
}
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 functions int, round, floor, ceil 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>
Clojure
<lang clojure> n + floor(1/2 + sqrt(n))
- provides floor and sqrt, but we use Java's sqrt as it's faster
- (Clojure's is more exact)
(use 'clojure.contrib.math)
(defn nonsqr [#^Integer n] (+ n (floor (+ 0.5 (Math/sqrt n)))))
(defn square? [#^Double n]
(let [r (floor (Math/sqrt n))] (= (* r r) n)))
(doseq [n (range 1 23)] (printf "%s -> %s%n" n (nonsqr n))) (defn verify [] (not-any? square? (pmap nonsqr (range 1 1000001))) ) </lang>
Common Lisp
<lang lisp>(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)))))</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
<lang haskell>nonsqr :: Integral a => a -> a nonsqr n = n + round (sqrt (fromIntegral n))</lang>
> 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
IDL
<lang IDL> n = lindgen(1000000)+1 ; Take a million numbers
f = n+floor(.5+sqrt(n)) ; Apply formula print,f[0:21] ; Output first 22 print,where(sqrt(f) eq fix(sqrt(f))) ; Test for squares</lang>
Output:
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 -1
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>
Logo
<lang logo>repeat 22 [print sum # round sqrt #]</lang>
Modula-3
<lang modula3>MODULE NonSquare EXPORTS Main;
IMPORT IO, Fmt, Math;
VAR i: INTEGER;
PROCEDURE NonSquare(n: INTEGER): INTEGER =
BEGIN RETURN n + FLOOR(0.5D0 + Math.sqrt(FLOAT(n, LONGREAL))); END NonSquare;
BEGIN
FOR n := 1 TO 22 DO IO.Put(Fmt.Int(NonSquare(n)) & " "); END; IO.Put("\n"); FOR n := 1 TO 1000000 DO i := NonSquare(n); IF i = FLOOR(Math.sqrt(FLOAT(i, LONGREAL))) THEN IO.Put("Found square: " & Fmt.Int(n) & "\n"); END; END;
END NonSquare.</lang> Output:
2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27
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 1_000_000 do let j = sqrt (float (nonsqr i)) in assert (j <> floor j) done;;
- : unit = ()</lang>
Perl
<lang perl>sub nonsqr { my $n = shift; $n + int(0.5 + sqrt($n)) } print join(' ', map nonsqr($_), 1..22), "\n"; foreach my $i (1..1_000_000) {
my $j = sqrt(nonsqr($i)); $j != int($j) or die "Found a square in the sequence: $i";
}</lang>
PowerShell
Implemented as a filter here, which can be used directly on the pipeline. <lang powershell>filter Get-NonSquare {
return $_ + [Math]::Floor(1/2 + [Math]::Sqrt($_))
}</lang> Printing out the first 22 values is straightforward, then: <lang powershell>1..22 | Get-NonSquare</lang> If there were any squares for n up to one million, they would be printed with the following, but there is no output: <lang powershell>1..1000000 `
| Get-NonSquare ` | Where-Object { $r = [Math]::Sqrt($_) [Math]::Truncate($r) -eq $r }</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>
R
Printing the first 22 nonsquares. <lang R>nonsqr <- function(n) n + floor(1/2 + sqrt(n)) nonsqr(1:22)</lang>
[1] 2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27
Testing the first million nonsquares. <lang R>is.square <- function(x) {
sqrx <- sqrt(x) err <- abs(sqrx - round(sqrx)) err < 100*.Machine$double.eps
} any(is.square(nonsqr(1:1e6)))</lang>
[1] FALSE
Ruby
<lang ruby>f = lambda {|n| n + (1.0/2 + Math.sqrt(n)).floor} 1.upto(22) {|n| puts "#{n} #{f.call n}"} 1.upto(1_000_000) do |n|
i = f.call n if i == (Math.sqrt(i).to_int)**2 fail "Oops, found a square f(#{n}) = #{i}" endend
puts "done"</lang>
Standard ML
<lang sml>- fun nonsqr n = n + round (Math.sqrt (real n)); val nonsqr = fn : int -> int - List.tabulate (23, nonsqr); val it = [0,2,3,5,6,7,8,10,11,12,13,14,...] : int list - let fun loop i = if i = 1000000 then true
else let val j = Math.sqrt (real (nonsqr i)) in Real.!= (j, Real.realFloor j) andalso loop (i+1) end in loop 1 end;
val it = true : bool</lang>
Tcl
<lang tcl>package require Tcl 8.5
set f {n {expr {$n + floor(0.5 + sqrt($n))}}}
for {set x 1} {$x <= 22} {incr x} {
puts [format "%d\t%s" $x [apply $f $x]]
}
puts "looking for a square..." for {set x 1} {$x <= 1000000} {incr x} {
set y [apply $f $x] set s [expr {sqrt($y)}] if {$s == int($s)} { error "found a square in the sequence: $x -> $y" }
} puts "done"</lang> outputs
1 2.0 2 3.0 3 5.0 4 6.0 5 7.0 6 8.0 7 10.0 8 11.0 9 12.0 10 13.0 11 14.0 12 15.0 13 17.0 14 18.0 15 19.0 16 20.0 17 21.0 18 22.0 19 23.0 20 24.0 21 26.0 22 27.0 looking for a square... done
TI-89 BASIC
Definition and 1 to 22, interactively:
■ n+floor(1/2+√(n)) → f(n) Done ■ seq(f(n),n,1,22) {2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27}
Program testing up to one million:
test() Prgm Local i, ns For i, 1, 10^6 f(i) → ns If (floor(√(ns)))^2 = ns Then Disp "Oops: " & string(ns) EndIf EndFor Disp "Done" EndPrgm
(This program has not been run to completion.)
Ursala
<lang Ursala>#import nat
- import flo
nth_non_square = float; plus^/~& math..trunc+ plus/0.5+ sqrt is_square = sqrt; ^E/~& math..trunc
- show+
examples = %neALP ^(~&,nth_non_square)*t iota23 check = (is_square*~+nth_non_square*t; ~&i&& %eLP)||-[no squares found]-! iota 1000000</lang> output:
< 1: 2.000000e+00, 2: 3.000000e+00, 3: 5.000000e+00, 4: 6.000000e+00, 5: 7.000000e+00, 6: 8.000000e+00, 7: 1.000000e+01, 8: 1.100000e+01, 9: 1.200000e+01, 10: 1.300000e+01, 11: 1.400000e+01, 12: 1.500000e+01, 13: 1.700000e+01, 14: 1.800000e+01, 15: 1.900000e+01, 16: 2.000000e+01, 17: 2.100000e+01, 18: 2.200000e+01, 19: 2.300000e+01, 20: 2.400000e+01, 21: 2.600000e+01, 22: 2.700000e+01> no squares found