Smallest square that begins with n: Difference between revisions
Add Refal
m (→{{header|Julia}}: shorten) |
Not a robot (talk | contribs) (Add Refal) |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 1,780:
484 is 22²
49 is 7²
</pre>
=={{header|JavaScript}}==
{{Trans|Julia}}
Procedural, uses console.log to show the numbers.
<syntaxhighlight lang="javascript">
{ // find the smallest square that begins with n for n in 1..49
'use strict'
const smsq = function( n ) {
let results = [], found = 0, square = 1, delta = 3
while( found < n ) {
let k = square
while( k > 0 ) {
if( k <= n && results[ k ] == null ) {
results[ k ] = square
found += 1
}
k = Math.floor( k / 10 )
}
square = square + delta
delta = delta + 2
}
return results
} // smsq
const seq = smsq( 49 )
let out = ""
for( let i = 1; i < seq.length; i ++ ) {
out += seq[ i ].toString().padStart( 6 )
if( i % 10 == 0 ){ out += "\n" }
}
console.log( out )
}
</syntaxhighlight>
{{out}}
<pre>
1 25 36 4 529 64 729 81 9 100
1156 121 1369 144 1521 16 1764 1849 196 2025
2116 225 2304 2401 25 2601 2704 289 2916 3025
3136 324 3364 3481 35344 36 3721 3844 3969 400
41209 4225 4356 441 45369 4624 4761 484 49
</pre>
=={{header|Julia}}==
<syntaxhighlight lang="julia">
function smsq(n = 49)
results = zeros(Int, n)
found, square, delta = 0, 1, 3
Line 1,802 ⟶ 1,845:
foreach(p -> print(rpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""), enumerate(smsq()))
println()
@btime smsq(1_000_000)
</syntaxhighlight>{{out}}
<pre>
1 25 36 4 529 64 729 81 9 100
1156 121 1369 144 1521 16 1764 1849 196 2025
2116 225 2304 2401 25 2601 2704 289 2916 3025
3136 324 3364 3481 35344 36 3721 3844 3969 400
41209 4225 4356 441 45369 4624 4761 484 49
27.356 ms (2 allocations: 7.63 MiB)
</pre>
=={{header|Lua}}==
{{Trans|Julia}}
<syntaxhighlight lang="lua">
do -- find the smallest square that begins with n for n in 1..49
local function smsq( n )
local results, found, square, delta = {}, 0, 1, 3
while found < n do
local k = square
while k > 0 do
if k <= n and results[ k ] == nil then
results[ k ] = square
found = found + 1
end
k = math.floor( k / 10 )
end
square = square + delta
delta = delta + 2
end
return results
end
local seq = smsq( 49 )
for i = 1, #seq do
io.write( " ", string.format( "%5d", seq[ i ] ) )
if i % 10 == 0 then io.write( "\n" ) end
end
end
</syntaxhighlight>
{{out}}
<pre>
1 25 36 4 529 64 729 81 9 100
1156 121 1369 144 1521 16 1764 1849 196 2025
2116 225 2304 2401 25 2601 2704 289 2916 3025
3136 324 3364 3481 35344 36 3721 3844 3969 400
41209 4225 4356 441 45369 4624 4761 484 49
</pre>
Line 1,949 ⟶ 2,032:
484
49</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE SmallestSquareWithPrefix;
FROM InOut IMPORT WriteCard, WriteLn;
VAR n: CARDINAL;
PROCEDURE prefix(n, m: CARDINAL): BOOLEAN;
BEGIN
IF n>=m
THEN RETURN n=m
ELSE RETURN prefix(n, m DIV 10)
END
END prefix;
PROCEDURE firstPrefixSquare(n: CARDINAL): CARDINAL;
VAR
sq, sqr: CARDINAL;
BEGIN
sqr := 0;
REPEAT
INC(sqr);
sq := sqr*sqr
UNTIL prefix(n, sq);
RETURN sq
END firstPrefixSquare;
BEGIN
FOR n := 0 TO 49 DO
WriteCard(firstPrefixSquare(n), 7);
IF n MOD 10 = 9 THEN WriteLn END
END
END SmallestSquareWithPrefix.</syntaxhighlight>
{{out}}
<pre> 1 1 25 36 4 529 64 729 81 9
100 1156 121 1369 144 1521 16 1764 1849 196
2025 2116 225 2304 2401 25 2601 2704 289 2916
3025 3136 324 3364 3481 35344 36 3721 3844 3969
400 41209 4225 4356 441 45369 4624 4761 484 49</pre>
=={{header|Nim}}==
Line 2,125 ⟶ 2,247:
check 1..1E7 in 328 ms
TIO.RUN-> check 1..1E7 in 2540 ms ( old compiler version 3.0.4/3.2.3 and 2.3 vs 4.4 Ghz )
</pre>
===={{trans|Julia}}====
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.<br>
Improved version ->335 ms<br>
Stop searching as early as possible->minimize count of divisions (~ n*(1+3.162=sqrt(10)) ) -> 71 ms<br>
increment as long the testsqr didn't change in last digit. Divisions (~ n*(1+1.8662 )) -> 53 ms :-)
<syntaxhighlight lang="pascal">
program smsq;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
uses
sysutils;
type
tRes = array of Uint32;
var
maxTestVal : Uint32;
function smsq(n:Uint32):tRes;
// limit n is ~ 1.358E9
var
square,nxtSqr,Pow10 : Uint64;
n_run,testSqr,found : Uint32;
begin
setlength(result,n+1);
fillchar(result[0],length(result)*Sizeof(result[0]),#0);
found := 0;
square := 0;
n_run := 0;
Pow10 := 1;
nxtSqr := 1;//sqr(n_run)+1;
while found < n do
begin
repeat
n_run +=1;
square := sqr(n_run);
until square >= nxtSqr;
//bring square into the right place
testSqr := square div pow10;
while testSqr > n do
Begin
pow10 *=10;
testSqr := testSqr div 10;
end;
//next square must increase by one digit
nxtSqr := (testSqr+1)*pow10;
repeat
//no need to test any more
//if found ex. 4567 than 456,45 and 4 already marsquareed
if result[testSqr] <> 0 then
BREAK;
result[testSqr] := n_run;
found += 1;
testSqr := testSqr div 10;
until testSqr = 0;
end;
maxTestVal := n_run;
end;
var
t0 : Int64;
n,i : Uint32;
results : tRes;
BEGIN
n := 49;
results := smsq(n);
For i := 1 to n do
begin
write(sqr(results[i]):6);
if i mod 10 = 0 then
Writeln;
end;
writeln;
writeln('Max test value : ',maxTestVal); ;
writeln;
n := 10*1000*1000;
// speed up cpu
smsq(n);
t0 := GetTickCount64;
smsq(n);
t0 := GetTickCount64-t0;
writeln('check 1..',n,' in ', T0,' ms. Max test value : ',maxTestVal);
END.
</syntaxhighlight>
{{out|@home}}
<pre>
1 25 36 4 529 64 729 81 9 100
1156 121 1369 144 1521 16 1764 1849 196 2025
2116 225 2304 2401 25 2601 2704 289 2916 3025
3136 324 3364 3481 35344 36 3721 3844 3969 400
41209 4225 4356 441 45369 4624 4761 484 49
Max test value : 213
check 1..10000000 in 53 ms. Max test value : 31622776
....
check 1..1000000000 in 5174 ms. Max test value : 3162277656
</pre>
Line 2,179 ⟶ 2,396:
<syntaxhighlight lang="phix">
with javascript_semantics
constant lim =
sequence res = repeat(0,lim)
integer n = 1, found = 0
Line 2,700 ⟶ 2,917:
Same output.
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Table (7 7) <Each FirstPrefixSquare <Iota 1 49>>>;
};
Cell {
s.W s.N, <Repeat s.W ' '> <Symb s.N>: e.C,
<Last s.W e.C>: (e.X) e.CI = e.CI;
}
Repeat {
0 s.C = ;
s.N s.C = s.C <Repeat <- s.N 1> s.C>;
};
Table {
(s.Cols s.CW) e.X = <Table () (s.Cols s.Cols s.CW) e.X>;
(e.Row) (s.Cols s.N s.CW), e.Row: {
= ;
e.Row = <Prout e.Row>;
};
(e.Row) (s.Cols 0 s.CW) e.X =
<Prout e.Row>
<Table () (s.Cols s.Cols s.CW) e.X>;
(e.Row) (s.Cols s.N s.CW) s.I e.X =
<Table (e.Row <Cell s.CW s.I>) (s.Cols <- s.N 1> s.CW) e.X>;
};
Each {
s.F = ;
s.F s.I e.X = <Mu s.F s.I> <Each s.F e.X>;
};
Iota {
s.End s.End = s.End;
s.Start s.End = s.Start <Iota <+ 1 s.Start> s.End>;
};
FirstPrefixSquare {
s.N = <FirstPrefixSquare s.N 1>;
s.N s.Sqr, <* s.Sqr s.Sqr>: s.Sq,
<Symb s.N>: e.Pfx,
<Symb s.Sq>: e.Pfx e.X = s.Sq;
s.N s.Sqr = <FirstPrefixSquare s.N <+ 1 s.Sqr>>;
};
</syntaxhighlight>
{{out}}
<pre> 1 25 36 4 529 64 729
81 9 100 1156 121 1369 144
1521 16 1764 1849 196 2025 2116
225 2304 2401 25 2601 2704 289
2916 3025 3136 324 3364 3481 35344
36 3721 3844 3969 400 41209 4225
4356 441 45369 4624 4761 484 49</pre>
=={{header|REXX}}==
Line 3,058 ⟶ 3,330:
(return-from search)))
((set k (trunc k 10)))))))</syntaxhighlight>
=={{header|Uiua}}==
{{works with|Uiua|0.10}}
In best YAGNI style, just calculate sufficient squares for the task as specced (up to 220^2)
<syntaxhighlight lang="Uiua">
IsPrefix ← =⧻⟜(/+⬚@.=)
⊞◇IsPrefix °⋕↘1⇡50 °⋕.ⁿ2+1⇡220
⊏≡(⊢⊚)
</syntaxhighlight>
{{out}}
<pre>
[1 25 36 4 529 64 729 81 9 100 1156 ...etc...]
</pre>
=={{header|VTL-2}}==
| |||