# Find square difference

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.

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

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

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 */
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 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 );
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

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