Sequence of non-squares: Difference between revisions

;Task:

Show that the following remarkable formula gives the [http://www.research.att.com/~njas/sequences/A000037 sequence] of non-square [[wp:Natural_number|natural numbers]]:

* Print out the values for &nbsp; <big> n </big> &nbsp; in the range &nbsp; '''1''' &nbsp; to &nbsp; '''22'''

* Show that no squares occur for &nbsp; <big> n </big> &nbsp; less than one million

 

 

<br><br>

 

=={{header|Ada}}==

with Ada.Text_IO; use Ada.Text_IO;

 

end if;

end loop;

{{out}}

<pre>

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

 

main: (

FI

OD

{{out}}

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

 

=={{header|ALGOL W}}==

% check values of the function: f(n) = n + floor(1/2 + sqrt(n)) %

% are not squares %

else write( "f(n) produced a square" )

 

{{out}}

<pre>

=={{header|APL}}==

Generate the first 22 numbers:

NONSQUARE 22

Show there are no squares in the first million:

HOWMANYSQUARES NONSQUARE 1000000

 

=={{header|AutoHotkey}}==

ahk forum: [http://www.autohotkey.com/forum/post-276683.html#276683 discussion]

t .= (A_Index + floor(0.5 + sqrt(A_Index))) " "

MsgBox %t%

Loop 1000000

x := A_Index + floor(0.5 + sqrt(A_Index)), s += x = round(sqrt(x))**2

 

=={{header|AWK}}==

1 2

2 3

 

$ 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"}}'

 

=={{header|BASIC}}==

{{works with|FreeBASIC}}

{{works with|RapidQ}}

DIM j AS Double

DIM found AS Integer

END IF

NEXT i

 

=={{header|BBC BASIC}}==

S% = N% + SQR(N%) + 0.5

PRINT S%

IF S%/R% = R% STOP

NEXT

{{out}}

<pre>

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.

 

 

scale = 20

}

 

 

The functions int, round, floor, ceil are taken from [http://www.pixelbeat.org/scripts/bc here] (int is slightly modified) ([http://www.pixelbeat.org/scripts/ Here] he states the license is GPL).

 

 

1 22r@{?s0.5?+av?+}[m

 

=={{header|C}}==

#include <stdio.h>

#include <assert.h>

}

return 0;

 

=={{header|C sharp|C#}}==

using System.Diagnostics;

 

}

}

 

=={{header|C++}}==

#include <algorithm>

#include <vector>

}

return 0 ;

{{out}}

<pre>

</pre>

 

 

;; (Clojure's is more exact)

(use 'clojure.contrib.math)

(doseq [n (range 1 23)] (printf "%s -> %s\n" n (nonsqr n)))

 

 

=={{header|CoffeeScript}}==

non_square = (n) -> n + Math.floor(1/2 + Math.sqrt(n))

 

 

console.log "success"

 

{{out}}

{{works with|CCL}}

 

(flet ((non-square (n)

"Compute the N-th number of the non-square sequence"

:when (squarep (non-square n))

:do (format t "Found a square: ~D -> ~D~%"

 

=={{header|D}}==

 

int nonSquare(in int n) pure nothrow @safe @nogc {

assert(ns != (cast(int)real(ns).sqrt) ^^ 2);

}

{{out}}

<pre>[2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27]</pre>

 

=={{header|EchoLisp}}==

(lib 'sequences)

 

(filter square? (take A000037 1000000))

→ null

 

=={{header|Eiffel}}==

class

APPLICATION

end

 

{{out}}

<pre>

 

=={{header|Elixir}}==

 

IO.inspect for n <- 1..22, do: f.(n)

nil -> IO.puts "No squares found below #{n}"

val -> IO.puts "Error: number is a square: #{val}"

 

{{out}}

 

=={{header|Erlang}}==

-module(non_squares).

-export([main/0]).

non_square(N) ->

N+trunc(1/2+ math:sqrt(N)).

 

=={{header|Euphoria}}==

This is based on the [[BASIC]] and [[Go]] examples.

return n + floor( 0.5 + sqrt( n ) )

end function

if found = 0 then

puts( 1, "No squares found\n" )

 

=={{header|F_Sharp|F#}}==

 

let SequenceOfNonSquares =

|> Seq.map(fun f -> (f, nonsqr f))

|> Seq.filter(fun f -> IsSquare(snd f))

 

> SequenceOfNonSquares;;

 

=={{header|Factor}}==

sequences ;

 

each ;

 

{{out}}

<pre>

=={{header|Fantom}}==

 

class Main

{

}

}

 

=={{header|Forth}}==

: f>u f>d drop ;

 

: square? ( n -- ? ) u>f fsqrt fdup fround f- f0= ;

: test ( n -- ) 1 do i fn square? if cr i . ." fn was square" then loop ;

 

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

 

IMPLICIT NONE

END DO

 

 

=={{header|FreeBASIC}}==

 

Function nonSquare (n As UInteger) As UInteger

Print

Print "Press any key to quit"

 

{{out}}

 

=={{header|GAP}}==

# non-squares function is better done with a generator.

 

 

ForAll([1 .. 1000000], i -> a() = b());

 

=={{header|Go}}==

I assume it's obvious that the function monotonically increases, thus it's enough to just watch for the next possible square. If a square is found, the panic will cause an ugly stack trace.

 

import (

}

fmt.Println("No squares occur for n <", limit)

{{out}}

<pre>

 

Solution:

 

Test Program:

 

{{out}}

 

=={{header|Haskell}}==

 

> map nonsqr [1..22]

Or, in a point-free variation, defining a 'main' for the compiler (rather than interpreter)

 

 

 

nonSqr :: Int -> Int

nonSqr = (+) <*> (round . root)

 

 

main :: IO ()

main =

mapM_

putStrLn

{{Out}}

<pre>First 22 members of the series:

 

=={{header|HicEst}}==

 

nonSqr = $ + FLOOR(0.5 + $^0.5)

ENDDO

WRITE(Name) squares_found

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

squares_found=0; </pre>

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

procedure nsq(n) # return non-squares

return n + floor(0.5 + sqrt(n))

{{libheader|Icon Programming Library}}

[http://www.cs.arizona.edu/icon/library/src/procs/numbers.icn numbers provides floor]

 

=={{header|IDL}}==

f = n+floor(.5+sqrt(n)) ; Apply formula

print,f[0:21] ; Output first 22

 

{{out}}

 

=={{header|J}}==

 

rf 1+i.22 NB. Results from 1 to 22

 

+/ (rf e. *:) 1+i.1e6 NB. Number of square RFs <= 1e6

 

=={{header|Java}}==

public static int nonsqr(int n) {

return n + (int)Math.round(Math.sqrt(n));

}

}

 

=={{header|JavaScript}}==

Iterative

 

for (var i = 1; i < 23; i++) a[i] = i + Math.floor(1/2 + Math.sqrt(i));

console.log(a);

for (i = 1; i < 1000000; i++) if (Number.isInteger(i + Math.floor(1/2 + Math.sqrt(i))) === false) {

console.log("The ",i,"th element of the sequence is a square");

 

===ES6===

 

By functional composition

 

 

// nonSquare :: Int -> Int

 

 

 

 

 

 

};

 

 

 

 

 

{{Out}}

 

=={{header|jq}}==

{{works with|jq|1.4}}

 

def is_square: sqrt | . == floor;

(range(1;23) | A000037),

"Check for squares for n up to 1e6:",

{{out}}

For n up to and including 22:

2

27

Check for squares for n up to 1e6:

 

=={{header|Julia}}==

 

{{out}}

<pre>nonsquare.(1:1000000) ∩ collect(1:1000) .^ 2 = Int64[]</pre>

 

=={{header|K}}==

{{out}}

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

{{out}}

<pre>0</pre>

 

=={{header|Kotlin}}==

 

fun f(n: Int) = n + Math.floor(0.5 + Math.sqrt(n.toDouble())).toInt()

if (squares.size == 0) println("There are no squares for n less than one million")

else println("Squares are generated for the following values of n: $squares")

 

{{out}}

There are no squares for n less than one million

</pre>

 

=={{header|Liberty BASIC}}==

for i = 1 to 22

print nonsqr( i); " ";

nonsqr = n +int( 0.5 +n^0.5)

end function

<pre>

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

 

=={{header|Logo}}==

 

=={{header|Lua}}==

return n + math.floor(1/2 + math.sqrt(n))

end

end

end

{{out}}

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

No squares found</pre>

 

=={{header|Maple}}==

with(NumberTheory):

 

 

number;

 

{{out}}<pre>

 

</pre>

nonsq@Range[22]

If[! Or @@ (IntegerQ /@ Sqrt /@ nonsq@Range[10^6]),

Print["No squares for n <= ", 10^6]

{{out}}

<pre>{2, 3, 5, 6, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21, 22, 23, 24, 26, 27}

 

=={{header|MATLAB}}==

 

for n = (1:i)

fprintf('\nNo square numbers were generated for n <= %d\n',i);

Solution:

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

 

=={{header|Maxima}}==

makelist(nonsquare(n), n, 1, 20);

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

u: makelist(i, i, 1, m)$

is(sublist(u, not_square) = sublist(map(nonsquare, u), lambda([x], x <= m)));

 

=={{header|min}}==

{{works with|min|0.19.3}}

(sqrt dup floor - 0 ==) :sq?

(:n =q 1 'dup q concat 'succ concat n times pop) :upto

(non-sq print! " " print!) 22 upto newline

"Squares for n below one million:" puts!

{{out}}

<pre>

Squares for n below one million:

</pre>

 

=={{header|МК-61/52}}==

 

=={{header|MMIX}}==

GREG @

buf OCTA 0,0

LDA $255,NL

TRAP 0,Fputs,StdOut

{{out}}

<pre>~/MIX/MMIX/Rosetta> mmix SoNS

 

=={{header|Modula-3}}==

 

IMPORT IO, Fmt, Math;

END;

END;

{{out}}

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

 

=={{header|Nim}}==

for i in 1..n:

 

 

{{out}}

 

=={{header|OCaml}}==

val nonsqr : int -> int = <fun>

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

assert (j <> floor j)

done;;

 

=={{header|Oforth}}==

 

 

 

{{out}}

 

=={{header|Ol}}==

(import (lib math))

 

; ==> ()

 

 

=={{header|Oz}}==

fun {NonSqr N}

N + {Float.toInt {Floor 0.5 + {Sqrt {Int.toFloat N}}}}

in

{Show {List.take Ns 22}}

 

=={{header|PARI/GP}}==

 

=={{header|Pascal}}==

{{libheader|Math}}

 

uses

writeln('square found for n = ', n);

end;

{{out}}

<pre>:> ./SequenceOfNonSquares

a little speedup in testing upto 1 billion.

5 secs instead of 21 secs using fpc2.6.4

//sequence of non-squares

//n = i + floor(1/2 + sqrt(i))

First22;

Test(1000*1000*1000);

 

=={{header|Perl}}==

 

print join(' ', map nonsqr($_), 1..22), "\n";

my $root = sqrt nonsqr($i);

die "Oops, nonsqr($i) is a square!" if $root == int $root;

 

{{out}}

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

 

=={{header|Phix}}==

{{out}}

<pre>

none found {1001,1002001}

</pre>

 

=={{header|PHP}}==

//First Task

for($i=1;$i<=22;$i++){

echo("Up to 1000000, found no square number in the sequence!");

}

{{Out}}

<pre>>php nsqrt.php

Up to 1000000, found no square number in the sequence!

></pre>

 

=={{header|PicoLisp}}==

(+ N (sqrt N T)) ) # 'sqrt' rounds when called with 'T'

 

(let (N (sqfun I) R (sqrt N))

(when (= N (* R R))

{{out}}

<pre>1 2

 

=={{header|PL/I}}==

put skip edit ((n, n + floor(sqrt(n) + 0.5) do n = 1 to n))

(skip, 2 f(5));

 

Results:

 

1 2

2 3

20 24

21 26

 

Test 1,000,000 values:

 

test: proc options (main);

declare n fixed (15);

 

end test;

 

=={{header|PostScript}}==

/issquare { dup sqrt floor dup mul eq } def

 

} if pop

} for

{{out}} (lack of error message shows none below 1000 produced a square)

<pre>

=={{header|PowerShell}}==

Implemented as a filter here, which can be used directly on the pipeline.

return $_ + [Math]::Floor(1/2 + [Math]::Sqrt($_))

Printing out the first 22 values is straightforward, then:

If there were any squares for ''n'' up to one million, they would be printed with the following, but there is no output:

| Get-NonSquare `

| Where-Object {

$r = [Math]::Sqrt($_)

[Math]::Truncate($r) -eq $r

 

=={{header|PureBasic}}==

For a = 1 To 22

; Integer, so no floor needed

EndIf

; Wait for enter

 

=={{header|Python}}==

>>> def non_square(n):

return n + floor(1/2 + sqrt(n))

----> 2 next(filter(is_square, non_squares))

 

 

 

 

{{Works with|Python|3.7}}

 

from itertools import count, islice

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>OEIS A000037

True if any of the first 10^6 terms are perfect squares:

False</pre>

 

=={{header|R}}==

Printing the first 22 nonsquares.

[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.

{

sqrx <- sqrt(x)

err < 100*.Machine$double.eps

}

[1] FALSE

 

=={{header|Racket}}==

 

#lang racket

 

(for/or ([n (in-range 1 1000001)])

(square? (non-square n)))

 

{{out}}

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

#f

</pre>

 

:::* &nbsp; 8 &nbsp; = &nbsp; iSqrt(64)

:::* &nbsp; 8 &nbsp; = &nbsp; iSqrt(65)

parse arg N M . /*obtain optional arguments from the CL*/

if N=='' | N=="," then N= 22 /*Not specified? Then use the default.*/

say center(j, 20) center(j +floor(1/2 +sqrt(j)), 20)

end /*j*/

do k=1 for M /*have it step through a million of 'em*/

$= k + floor( sqrt(k) + .5 ) /*use the specified formula (algorithm)*/

end /*k*/

say; if #==0 then #= 'no' /*use gooder English for display below.*/

exit /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

do while #>1; #=#%4; _=x-r-#; r=r%2; if _<0 then iterate; x=_; r=r+#; end; return r

/*──────────────────────────────────────────────────────────────────────────────────────*/

sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); m.=9; numeric form; h=d+6

{{out|output}}

<pre>

 

=={{header|Ring}}==

for n=1 to 22

x = n + floor(1/2 + sqrt(n))

next

see nl

 

=={{header|Ruby}}==

n + (0.5 + Math.sqrt(n)).floor

end

(squares & non_squares).each do |n|

puts "Oops, found a square f(#{non_squares.index(n)}) = #{n}"

 

=={{header|Rust}}==

{{works with|Rust|1.1}}

fn f(n: i64) -> i64 {

n + (0.5 + (n as f64).sqrt()) as i64

println!("{} unexpected squares found", count);

}

 

=={{header|Scala}}==

for(n<-1 to 22) println(n + " "+ nonsqr(n))

j==math.floor(j)

}

 

=={{header|Scheme}}==

(lambda (index)

(+ index (inexact->exact (floor (+ (/ 1 2) (sqrt index)))))))

 

(display ((any? square?) (((sequence non-squares) 1) 999999)))

{{out}}

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

 

=={{header|Seed7}}==

include "float.s7i";

include "math.s7i";

end if;

end for;

 

=={{header|Sidef}}==

{|i| nonsqr(i) }.map(1..22).join(' ').say

 

die "Found a square in the sequence: #{i}"

}

 

=={{header|Smalltalk}}==

nonSquare := [:n |

n + (n sqrt) rounded

].

Transcript show: 'Squares found for values up to 1,000,000: ';

 

=={{header|Standard ML}}==

val nonsqr = fn : int -> int

- List.tabulate (23, nonsqr);

loop 1

end;

 

=={{header|Tcl}}==

 

set f {n {expr {$n + floor(0.5 + sqrt($n))}}}

}

}

{{out}}

<pre>1 2.0

Definition and 1 to 22, interactively:

 

Done

■ seq(f(n),n,1,22)

 

Program testing up to one million:

 

Prgm

Local i, ns

EndFor

Disp "Done"

 

(This program has not been run to completion.)

 

=={{header|Ursala}}==

#import flo

 

 

examples = %neALP ^(~&,nth_non_square)*t iota23

{{out}}

<pre>

no squares found

</pre>

=={{header|VBA}}==

Sub Main()

Dim i&, c&, j#, s$

Private Function ns(l As Long) As Long

ns = l + Int(1 / 2 + Sqr(l))

{{out}}

<pre>values for n in the range 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,

0 squares less than 1000000</pre>

=={{header|XLISP}}==

(+ n (floor (+ 0.5 (sqrt n)))))

 

(print (mapcar non-square (range 1 23)))

 

{{out}}

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

 

=={{header|XPL0}}==

 

func real Floor(X); \Truncate X toward - infinity

M0:= M;

];

 

{{out}}

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

</pre>

 

=={{header|zkl}}==

[1..22].apply(seq).toString(*).println();

 

isSquare(25) //-->True

isSquare(26) //-->False

modf returns the integer and fractional parts of a float

{{out}}