Find square difference

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

<lang 11l>L(n) 1..

  I n^2 - (n - 1)^2 > 1000
     print(n)
     L.break</lang>

Output:

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. <lang algol68>BEGIN # find the lowest positive n where the difference between n^2 and (n-1)^2 is > 1000 #

   []INT test = ( 1 000, 32 000, 2 000 000 000 );
   FOR i FROM LWB test TO UPB test DO
       INT required difference = test[ i ];
       # n^2 - ( n - 1 )^2 is n^2 - n^2 + 2n - 1, i.e. 2n - 1 #
       # so 2n - 1 > reuired difference or n > reuired difference / 2 #
       print( ( "Smallest n where n^2 - (n-1)^2 is > ", whole( required difference, -12 )
              , " is: ", whole( ( ( required difference + 1 ) OVER 2 ) + 1, -12 )
              , newline
              )
            )
   OD

END</lang>

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

<lang pascal>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.</lang>

Output:

Smallest n where n^2 - (n-1)^2 is > 1000 is: 501

Arturo

<lang rebol>i: new 1 while ø [

   if 1000 < (i^2)-(dec i)^2
       -> break
   inc 'i

] print i</lang>

Output:

Asymptote

<lang Asymptote>int fpow(int n) {

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

}

write(fpow(1000));</lang>

AutoHotkey

<lang AutoHotkey>while ((n:=A_Index)**2 - (n-1)**2 < 1000)

   continue

MsgBox % result := n</lang>

Output:

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)

} </lang>

Output:

BASIC

BASIC256

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

print fpow(1001) end</lang>

PureBasic

<lang 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()</lang>

QBasic

<lang qbasic>FUNCTION fpow (n)

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

END FUNCTION

PRINT fpow(1001)</lang>

True BASIC

<lang qbasic>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 </lang>

Yabasic

<lang freebasic>sub fpow(n)

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

end sub

print fpow(1001) end</lang>

C

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

}</lang>

Output:

C++

The C solution is also idomatic in C++. An alterate approach is to use Ranges from C++20. <lang cpp>#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';

} </lang>

Output:

Dart

<lang 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));

}</lang>

Output:

F#

<lang fsharp> let n=1000 in printfn $"%d{((n+1)/2)+1}" </lang>

Output:

Factor

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

Works with: Factor version 0.99 2021-06-02

<lang factor>USING: math math.functions prettyprint ;

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

1000 least-sq .</lang>

Output:

Fermat

<lang>Func F(n) =

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

!!F(1000);</lang>

Output:

FreeBASIC

<lang 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)</lang>

Output:

Go

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

}</lang>

Output:

Haskell

The sequence of differences between successive squares is the sequence of odd numbers. <lang haskell>import Data.List (findIndex)

f = succ . flip div 2

-- Or, with redundant verbosity

g n =

 let Just i = findIndex (> n) [1, 3..]
 in  succ i

main = do

 print $ f 1000
 print $ g 1000</lang>

Output:

501
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: <lang jq>first( range(1; infinite) | select( 2 * . - 1 > 1000 ) )</lang> Or, for anyone envious of Bitcoin's contribution to global warming: <lang jq> first( range(1; infinite) | select( .*. - ((.-1) | .*.) > 1000 ) ) </lang>

Output:

Julia

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

Pari/GP

<lang parigp>F(n)=i=0;while(i^2-(i-1)^2<n,i=i+1);return(i); print(F(1000))</lang>

Output:

Pencil and Paper

Find the smallest positive integer number n, where the difference of n² and (n - 1)² 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

<lang 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";</lang>

Output:

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

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. <lang pli>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</lang>

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

Python

<lang 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() </lang>

Output:

working...
Least number is = 501
done...

Quackery

<lang Quackery> [ dup * ] is squared ( n --> n )

 0 
 [ 1+
   dup squared 
   over 1 - squared - 
   1000 > until ]
 echo</lang>

Output:

Using algebra

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

Output:

Raku

<lang perl6>say first { $_² - ($_-1)² > 1000 }, ^Inf;</lang>

Output:

Ring

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

Output:

working...
Latest number is = 501
done...

Sidef

<lang ruby>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}"</lang>

Output:

501^2 - 500^2 = 1001

Verilog

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

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. <lang ecmascript>var squareDiff = Fn.new { |k| ((k + 1) * 0.5).ceil } System.print(squareDiff.call(1000))</lang>

Output:

XPL0

n^2 - (n - 1)^2 > 1000
n^2 - (n^2 - 2n + 1) > 1000
2n - 1 > 1000
2n > 1001
n > 500.5
n = 501