Find square difference

From Rosetta Code
Revision as of 23:20, 13 March 2023 by Steenslag (talk | contribs) (→‎{{header|Ruby}}: Add Ruby)
Find square difference is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task


Find and show on this page the least positive integer number n, where difference of n*n and (n-1)*(n-1) greater than 1000.
The result is 501 because 501*501 - 500*500 = 251001 - 250000 = 1001 > 1000.



11l

L(n) 1..
   I n^2 - (n - 1)^2 > 1000
      print(n)
      L.break
Output:
501

Ada

with Ada.Text_IO; use Ada.Text_IO;

procedure Find_Square_Difference is
   Last   : Natural := 0;
   Square : Positive;
   Diff   : Positive;
begin
   for N in 1 .. Positive'Last loop
      Square := N ** 2;
      Diff   := Square - Last;
      Last   := Square;
      if Diff > 1000 then
         Put_Line (N'Image);
         exit;
      end if;
   end loop;
end Find_Square_Difference;
Output:
 501

ALGOL 68

Also shows the least positive integer where the difference between n^2 and (n-1)^2 is greater than 32 000 and 2 000 000 000. 

BEGIN # find the lowest positive n where the difference between n^2 and (n-1)^2 is > 1000 #
    # shows the smalled square n where n^2 - (n-1)^2 is greater than required difference  # 
    #       n^2 - ( n - 1 )^2 is n^2 - n^2 + 2n - 1, i.e. 2n - 1                          #
    #       so 2n - 1 > required difference or n > ( required difference + 1 ) / 2        #
    PROC show least square = ( INT required difference )VOID:
        print( ( "Smallest n where n^2 - (n-1)^2 is > ", whole( required difference, -12 )
               , " is: ", whole( ( ( required difference + 1 ) OVER 2 ) + 1, -12 )
               , newline
               )
             );
    show least square(         1 000 );
    show least square(        32 000 );
    show least square( 2 000 000 000 )
END
Output:
Smallest n where n^2 - (n-1)^2 is >         1000 is:          501
Smallest n where n^2 - (n-1)^2 is >        32000 is:        16001
Smallest n where n^2 - (n-1)^2 is >   2000000000 is:   1000000001

ALGOL W

begin % find the lowest positive n where the difference between n^2 and (n-1)^2 is > 1000 %
    integer requiredDifference;
    requiredDifference := 1000;
    write(  i_w := 1, s_w := 0,
         , "Smallest n where n^2 - (n-1)^2 is > ", requiredDifference
         , " is: ", ( ( requiredDifference + 1 ) div 2 ) + 1
         )
end.
Output:
Smallest n where n^2 - (n-1)^2 is > 1000 is: 501

Arturo

i: new 1
while ø [
    if 1000 < (i^2)-(dec i)^2
        -> break
    inc 'i
]
print i
Output:
501

Asymptote

int fpow(int n) {
  int i = 0;
  while (i^2 - (i-1)^2 < n) ++i;
  return i;
}

write(fpow(1000));

AutoHotkey

while ((n:=A_Index)**2 - (n-1)**2 < 1000)
    continue
MsgBox % result := n
Output:
501

AWK

# syntax: GAWK -f FIND_SQUARE_DIFFERENCE.AWK
BEGIN {
    n = 1001
    while (i^2-(i-1)^2 < n) {
      i++
    }
    printf("%d\n",i)
    exit(0)
}
Output:
501

BASIC

BASIC256

function fpow(n)
	i = 0
	while i^2 - (i-1)^2 < n
		i += 1
	end while
	Return i
end function

print fpow(1001)
end

PureBasic

Procedure fpow(n.i)
  Define i.i
  While Pow(i, 2) - Pow((i-1), 2) < n
    i + 1
  Wend
  ProcedureReturn i
EndProcedure

OpenConsole()
Print(Str(fpow(1001)))
Input()
CloseConsole()

QBasic

FUNCTION fpow (n)
    WHILE (i * i) - ((i - 1) * (i - 1)) < n
        i = i + 1
    WEND
    fpow = i
END FUNCTION

PRINT fpow(1001)

Run BASIC

function fpow(n)
    while i^2-(i-1)^2 < n
        i = i+1
    wend
    fpow = i
end function
 
print fpow(1001)

True BASIC

FUNCTION fpow (n)
    DO WHILE i ^ 2 - (i - 1) ^ 2 < n
       LET i = i + 1
    LOOP
    LET fpow = I
END FUNCTION

PRINT fpow(1001)
END

Tiny BASIC

    LET N = 1001

    LET I = 0
10  LET R = I*I - (I-1)*(I-1)
    IF R >= N THEN GOTO 20
    IF R < N THEN LET I = I + 1
    GOTO 10
20  PRINT I
    END

Yabasic

sub fpow(n)
    while i^2 - (i-1)^2 < n
        i = i + 1
    wend
    Return i
end sub

print fpow(1001)
end


bc

(1000 + 1) / 2 + 1
Output:
501

C

#include<stdio.h>
#include<stdlib.h>

int f(int n) {
    int i, i1;
    for(i=1;i*i-i1*i1<n;i1=i, i++);
    return i;
}

int main(void) {
    printf( "%d\n", f(1000) );
    return 0;
}
Output:
501

C++

The C solution is also idomatic in C++. An alterate approach is to use Ranges from C++20. 

#include <iostream>
#include <ranges>

int main()
{
    const int maxSquareDiff = 1000;
    auto squareCheck = [maxSquareDiff](int i){return 2 * i - 1 > maxSquareDiff;};
    auto answer = std::views::iota(1) |  // {1, 2, 3, 4, 5, ....}
      std::views::filter(squareCheck) |  // filter out the ones that are below 1000
      std::views::take(1);               // take the first one
    std::cout << answer.front() << '\n';
}
Output:
501

Dart

import 'dart:math';

int leastSquare(int gap) {
  for (int n = 1;; n++) {
    if (pow(n, 2) - pow((n - 1), 2) > gap) {
      return n;
    }
  }
}

void main() {
  print(leastSquare(1000));
}
Output:
501

dc

1000 1+2/1+p
Output:
501

EasyLang

repeat
   i += 1
   square = pow i 2
   diffSquare = pow (i - 1) 2
   difference = square - diffSquare
   until difference > 1000
.
print i

F#

let n=1000 in printfn $"%d{((n+1)/2)+1}"
Output:
501

Factor

The difference between squares is the odd numbers, so ls(n)=⌈n/2+1⌉.

Works with: Factor version 0.99 2021-06-02
USING: math math.functions prettyprint ;

: least-sq ( m -- n ) 2 / 1 + ceiling ;

1000 least-sq .
Output:
501

Fermat

Func F(n) =
    i:=0;
    while i^2-(i-1)^2<n do i:=i+1 od; i.;

!!F(1000);
Output:
501

Forth

Works with: gforth version 0.7.3
Translation of: Quackery
: square dup * ;
: square-diff
  0 begin 1+
  dup square over 1- square -
  1000 > until . ;

square-diff
Output:
501  ok


FreeBASIC

function fpow(n as uinteger) as uinteger
    dim as uinteger i
    while i^2-(i-1)^2 < n
        i+=1
    wend
    return i
end function

print fpow(1001)
Output:
501

Go

package main

import (
    "fmt"
    "math"
)

func squareDiff(k int) int {
    return int(math.Ceil(float64(k+1) * 0.5))
}

func main() {
    fmt.Println(squareDiff(1000))
}
Output:
501

Haskell

The sequence of differences between successive squares is the sequence of odd numbers. 

import Data.List (findIndex)

f = succ . flip div 2

-- Or, with redundant verbosity

g n = i
  where
    Just i = succ <$> findIndex (> n) [1, 3 ..]

main = mapM_ print $ [f, g] <*> [1000]
Output:
501
501

J

Through inspection, we can see that the "square difference' for a number n is (2*n)-1: 

   (*: - *:&<:) 1 2 3 4 5
1 3 5 7 9

Therefore, we expect that n=501 would give us a "square difference' of 1001. Testing, we can see that this is the case: 

   (*: - *:&<:) 501
1001

Joy

1000 succ 2 / succ.
Output:
501

jq

Works with: jq

Works with gojq, the Go implementation of jq

So this question is essentially asking to solve `2n - 1 > 1000`. Wow.

At the risk of hastening RC's demise, one could offer a jq solution like so: 

first( range(1; infinite) | select( 2 * . - 1 > 1000 ) )

Or, for anyone envious of Bitcoin's contribution to global warming: 

first( range(1; infinite) | select( .*. - ((.-1) | .*.) > 1000 ) )
Output:
501

Julia

julia> findfirst(n -> n*n - (n-1)*(n-1) > 1000, 1:1_000_000)
501

OCaml

let calculate x =
  succ (succ x lsr 1)

let () =
  Printf.printf "%u\n" (calculate 1000)
Output:
501

Pari/GP

F(n)=i=0;while(i^2-(i-1)^2<n,i=i+1);return(i);
print(F(1000))
Output:
501

Pencil and Paper

Find the smallest positive integer number n, where the difference of n2 and (n - 1)2 is greater than 1000. 

r: roots of squares
s: successive squares
d: differences between successive squares,
   (a.k.a, the list of positive odd integers)

r: 0, 1, 2, 3,  4,  5,  6,  7,  8,  9,  10, ...
s: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...
d: 1, 3, 5, 7,  9, 11, 13, 15, 17, 19, ...

r: n
s: n * n
d: n * 2 + 1

solve for d > 1,000
the first odd integer greater than 1,000 is 1,001
(1,001 + 1) / 2 = 501 ( = n)

Perl

#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Least_square
use warnings;

my $n = 1;
$n++ until $n ** 2 - ($n-1) ** 2 > 1000;
print "$n\n";
Output:
501

Phix

Essentially Wren equivalent, but explained in excruciating detail especially for enyone that evidently needs elp, said Eeyore. 

with javascript_semantics
printf(1,"""
n*n - (n - 1)*(n - 1) > 1000
n*n - (n*n - 2*n + 1) > 1000
n*n - n*n + 2*n - 1 > 1000
2*n - 1 > 1000
2*n > 1001
n > 500.5
n = %d
""",ceil(500.5))
Output:
n*n - (n - 1)*(n - 1) > 1000
n*n - (n*n - 2*n + 1) > 1000
n*n - n*n + 2*n - 1 > 1000
2*n - 1 > 1000
2*n > 1001
n > 500.5
n = 501

Or if you prefer, same output: 

with javascript_semantics
string e                                                -- equation
procedure p(string s)
    e := s                                              -- set/save
    printf(1,"%s\n",s)
end procedure
p("n*n - (n - 1)*(n - 1) > 1000")                       -- original
p(substitute(e,"(n - 1)*(n - 1)",                   
               "(n*n - 2*n + 1)"))                      -- expand
string{l,m,r} = scanf(e,"%s - (%s)%s")[1]
m = substitute_all(m,"-+|","|-+")                       -- unsign
p(sprintf("%s - %s%s",{l,m,r}))
p(substitute(e,"n*n - n*n + ",""))                      -- eliminate
p(substitute_all(e,{" - 1","1000"},{"","1001"}))        -- add 1
p(substitute_all(e,{"2*","1001"},{"","500.5"}))         -- divide by 2
p(substitute(e,"> 500.5",sprintf("= %d",ceil(500.5))))  -- solve

or even: 

without js -- (user defined types are not implicitly called)
type pstring(string s) printf(1,"%s\n",s) return true end type
pstring e                                               -- equation
e = "n*n - (n - 1)*(n - 1) > 1000"                      -- original
e = substitute(e,"(n - 1)*(n - 1)",                 
                 "(n*n - 2*n + 1)")                     -- expand
string{l,m,r} = scanf(e,"%s - (%s)%s")[1]
m = substitute_all(m,"-+|","|-+")                       -- unsign
e = sprintf("%s - %s%s",{l,m,r})
e = substitute(e,"n*n - n*n + ","")                     -- eliminate
e = substitute_all(e,{" - 1","1000"},{"","1001"})       -- add 1
e = substitute_all(e,{"2*","1001"},{"","500.5"})        -- divide by 2
e = substitute(e,"> 500.5",sprintf("= %d",ceil(500.5))) -- solve

Phixmonti

/# Rosetta Code problem: http://rosettacode.org/wiki/Find_square_difference
by Galileo, 10/2022 #/

def >1000
    dup dup * over 1 - dup * - 1001 <
enddef

0 true while 1 + >1000 endwhile print
Output:
501
=== Press any key to exit ===

PL/M

This can be compiled with the original 8080 PL/M compiler and run under CP/M or an emulator.
Note that the original 8080 PL/M compiler only supports 8 and 16 bit unisgned numbers. 

100H: /* FIND THE LEAST +VE N WHERE N SQUARED - (N-1) SQUARED > 1000 */

   BDOS: PROCEDURE( FN, ARG ); /* CP/M BDOS SYSTEM CALL */
      DECLARE FN BYTE, ARG ADDRESS;
      GOTO 5;
   END BDOS;
   PR$CHAR:   PROCEDURE( C ); DECLARE C BYTE;    CALL BDOS( 2, C ); END;
   PR$STRING: PROCEDURE( S ); DECLARE S ADDRESS; CALL BDOS( 9, S ); END;
   PR$NL:     PROCEDURE; CALL PR$CHAR( 0DH ); CALL PR$CHAR( 0AH );  END;
   PR$NUMBER: PROCEDURE( N );
      DECLARE N ADDRESS;
      DECLARE V ADDRESS, N$STR( 6 ) BYTE, W BYTE;
      V = N;
      W = LAST( N$STR );
      N$STR( W ) = '$';
      N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      DO WHILE( ( V := V / 10 ) > 0 );
         N$STR( W := W - 1 ) = '0' + ( V MOD 10 );
      END;
      CALL PR$STRING( .N$STR( W ) );
   END PR$NUMBER;

   PRINT$LEAST: PROCEDURE( DIFF );
      DECLARE DIFF ADDRESS;
      CALL PR$STRING( . 'THE LOWEST N WHERE THE SQUARES OF N AND N-1 $' );
      CALL PR$STRING( . 'DIFFER BY MORE THAN $' );
      CALL PR$NUMBER( DIFF );
      CALL PR$STRING( .' IS: $' );
      CALL PR$NUMBER( ( ( DIFF + 1 ) / 2 ) + 1 );
      CALL PR$NL;
   END PRINT$LEAST ;
   CALL PRINT$LEAST(  1000 );
   CALL PRINT$LEAST( 32000 );
   CALL PRINT$LEAST( 65000 );

EOF
Output:
THE LOWEST N WHERE THE SQUARES OF N AND N-1 DIFFER BY MORE THAN 1000 IS: 501
THE LOWEST N WHERE THE SQUARES OF N AND N-1 DIFFER BY MORE THAN 32000 IS: 16001
THE LOWEST N WHERE THE SQUARES OF N AND N-1 DIFFER BY MORE THAN 65000 IS: 32501

Plain English

Library: Plain English-output
To run:
Start up.
Put 1 into a counter.
Loop.
If the counter does have a square difference, write the counter to the output; break.
Bump the counter.
Repeat.
Wait for the escape key.
Shut down.

To decide if a number does have a square difference:
Put the number into another number.
Raise the other number to 2.
Put the number into a third number.
Subtract 1 from the third number.
Raise the third number to 2.
If the other number minus the third number is greater than 1000, say yes.
Say no.

Python

import math
print("working...")
limit1 = 6000
limit2 = 1000
oldSquare = 0
newSquare = 0

for n in range(limit1):
    newSquare = n*n
    if (newSquare - oldSquare > limit2):
     print("Least number is = ", end = "");
     print(int(math.sqrt(newSquare)))
     break
    oldSquare = n*n

print("done...")
print()
Output:
working...
Least number is = 501
done...

Quackery

  [ dup * ] is squared ( n --> n )
  
  0 
  [ 1+
    dup squared 
    over 1 - squared - 
    1000 > until ]
  echo
Output:
501

Using algebra

Noting that a²-b² ≡ (a+b)(a-b), and that in this instance a = b+1. 

  1000 2 / 1+ echo
Output:
501

Raku

say first { $_² - ($_-1)² > 1000 }, ^Inf;
Output:
501

Ring

load "stdlib.ring"
see "working..." + nl
limit1 = 6000
limit2 = 1000
oldPrime = 0
newPrime = 0

for n = 1 to limit1
    newPrime = n*n
    if newPrime - oldPrime > limit2
       see "Latest number is = " + sqrt(newPrime) + nl
       exit
    ok
    oldPrime = n*n
next

see "done..." + nl
Output:
working...
Latest number is = 501
done...

RPL

≪ 1 1 
   DO
      SWAP 1 + DUP SQ
   UNTIL DUP 4 ROLL - 1000 > END DROP
≫ EVAL
Output:
1: 501

The above program takes 16.4 seconds to be executed on a HP-28S.

Algebraic approach

≪ 'n^2-(n-1)^2-1000'
   EXPAN COLCT 'n' ISOL CEIL
≫ EVAL

which returns the same result in only 9.2 seconds.

Ruby

p (1..).detect{|n| n*n - (n-1)*(n-1) > 1000 }
Output:
501

Sidef

var N = 1000

# Binary search
var n = bsearch_ge(1, N, {|k|
    k**2 - (k-1)**2 <=> N+1
})

# Closed-form
var m = ceil((N + 1 + N&1) / 2)

assert(n**2 - (n-1)**2 > N)
assert_eq(n, m)

say "#{n}^2 - #{n-1}^2 = #{n**2 - (n-1)**2}"
Output:
501^2 - 500^2 = 1001

Verilog

module main;
  integer i, n;
  
  initial begin
    n = 1000;
    i = 0;
    while (i ** 2 - (i - 1) ** 2 < n) i=i+1;
    $display(i);
    $finish ;
  end
endmodule

Wren

The solution n for some non-negative integer k needs to be such that: n² - (n² - 2n + 1) > k which reduces to: n > (k + 1)/2. 

var squareDiff = Fn.new { |k| ((k + 1) * 0.5).ceil }
System.print(squareDiff.call(1000))
Output:
501

XPL0

n^2 - (n - 1)^2 > 1000
n^2 - (n^2 - 2n + 1) > 1000
2n - 1 > 1000
2n > 1001
n > 500.5
n = 501
Retrieved from "https://rosettacode.org/w/index.php?title=Find_square_difference&oldid=338717"