Find square difference: Difference between revisions
Find square difference in Tiny BASIC |
m →{{header|Haskell}}: Trivial edit to a trivial problem |
||
Line 329:
-- Or, with redundant verbosity
g n = i
where
main = mapM_ print $ [f, g] <*> [1000]</lang>▼
▲ print $ g 1000</lang>
{{Out}}
<pre>501
|
Revision as of 16:01, 15 June 2022
- 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:
501
Ada
<lang 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;</lang>
- 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. <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:
501
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:
501
AWK
<lang 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:
501
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>
Run BASIC
<lang lb>function fpow(n)
while i^2-(i-1)^2 < 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>
Tiny BASIC
<lang qbasic> 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</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:
501
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:
501
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:
501
F#
<lang fsharp> let n=1000 in printfn $"%d{((n+1)/2)+1}" </lang>
- Output:
501
Factor
The difference between squares is the odd numbers, so ls(n)=⌈n/2+1⌉.
<lang factor>USING: math math.functions prettyprint ;
- least-sq ( m -- n ) 2 / 1 + ceiling ;
1000 least-sq .</lang>
- Output:
501
Fermat
<lang>Func F(n) =
i:=0; while i^2-(i-1)^2<n do i:=i+1 od; i.;
!!F(1000);</lang>
- Output:
501
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:
501
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:
501
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 = i
where Just i = succ <$> findIndex (> n) [1, 3 ..]
main = mapM_ print $ [f, g] <*> [1000]</lang>
- Output:
501 501
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:
501
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:
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
<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:
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
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:
501
Using algebra
Noting that a²-b² ≡ (a+b)(a-b), and that in this instance a = b+1.
<lang Quackery> 1000 2 / 1+ echo</lang>
- Output:
501
Raku
<lang perl6>say first { $_² - ($_-1)² > 1000 }, ^Inf;</lang>
- Output:
501
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
next
see "done..." + nl </lang>
- 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:
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