Rosetta Code

Find square difference


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.

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



11lEdit

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

AdaEdit

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

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 WEdit

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

ArturoEdit

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

AsymptoteEdit

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

write(fpow(1000));

AutoHotkeyEdit

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

AWKEdit

# 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

BASICEdit

BASIC256Edit

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

print fpow(1001)
end

PureBasicEdit

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

QBasicEdit

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

PRINT fpow(1001)

Run BASICEdit

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

True BASICEdit

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 BASICEdit

    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

YabasicEdit

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

print fpow(1001)
end


bcEdit

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

CEdit

#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++Edit

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

DartEdit

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

dcEdit

1000 1+2/1+p
Output:
501

EasyLangEdit

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

F#Edit

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

FactorEdit

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

FermatEdit

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

!!F(1000);
Output:
501

ForthEdit

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


FreeBASICEdit

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

GoEdit

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

HaskellEdit

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

JEdit

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

JoyEdit

1000 succ 2 / succ.
Output:
501

jqEdit

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

JuliaEdit

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

OCamlEdit

let calculate x =
  succ (succ x lsr 1)

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

Pari/GPEdit

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

Pencil and PaperEdit

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)

PerlEdit

#!/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

PhixEdit

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

PhixmontiEdit

/# 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/MEdit

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 EnglishEdit

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.

PythonEdit

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

QuackeryEdit

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

Using algebraEdit

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

  1000 2 / 1+ echo
Output:
501

RakuEdit

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

RingEdit

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

RPLEdit

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

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

which returns the same result in only 9.2 seconds.

RubyEdit

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

SidefEdit

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

VerilogEdit

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

WrenEdit

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

XPL0Edit

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"