Sequence of non-squares: Difference between revisions

From Rosetta Code
Content added Content deleted
(add Ruby)
Line 329: Line 329:
>>>
>>>
</lang>
</lang>

=={{header|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>


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

Revision as of 09:49, 11 June 2009

Task
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

Translation of: C
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<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

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

Works with: FreeBASIC
Works with: RapidQ

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

  1. include <math.h>
  2. include <stdio.h>
  3. 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

Works with: Fortran version 90 and later

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

  1. (* 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 = ()

  1. (* 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>

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>

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
Retrieved from "https://rosettacode.org/wiki/Sequence_of_non-squares?oldid=80513"