Smallest square that begins with n
Smallest square that begins with n 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
Find the smallest (decimal integer) squares that begin with n for 0 < n < 50
11l
F firstSquareWithPrefix(n)
V pfx = String(n)
L(x) 0..
V s = String(x * x)
I s.starts_with(pfx)
R Int(s)
L(n) 0 <.< 50
print(firstSquareWithPrefix(n))- Output:
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
ABC
HOW TO REPORT n begins.with m:
SELECT:
n<m: FAIL
n=m: SUCCEED
n>m: REPORT (floor (n/10)) begins.with m
HOW TO RETURN first.square.with.prefix n:
PUT 1 IN sq.root
WHILE NOT (sq.root**2) begins.with n:
PUT sq.root+1 IN sq.root
RETURN sq.root**2
FOR i IN {0..49}:
WRITE (first.square.with.prefix i)>>7
IF i mod 10 = 9: WRITE /- Output:
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
Action!
CARD FUNC GetNumber(BYTE x)
CARD i,sq
i=1
DO
sq=i*i
WHILE sq>x
DO
sq==/10
OD
IF sq=x THEN
RETURN (i*i)
FI
i==+1
OD
RETURN (0)
PROC Main()
BYTE i
CARD num
FOR i=1 TO 49
DO
num=GetNumber(i)
PrintC(num) Put(32)
OD
RETURN- Output:
Screenshot from Atari 8-bit computer
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 3585 36 3721 3844 3969 400 4160 4225 4356 441 4529 4624 4761 484 49
ALGOL 68
BEGIN # find the smallest square that begins with n for n in 1..49 #
INT max number = 49;
[ max number ]INT square; FOR i TO max number DO square[ i ] := 0 OD;
INT number found := 0;
FOR i WHILE number found < max number DO
INT sq = i * i;
INT v := sq;
WHILE v > 0 DO
IF v <= max number THEN
IF square[ v ] = 0 THEN
# found the first square that starts with v #
square[ v ] := sq;
number found +:= 1
FI
FI;
v OVERAB 10
OD
OD;
# show the squares #
FOR i TO max number DO
print( ( " ", whole( square[ i ], -6 ) ) );
IF i MOD 10 = 0 THEN print( ( newline ) ) FI
OD
END- Output:
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
ALGOL W
begin % print the lowest square that starts with 1..49 %
integer MAX_NUMBER;
MAX_NUMBER := 49;
begin
integer array lowest( 1 :: MAX_NUMBER );
integer numberFound, n;
numberFound := 0;
for i := 1 until MAX_NUMBER do lowest( i ) := 0;
n := 0;
while numberFound < MAX_NUMBER do begin
integer v, n2;
n := n + 1;
v := n2 := n * n;
while v > 0 do begin
if v <= MAX_NUMBER and lowest( v ) = 0 then begin
% found a square that starts with a number in the range %
lowest( v ) := n2;
numberFound := numberFOund + 1
end if_v_le_MAX_NUMBER_and_lowest_v_eq_0 ;
v := v div 10
end while_v_gt_0
end while_numberFound_lt_MAX_NUMBER ;
% show the squares %
for i := 1 until MAX_NUMBER do begin
writeon( i_w := 6, s_w := 0, " ", lowest( i ) );
if i rem 10 = 0 then write()
end for_i
end
end.- Output:
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
APL
5 10⍴'∘',0 {1=⊃(⍕⍵)⍷⍕⍺×⍺:⍺×⍺ ⋄ (⍺+1)∇⍵}¨ ⍳49
- Output:
∘ 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
Arturo
loop 1..49 'n [
ns: to :string n
print [pad to :string n 2 "->" (first select.first 0..∞ 'x -> prefix? to :string x^2 ns)^2]
]
- Output:
1 -> 1 2 -> 25 3 -> 36 4 -> 4 5 -> 529 6 -> 64 7 -> 729 8 -> 81 9 -> 9 10 -> 100 11 -> 1156 12 -> 121 13 -> 1369 14 -> 144 15 -> 1521 16 -> 16 17 -> 1764 18 -> 1849 19 -> 196 20 -> 2025 21 -> 2116 22 -> 225 23 -> 2304 24 -> 2401 25 -> 25 26 -> 2601 27 -> 2704 28 -> 289 29 -> 2916 30 -> 3025 31 -> 3136 32 -> 324 33 -> 3364 34 -> 3481 35 -> 35344 36 -> 36 37 -> 3721 38 -> 3844 39 -> 3969 40 -> 400 41 -> 41209 42 -> 4225 43 -> 4356 44 -> 441 45 -> 45369 46 -> 4624 47 -> 4761 48 -> 484 49 -> 49
AutoHotkey
loop 49
result .= SS(A_Index) (Mod(A_Index,7)?"`t":"`n")
MsgBox % result
return
SS(n) {
if (n < 1)
return
loop{
sq := a_index**2
while (sq > n)
sq := Format("{:d}", sq/10)
if (sq = n)
return a_index**2
}
}
- Output:
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
AWK
# syntax: GAWK -f SMALLEST_SQUARE_THAT_BEGINS_WITH_N.AWK
# converted from C
BEGIN {
print("Prefix n^2 n")
for (i=1; i<50; i++) {
x(i)
}
exit(0)
}
function x(n, i,sq) {
i = 1
while (1) {
sq = i * i
while (sq > n) {
sq = int(sq/10)
}
if (sq == n) {
printf("%3d %7d %4d\n",n,i*i,i)
return
}
i++
}
}
- Output:
Prefix n^2 n 1 1 1 2 25 5 3 36 6 4 4 2 5 529 23 6 64 8 7 729 27 8 81 9 9 9 3 10 100 10 11 1156 34 12 121 11 13 1369 37 14 144 12 15 1521 39 16 16 4 17 1764 42 18 1849 43 19 196 14 20 2025 45 21 2116 46 22 225 15 23 2304 48 24 2401 49 25 25 5 26 2601 51 27 2704 52 28 289 17 29 2916 54 30 3025 55 31 3136 56 32 324 18 33 3364 58 34 3481 59 35 35344 188 36 36 6 37 3721 61 38 3844 62 39 3969 63 40 400 20 41 41209 203 42 4225 65 43 4356 66 44 441 21 45 45369 213 46 4624 68 47 4761 69 48 484 22 49 49 7
BASIC
10 FOR I=1 TO 49
20 J=1
30 K=J*J
40 IF K>I THEN K=FIX(K/10): GOTO 40
50 IF K=I THEN PRINT J*J,: GOTO 80
60 J=J+1
70 GOTO 30
80 NEXT I
- Output:
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
BASIC256
print "Prefix n^2 n"
print "-----------------------------"
for i = 1 to 49
j = 1
while true
k = j ^ 2
while k > i
k = int(k / 10)
end while
if k = i then
print i, j*j, int(sqr(j^2))
exit while
end if
j += 1
end while
next i
- Output:
Igual que la entrada de FreeBASIC.
True BASIC
PRINT "Prefix n^2 n"
PRINT "------------------------------------"
FOR i = 1 to 49
LET N = 1
DO
LET j = N ^ 2
DO WHILE j > i
LET j = int(j / 10)
LOOP
IF j = i then
PRINT i, N^2, sqr(N^2)
EXIT DO
END IF
LET N = N + 1
LOOP
NEXT i
END
- Output:
Igual que la entrada de FreeBASIC.
bc
for (q = a = 1; c != 49; q += a += 2) {
for (k = q; k != 0; k /= 10) if (k < 50) {
if (m[k] != 0) break
m[k] = q
c += 1
}
}
for (k = 1; k != 50; ++k) m[k]
BQN
Bgn← (⊣≡≠∘⊣↑⊢)○•Fmt
Ssq← ט ⊢{𝕨((Bgn⟜(ט ))◶(⊣𝕊1˙+⊢)‿⊢)𝕩}1˙
10‿5⥊@∾Ssq¨1↓↕50
- Output:
┌─
╵ @ 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
┘
C
#include <stdio.h>
void f(int n) {
int i = 1;
if (n < 1) {
return;
}
while (1) {
int sq = i * i;
while (sq > n) {
sq /= 10;
}
if (sq == n) {
printf("%3d %9d %4d\n", n, i * i, i);
return;
}
i++;
}
}
int main() {
int i;
printf("Prefix n^2 n\n");
printf("");
for (i = 1; i < 50; i++) {
f(i);
}
return 0;
}
- Output:
Prefix n^2 n 1 1 1 2 25 5 3 36 6 4 4 2 5 529 23 6 64 8 7 729 27 8 81 9 9 9 3 10 100 10 11 1156 34 12 121 11 13 1369 37 14 144 12 15 1521 39 16 16 4 17 1764 42 18 1849 43 19 196 14 20 2025 45 21 2116 46 22 225 15 23 2304 48 24 2401 49 25 25 5 26 2601 51 27 2704 52 28 289 17 29 2916 54 30 3025 55 31 3136 56 32 324 18 33 3364 58 34 3481 59 35 35344 188 36 36 6 37 3721 61 38 3844 62 39 3969 63 40 400 20 41 41209 203 42 4225 65 43 4356 66 44 441 21 45 45369 213 46 4624 68 47 4761 69 48 484 22 49 49 7
C#
using System;
class Program
{
static void Main(string[] args)
{
int i, d, s, t, n = 50, c = 1;
var sw = new int[n];
for (i = d = s = 1; c < n; i++, s += d += 2)
for (t = s; t > 0; t /= 10)
if (t < n && sw[t] < 1)
Console.Write("", sw[t] = s, c++);
Console.Write(string.Join(" ", sw).Substring(2));
}
}
- Output:
Same as F#
C++
#include <iostream>
void f(int n) {
if (n < 1) {
return;
}
int i = 1;
while (true) {
int sq = i * i;
while (sq > n) {
sq /= 10;
}
if (sq == n) {
printf("%3d %9d %4d\n", n, i * i, i);
return;
}
i++;
}
}
int main() {
std::cout << "Prefix n^2 n\n";
for (int i = 0; i < 50; i++) {
f(i);
}
return 0;
}
- Output:
Prefix n^2 n 1 1 1 2 25 5 3 36 6 4 4 2 5 529 23 6 64 8 7 729 27 8 81 9 9 9 3 10 100 10 11 1156 34 12 121 11 13 1369 37 14 144 12 15 1521 39 16 16 4 17 1764 42 18 1849 43 19 196 14 20 2025 45 21 2116 46 22 225 15 23 2304 48 24 2401 49 25 25 5 26 2601 51 27 2704 52 28 289 17 29 2916 54 30 3025 55 31 3136 56 32 324 18 33 3364 58 34 3481 59 35 35344 188 36 36 6 37 3721 61 38 3844 62 39 3969 63 40 400 20 41 41209 203 42 4225 65 43 4356 66 44 441 21 45 45369 213 46 4624 68 47 4761 69 48 484 22 49 49 7
CLU
begins_with = proc (n, s: int) returns (bool)
while n>s do n := n/10 end
return(n=s)
end begins_with
smallest_square = proc (n: int) returns (int)
sq: int := 1
while ~begins_with(sq**2, n) do sq := sq + 1 end
return(sq**2)
end smallest_square
start_up = proc ()
po: stream := stream$primary_output()
col: int := 0
for i: int in int$from_to(1,49) do
stream$putright(po, int$unparse(smallest_square(i)), 7)
col := col + 1
if col=10 then
col := 0
stream$putl(po, "")
end
end
stream$putl(po, "")
end start_up- Output:
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
COBOL
IDENTIFICATION DIVISION.
PROGRAM-ID. SMALLEST-SQUARE-BEGINS-WITH-N.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 N PIC 99.
01 SQUARE-NO PIC 999.
01 SQUARE PIC 9(5).
01 OUT-FMT PIC Z(4)9.
PROCEDURE DIVISION.
BEGIN.
PERFORM SMALLEST-SQUARE THRU SQUARE-START-TEST
VARYING N FROM 1 BY 1 UNTIL N IS EQUAL TO 50.
STOP RUN.
SMALLEST-SQUARE.
MOVE ZERO TO SQUARE-NO.
SQUARE-LOOP.
ADD 1 TO SQUARE-NO.
MULTIPLY SQUARE-NO BY SQUARE-NO GIVING SQUARE.
SQUARE-START-TEST.
IF SQUARE IS GREATER THAN N
DIVIDE 10 INTO SQUARE
GO TO SQUARE-START-TEST.
IF SQUARE IS NOT EQUAL TO N
GO TO SQUARE-LOOP.
MULTIPLY SQUARE-NO BY SQUARE-NO GIVING OUT-FMT.
DISPLAY OUT-FMT.
- Output:
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
Comal
0010 FUNC begins'with(n,s)
0020 WHILE n>s DO n:=n DIV 10
0030 RETURN n=s
0040 ENDFUNC begins'with
0050 //
0060 FUNC smallest'square(a)
0070 sq:=1
0080 WHILE NOT begins'with(sq^2,a) DO sq:+1
0090 RETURN sq^2
0100 ENDFUNC smallest'square
0110 //
0120 ZONE 7
0130 FOR i:=1 TO 49 DO
0140 PRINT smallest'square(i),
0150 IF i MOD 10=0 THEN PRINT
0160 ENDFOR i
0170 PRINT
0180 END
- Output:
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
Cowgol
include "cowgol.coh";
sub beginsWith(a: uint16, b: uint16): (r: uint8) is
while a > b loop
a := a / 10;
end loop;
if a == b then r := 1;
else r := 0;
end if;
end sub;
sub smallestSquare(n: uint16): (sq: uint16) is
var sqn: uint16 := 1;
loop
sq := sqn * sqn;
if beginsWith(sq, n) != 0 then
return;
end if;
sqn := sqn + 1;
end loop;
end sub;
var n: uint16 := 1;
while n < 50 loop
print_i16(smallestSquare(n));
print_nl();
n := n + 1;
end loop;- Output:
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
D
Iterative versions
import std.stdio;
void f(int n) {
if (n < 1) {
return;
}
int i = 1;
while (true) {
int sq = i * i;
while (sq > n) {
sq /= 10;
}
if (sq == n) {
"%3d %9d %4d".writefln(n, i * i, i);
return;
}
i++;
}
}
void main()
{
"Prefix n^2 n".writeln;
foreach(i ; iota(1, 50))
{
f(i);
}
}
- Output:
Prefix n^2 n 1 1 1 2 25 5 3 36 6 4 4 2 5 529 23 6 64 8 7 729 27 8 81 9 9 9 3 10 100 10 11 1156 34 12 121 11 13 1369 37 14 144 12 15 1521 39 16 16 4 17 1764 42 18 1849 43 19 196 14 20 2025 45 21 2116 46 22 225 15 23 2304 48 24 2401 49 25 25 5 26 2601 51 27 2704 52 28 289 17 29 2916 54 30 3025 55 31 3136 56 32 324 18 33 3364 58 34 3481 59 35 35344 188 36 36 6 37 3721 61 38 3844 62 39 3969 63 40 400 20 41 41209 203 42 4225 65 43 4356 66 44 441 21 45 45369 213 46 4624 68 47 4761 69 48 484 22 49 49 7
import std.stdio, std.range, std.conv, std.string;
// Choose an arbitrary large integer value to make sure brute forcing effective
// FYI 45_369+1 suffices for 0 < n < 50 and anything beyond will do. The output below tells...
const int upperBound = 1_000_000;
bool isTheBeginningOf(int a, int b) {
return indexOf(to!string(b^^2), to!string(a)) == 0;
}
void main()
{
foreach(i; iota(1, 50)) {
foreach(j; iota(upperBound)) {
if (isTheBeginningOf(i,j)) {
writefln("%4d: %4d^2 = %5d", i, j, j^^2 );
break;
}
}
}
}
- Output:
1: 1^2 = 1 2: 5^2 = 25 3: 6^2 = 36 4: 2^2 = 4 5: 23^2 = 529 6: 8^2 = 64 7: 27^2 = 729 8: 9^2 = 81 9: 3^2 = 9 10: 10^2 = 100 11: 34^2 = 1156 12: 11^2 = 121 13: 37^2 = 1369 14: 12^2 = 144 15: 39^2 = 1521 16: 4^2 = 16 17: 42^2 = 1764 18: 43^2 = 1849 19: 14^2 = 196 20: 45^2 = 2025 21: 46^2 = 2116 22: 15^2 = 225 23: 48^2 = 2304 24: 49^2 = 2401 25: 5^2 = 25 26: 51^2 = 2601 27: 52^2 = 2704 28: 17^2 = 289 29: 54^2 = 2916 30: 55^2 = 3025 31: 56^2 = 3136 32: 18^2 = 324 33: 58^2 = 3364 34: 59^2 = 3481 35: 188^2 = 35344 36: 6^2 = 36 37: 61^2 = 3721 38: 62^2 = 3844 39: 63^2 = 3969 40: 20^2 = 400 41: 203^2 = 41209 42: 65^2 = 4225 43: 66^2 = 4356 44: 21^2 = 441 45: 213^2 = 45369 46: 68^2 = 4624 47: 69^2 = 4761 48: 22^2 = 484 49: 7^2 = 49
Delphi
function LowSquareStartN(N: byte): integer;
{Find lowest square that matches N}
var S: string;
var T,J,DR,DN,DX: integer;
begin
{Get number of digits in N}
DN:=NumberOfDigits(N);
for Result:=1 to High(Integer) do
begin
T:=Result*Result;
{Divide off digits so no bigger than N}
DR:=NumberOfDigits(T);
DX:=DR-DN;
for J:=1 to DX do T:=T div 10;
{Does it match}
if T=N then break;
end;
end;
procedure SquareStartsN(Memo: TMemo);
{Find smallest square that begins with N}
var I,T: integer;
begin
for I:=1 to 50-1 do
begin
T:=LowSquareStartN(I);
Memo.Lines.Add(IntToStr(I)+' '+IntToStr(T*T));
end;
end;
- Output:
1 1 2 25 3 36 4 4 5 529 6 64 7 729 8 81 9 9 10 100 11 1156 12 121 13 1369 14 144 15 1521 16 16 17 1764 18 1849 19 196 20 2025 21 2116 22 225 23 2304 24 2401 25 25 26 2601 27 2704 28 289 29 2916 30 3025 31 3136 32 324 33 3364 34 3481 35 35344 36 36 37 3721 38 3844 39 3969 40 400 41 41209 42 4225 43 4356 44 441 45 45369 46 4624 47 4761 48 484 49 49 Elapsed Time: 105.599 ms.
Draco
proc nonrec prefix(word a, b) bool:
while a > b do a := a/10 od;
a = b
corp
proc nonrec findPrefixSquare(word n) word:
word sq, sqn;
sqn := 1;
while
sq := sqn * sqn;
not prefix(sq, n)
do
sqn := sqn + 1
od;
sq
corp
proc nonrec main() void:
word i, col;
col := 0;
for i from 1 upto 49 do
write(findPrefixSquare(i):7);
col := col + 1;
if col = 10 then
col := 0;
writeln()
fi
od
corp- Output:
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
EasyLang
func f n .
n$ = n
repeat
xx = x * x
until substr xx 1 len n$ = n$
x += 1
.
return xx
.
for i = 1 to 49
write f i & " "
.
- Output:
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
Excel
LAMBDA
Binding the name firstSquareWithPrefix to the following lambda expression in the Name Manager of the Excel WorkBook:
(See LAMBDA: The ultimate Excel worksheet function)
firstSquareWithPrefix
=LAMBDA(n,
LET(
pfx, TEXT(n, "0"),
lng, LEN(pfx),
UNTIL(
LAMBDA(i,
pfx = MID(TEXT(i ^ 2, "0"), 1, lng)
)
)(
LAMBDA(i, 1 + i)
)(0) ^ 2
)
)
and also assuming the following generic binding in the Name Manager for the WorkBook:
UNTIL
=LAMBDA(p,
LAMBDA(f,
LAMBDA(x,
IF(p(x),
x,
UNTIL(p)(f)(f(x))
)
)
)
)
- Output:
| fx | =firstSquareWithPrefix(A2) | ||||
|---|---|---|---|---|---|
| A | B | C | D | ||
| 1 | Prefix | Square | Prefix | Square | |
| 2 | 1 | 1 | 26 | 2601 | |
| 3 | 2 | 25 | 27 | 2704 | |
| 4 | 3 | 36 | 28 | 289 | |
| 5 | 4 | 4 | 29 | 2916 | |
| 6 | 5 | 529 | 30 | 3025 | |
| 7 | 6 | 64 | 31 | 3136 | |
| 8 | 7 | 729 | 32 | 324 | |
| 9 | 8 | 81 | 33 | 3364 | |
| 10 | 9 | 9 | 34 | 3481 | |
| 11 | 10 | 100 | 35 | 35344 | |
| 12 | 11 | 1156 | 36 | 36 | |
| 13 | 12 | 121 | 37 | 3721 | |
| 14 | 13 | 1369 | 38 | 3844 | |
| 15 | 14 | 144 | 39 | 3969 | |
| 16 | 15 | 1521 | 40 | 400 | |
| 17 | 16 | 16 | 41 | 41209 | |
| 18 | 17 | 1764 | 42 | 4225 | |
| 19 | 18 | 1849 | 43 | 4356 | |
| 20 | 19 | 196 | 44 | 441 | |
| 21 | 20 | 2025 | 45 | 45369 | |
| 22 | 21 | 2116 | 46 | 4624 | |
| 23 | 22 | 225 | 47 | 4761 | |
| 24 | 23 | 2304 | 48 | 484 | |
| 25 | 24 | 2401 | 49 | 49 | |
| 26 | 25 | 25 | 50 | 5041 | |
F#
// Generate emirps. Nigel Galloway: March 25th., 2021
let N=seq{1..0x0FFFFFFF}|>Seq.map(fun n->((*)n>>string)n)|>Seq.cache
let G=let fG n g=n|>Seq.map(fun n->N|>Seq.find(fun i->i.[0..g]=string n)) in seq{yield! fG(seq{1..9}) 0; yield! fG(seq{10..49}) 1}
G|>Seq.iter(printf "%s "); printfn ""
- Output:
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
Factor
USING: arrays combinators.short-circuit.smart formatting io
kernel math sequences ;
[let
50 :> lim
lim 0 <array> :> res
1 0 :> ( n! found! )
[ found lim 1 - < ] [
n dup * :> n2!
[ n2 zero? ] [
{ [ n2 lim < ] [ n2 res nth zero? ] } &&
[ found 1 + found! n n2 res set-nth ] when
n2 10 /i n2!
] until
n 1 + n!
] while
res rest
]
"Smallest square that begins with..." print
[ 1 + swap [ sq ] keep "%2d: %5d (%3d^2)\n" printf ]
each-index
- Output:
Smallest square that begins with... 1: 1 ( 1^2) 2: 25 ( 5^2) 3: 36 ( 6^2) 4: 4 ( 2^2) 5: 529 ( 23^2) 6: 64 ( 8^2) 7: 729 ( 27^2) 8: 81 ( 9^2) 9: 9 ( 3^2) 10: 100 ( 10^2) 11: 1156 ( 34^2) 12: 121 ( 11^2) 13: 1369 ( 37^2) 14: 144 ( 12^2) 15: 1521 ( 39^2) 16: 16 ( 4^2) 17: 1764 ( 42^2) 18: 1849 ( 43^2) 19: 196 ( 14^2) 20: 2025 ( 45^2) 21: 2116 ( 46^2) 22: 225 ( 15^2) 23: 2304 ( 48^2) 24: 2401 ( 49^2) 25: 25 ( 5^2) 26: 2601 ( 51^2) 27: 2704 ( 52^2) 28: 289 ( 17^2) 29: 2916 ( 54^2) 30: 3025 ( 55^2) 31: 3136 ( 56^2) 32: 324 ( 18^2) 33: 3364 ( 58^2) 34: 3481 ( 59^2) 35: 35344 (188^2) 36: 36 ( 6^2) 37: 3721 ( 61^2) 38: 3844 ( 62^2) 39: 3969 ( 63^2) 40: 400 ( 20^2) 41: 41209 (203^2) 42: 4225 ( 65^2) 43: 4356 ( 66^2) 44: 441 ( 21^2) 45: 45369 (213^2) 46: 4624 ( 68^2) 47: 4761 ( 69^2) 48: 484 ( 22^2) 49: 49 ( 7^2)
FOCAL
01.10 F I=1,49;D 2
01.20 Q
02.10 S N=1
02.20 S S=N*N
02.30 S A=S
02.40 I (A-I)2.7,2.9,2.5
02.50 S A=FITR(A/10)
02.60 G 2.4
02.70 S N=N+1
02.80 G 2.2
02.90 T %5,S,!- Output:
= 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
FreeBASIC
dim as uinteger ssq(1 to 49), count = 0, curr = 1, curr2
dim as string scurr2
while count < 49
curr2 = curr^2
scurr2 = str(curr2)
for j as uinteger = 1 to 49
if val(left(scurr2, len(str(j)))) = j and ssq(j) = 0 then
ssq(j) = curr2
count += 1
end if
next j
curr += 1
wend
print "Prefix n^2 n"
print "------------------------------"
for j as uinteger = 1 to 49
print j, ssq(j), sqr(ssq(j))
next j
- Output:
Prefix n^2 n------------------------------ 1 1 1 2 25 5 3 36 6 4 4 2 5 529 23 6 64 8 7 729 27 8 81 9 9 9 3 10 100 10 11 1156 34 12 121 11 13 1369 37 14 144 12 15 1521 39 16 16 4 17 1764 42 18 1849 43 19 196 14 20 2025 45 21 2116 46 22 225 15 23 2304 48 24 2401 49 25 25 5 26 2601 51 27 2704 52 28 289 17 29 2916 54 30 3025 55 31 3136 56 32 324 18 33 3364 58 34 3481 59 35 35344 188 36 36 6 37 3721 61 38 3844 62 39 3969 63 40 400 20 41 41209 203 42 4225 65 43 4356 66 44 441 21 45 45369 213 46 4624 68 47 4761 69 48 484 22 49 49 7
Go
package main
import (
"fmt"
"math"
)
func isSquare(n int) bool {
s := int(math.Sqrt(float64(n)))
return s*s == n
}
func main() {
var squares []int
outer:
for i := 1; i < 50; i++ {
if isSquare(i) {
squares = append(squares, i)
} else {
n := i
limit := 10
for {
n *= 10
for j := 0; j < limit; j++ {
s := n + j
if isSquare(s) {
squares = append(squares, s)
continue outer
}
}
limit *= 10
}
}
}
fmt.Println("Smallest squares that begin with 'n' in [1, 49]:")
for i, s := range squares {
fmt.Printf("%5d ", s)
if ((i + 1) % 10) == 0 {
fmt.Println()
}
}
if (len(squares) % 10) != 0 {
fmt.Println()
}
}
- Output:
Smallest squares that begin with 'n' in [1, 49]:
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
Haskell
import Control.Monad (join)
import Data.List (find, intercalate, isPrefixOf, transpose)
import Data.List.Split (chunksOf)
import Text.Printf (printf)
---------- FIRST SQUARE PREFIXED WITH DIGITS OF N --------
firstSquareWithPrefix :: Int -> Int
firstSquareWithPrefix n = unDigits match
where
ds = digits n
Just match = find (isPrefixOf ds) squareDigits
squareDigits :: [[Int]]
squareDigits = digits . join (*) <$> [0 ..]
--------------------------- TEST -------------------------
main :: IO ()
main =
putStrLn $
table " " $
chunksOf 10 $
show . firstSquareWithPrefix <$> [1 .. 49]
------------------------- GENERIC ------------------------
digits :: Int -> [Int]
digits = fmap (read . return) . show
unDigits :: [Int] -> Int
unDigits = foldl ((+) . (10 *)) 0
table :: String -> [[String]] -> String
table gap rows =
let ws = maximum . fmap length <$> transpose rows
pw = printf . flip intercalate ["%", "s"] . show
in unlines $ intercalate gap . zipWith pw ws <$> rows
- Output:
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
J
*:{.@I. (}.@i. {.@E.&":&>/ *:@i.@*:) 50
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
jq
Works with gojq, the Go implementation of jq
def smallest_square_beginning_with_n:
tostring as $n
| first (range(0; infinite)
| .*.
| select(tostring | startswith($n) )) ;
range(1; 50)
| . as $i
| smallest_square_beginning_with_n
| "\(.) is \(sqrt)²"- Output:
1 is 1² 25 is 5² 36 is 6² 4 is 2² 529 is 23² 64 is 8² 729 is 27² 81 is 9² 9 is 3² 100 is 10² 1156 is 34² 121 is 11² 1369 is 37² 144 is 12² 1521 is 39² 16 is 4² 1764 is 42² 1849 is 43² 196 is 14² 2025 is 45² 2116 is 46² 225 is 15² 2304 is 48² 2401 is 49² 25 is 5² 2601 is 51² 2704 is 52² 289 is 17² 2916 is 54² 3025 is 55² 3136 is 56² 324 is 18² 3364 is 58² 3481 is 59² 35344 is 188² 36 is 6² 3721 is 61² 3844 is 62² 3969 is 63² 400 is 20² 41209 is 203² 4225 is 65² 4356 is 66² 441 is 21² 45369 is 213² 4624 is 68² 4761 is 69² 484 is 22² 49 is 7²
JavaScript
Procedural, uses console.log to show the numbers.
{ // 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 )
}
- Output:
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
Julia
using BenchmarkTools
function smsq(n = 49)
results = zeros(Int, n)
found, square, delta = 0, 1, 3
while found < n
k = square
while k > 0
if k <= n && results[k] == 0
results[k] = square
found += 1
end
k ÷= 10
end
square += delta
delta += 2
end
return results
end
foreach(p -> print(rpad(p[2], 6), p[1] % 10 == 0 ? "\n" : ""), enumerate(smsq()))
println()
@btime smsq(1_000_000)
- Output:
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)
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
- Output:
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
MAD
NORMAL MODE IS INTEGER
VECTOR VALUES FMT = $I2,3H : ,I6*$
THROUGH LOOP, FOR I=1, 1, I.G.49
SQ = 0
FNDSQ SQ = SQ + 1
SQR = SQ * SQ
J = SQR
FNDPFX WHENEVER J.G.I
J = J/10
TRANSFER TO FNDPFX
END OF CONDITIONAL
WHENEVER J.NE.I, TRANSFER TO FNDSQ
LOOP PRINT FORMAT FMT,I,SQR
END OF PROGRAM- Output:
1: 1 2: 25 3: 36 4: 4 5: 529 6: 64 7: 729 8: 81 9: 9 10: 100 11: 1156 12: 121 13: 1369 14: 144 15: 1521 16: 16 17: 1764 18: 1849 19: 196 20: 2025 21: 2116 22: 225 23: 2304 24: 2401 25: 25 26: 2601 27: 2704 28: 289 29: 2916 30: 3025 31: 3136 32: 324 33: 3364 34: 3481 35: 35344 36: 36 37: 3721 38: 3844 39: 3969 40: 400 41: 41209 42: 4225 43: 4356 44: 441 45: 45369 46: 4624 47: 4761 48: 484 49: 49
Mathematica /Wolfram Language
max = 49;
maxlen = IntegerLength[max];
results = <||>;
Do[
sq = i^2;
id = IntegerDigits[sq];
starts = DeleteDuplicates[Take[id, UpTo[#]] & /@ Range[maxlen]];
starts //= Map[FromDigits];
starts //= Select[LessEqualThan[max]];
Do[
If[! KeyExistsQ[results, s],
results = AssociateTo[results, s -> i^2]
]
,
{s, starts}
]
If[Length[results] == max, Break[]]
,
{i, 1, \[Infinity]}
]
Column[results[#] & /@ Range[49]]
- Output:
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
Miranda
main :: [sys_message]
main = [Stdout (lay (map (concat . map (rjustify 6 . show . smallsqr))
(split 10 [1..49])))]
split :: num->[*]->[[*]]
split n [] = []
split n ls = take n ls:split n (drop n ls)
smallsqr :: num->num
smallsqr n = hd [x^2 | x<-[1..]; startswith n (x^2)]
startswith :: num->num->bool
startswith x y = False, if x>y
startswith x y = True, if x=y
startswith x y = startswith x (y div 10)- Output:
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
Modula-2
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.
- Output:
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
Nim
import strutils
const Max = 49
func starts(k: int): (int, int) =
## Return the starting values of "k".
## The first one is less than Max.
## If the first one is in 1..9, the second one is 0 else it is in 1..9.
var k = k
while k > Max: k = k div 10
result[0] = k
if k < 10: return
while k > 9: k = k div 10
result[1] = k
var squares: array[1..Max, int] # Maps "n" to the smallest square beginning with "n".
var count = Max # Number of squares still to found.
var n = 0
while count > 0:
inc n
let n2 = n * n
let (s1, s2) = n2.starts()
if squares[s1] == 0:
squares[s1] = n2
dec count
if s2 != 0 and squares[s2] == 0:
squares[s2] = n2
dec count
for i, n2 in squares:
stdout.write ($n2).align(5)
stdout.write if i mod 7 == 0: '\n' else: ' '
- Output:
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
OCaml
let rec is_prefix a b =
if b > a then is_prefix a (b/10) else a = b
let rec smallest ?(i=1) n =
let square = i*i in
if is_prefix n square then square else smallest n ~i:(succ i)
let _ =
for n = 1 to 49 do
Printf.printf "%d%c" (smallest n) (if n mod 10 = 0 then '\n' else '\t')
done
- Output:
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
Pascal
Free Pascal
Changed search not one by one.
Instead using multiples of trunc(sqrt(n) * sqrt(10)^i)+ [0,1].
Extreme reduced runtime.
45 -> sqrtN = sqrt(45* 1) = 6,7082039 ; sqrtN_10 = sqrt(45* 10) = 21,21320344
6 -> 36,7 -> 49 ; 21 -> 441,22 ->484
sqrtN *10 ;sqrtN_10 * 10
67 ->4489,68 -> 4624 ; 212 -> 44944, 213 -> 45369 (BINGO)
program LowSquareStartN;
uses
sysutils;
function LowSquareStartN(N: Uint32):Uint32;
{Find lowest square that matches N}
var
sqrtN,sqrtN_10,dez : double;
mySqr : Uint64;
Pow10 : int64;
begin
dez := 10;
Pow10:= 1;
sqrtN := sqrt(n);
//to stay more accurate, instead *sqrt(10);
sqrtN_10 := sqrt(n*dez);// one more decimal digit
mySqr := n;
repeat
result := Trunc(sqrtN);
mySqr := result*result;
mySqr := mySqr DIV Pow10;
if mySqr = n then EXIT;
//test only next number
inc(result);
mySqr := (result*result);
mySqr := mySqr DIV pow10;
if mySqr = n then EXIT;
pow10 *= 10;
result := Trunc(sqrtN_10);
mySqr := result*result;
mySqr := mySqr DIV pow10;
if mySqr = n then EXIT;
inc(result);
mySqr := result*result;
mySqr := mySqr DIV pow10;
if mySqr = n then EXIT;
pow10 *= 10;
sqrtN *= dez;
sqrtN_10 *=dez;
until sqrtN > Uint32(-1);
exit(0);readln;
end;
procedure SquareStartsN();
{Find smallest square that begins with N}
var
T : Uint64;
i : Uint32;
begin
writeln('Test 1 .. 49');
for I:=1 to 49 do
begin
T:=LowSquareStartN(I);
write(T*T:7); if i mod 10 = 0 then writeln;
end;
writeln;
writeln;
writeln('Test 999,991 .. 1,000,000');
for I:= 1000*1000-9 to 1000*1000 do
begin
T:= LowSquareStartN(I);
writeln(i:10,':',T:11,'->',t*t:20);
end;
writeln;
T := GetTickCount64;
for I:= 1 to 10*1000*1000-10 do
LowSquareStartN(I);
T := GetTickCount64-T;
writeln('check 1..1E7 in ', T,' ms');
end;
BEGIN
SquareStartsN();
END.
- @home:
Test 1 .. 49
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
Test 999,991 .. 1,000,000
999991: 3162264-> 9999913605696
999992: 999996-> 999992000016
999993: 3162267-> 9999932579289
999994: 999997-> 999994000009
999995: 316227-> 99999515529
999996: 999998-> 999996000004
999997: 3162273-> 9999970526529
999998: 999999-> 999998000001
999999: 3162277-> 9999995824729
1000000: 1000-> 1000000
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 )
Storing only the root ( n_running ) of the square so Uint32 suffices for the result.
Improved version ->335 ms
Stop searching as early as possible->minimize count of divisions (~ n*(1+3.162=sqrt(10)) ) -> 71 ms
increment as long the testsqr didn't change in last digit. Divisions (~ n*(1+1.8662 )) -> 53 ms :-)
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.
- @home:
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
Perl
use strict;
use warnings;
use constant Inf => 10e12; # arbitrarily large value
for my $n (1..49) {
do { printf "%2d: %3d^2 = %5d\n", $n, $_, $_**2 and last if $_**2 =~ /^$n/ } for 1..Inf
}
- Output:
1: 1^2 = 1 2: 5^2 = 25 3: 6^2 = 36 4: 2^2 = 4 5: 23^2 = 529 6: 8^2 = 64 7: 27^2 = 729 8: 9^2 = 81 9: 3^2 = 9 10: 10^2 = 100 11: 34^2 = 1156 12: 11^2 = 121 13: 37^2 = 1369 14: 12^2 = 144 26: 51^2 = 2601 27: 52^2 = 2704 28: 17^2 = 289 29: 54^2 = 2916 30: 55^2 = 3025 31: 56^2 = 3136 32: 18^2 = 324 33: 58^2 = 3364 34: 59^2 = 3481 35: 188^2 = 35344 36: 6^2 = 36 37: 61^2 = 3721 38: 62^2 = 3844 39: 63^2 = 3969 40: 20^2 = 400 41: 203^2 = 41209 42: 65^2 = 4225 43: 66^2 = 4356 44: 21^2 = 441 45: 213^2 = 45369 46: 68^2 = 4624 47: 69^2 = 4761 48: 22^2 = 484 49: 7^2 = 49
Phix
with javascript_semantics
constant lim = 49
sequence res = repeat(0,lim)
integer n = 1, found = 0
while found<lim do
integer n2 = n*n
while n2 do
if n2<=lim and res[n2]=0 then
found += 1
res[n2] = n
end if
n2 = floor(n2/10)
end while
n += 1
end while
res = columnize({tagset(lim),sq_power(res,2),apply(true,sprintf,{{"(%d^2)"},res})})
printf(1,"Smallest squares that begin with 1..%d:\n%s\n",
{lim,join_by(apply(true,sprintf,{{"%2d: %5d %-8s"},res}),10,5)})
- Output:
Smallest squares that begin with 1..49: 1: 1 (1^2) 11: 1156 (34^2) 21: 2116 (46^2) 31: 3136 (56^2) 41: 41209 (203^2) 2: 25 (5^2) 12: 121 (11^2) 22: 225 (15^2) 32: 324 (18^2) 42: 4225 (65^2) 3: 36 (6^2) 13: 1369 (37^2) 23: 2304 (48^2) 33: 3364 (58^2) 43: 4356 (66^2) 4: 4 (2^2) 14: 144 (12^2) 24: 2401 (49^2) 34: 3481 (59^2) 44: 441 (21^2) 5: 529 (23^2) 15: 1521 (39^2) 25: 25 (5^2) 35: 35344 (188^2) 45: 45369 (213^2) 6: 64 (8^2) 16: 16 (4^2) 26: 2601 (51^2) 36: 36 (6^2) 46: 4624 (68^2) 7: 729 (27^2) 17: 1764 (42^2) 27: 2704 (52^2) 37: 3721 (61^2) 47: 4761 (69^2) 8: 81 (9^2) 18: 1849 (43^2) 28: 289 (17^2) 38: 3844 (62^2) 48: 484 (22^2) 9: 9 (3^2) 19: 196 (14^2) 29: 2916 (54^2) 39: 3969 (63^2) 49: 49 (7^2) 10: 100 (10^2) 20: 2025 (45^2) 30: 3025 (55^2) 40: 400 (20^2)
Same output as the Pascal entry, slight tidy
with javascript_semantics
function LowSquareStartN(integer n)
-- Find lowest square that matches n
atom sqrtN = sqrt(n),
sqrtN_10 = sqrt(n*10)
integer pow10 = 1
do
for res in {trunc(sqrtN),trunc(sqrtN_10)} do
for plus01=0 to 1 do
if floor(res*res/pow10)=n then return res end if
res += 1
end for
pow10 *= 10
end for
sqrtN *= 10
sqrtN_10 *= 10
until sqrtN > 10*n
?9/0
end function
procedure SquareStartsN()
-- Find smallest square that begins with N
integer t
printf(1,"Test 1 .. 49\n")
for i=1 to 49 do
t := LowSquareStartN(i)
printf(1,"%7d%n",{t*t,mod(i,10)=0})
end for
printf(1,"\n\nTest 999,991 .. 1,000,000\n")
for i=999991 to 1000*1000 do
t := LowSquareStartN(i)
printf(1,"%10d:%11d->%20d\n",{i,t,t*t})
end for
puts(1,"\n")
end procedure
SquareStartsN()
Picat
Recursion and string approach
import util.
main =>
println([S : N in 1..49, S = smallest_square(N)]).
smallest_square(N) = Square =>
smallest_square(N.to_string,1,Square).
smallest_square(N,S,SS) :-
SS = S*S,
find((SS).to_string,N,1,_).
smallest_square(N,S,SS) :-
smallest_square(N,S+1,SS).- Output:
[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]
Iterative
main =>
println([S : N in 1..49, S = smallest_square2(N)]).
smallest_square2(N) = Ret =>
I = 1,
Found = false,
while (Found == false)
Square = I*I,
while (Square > N)
Square := Square // 10
end,
if Square == N then
Found := I*I
end,
I := I + 1
end,
Ret = Found.- Output:
[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]
PL/I
smallestSquare: procedure options(main);
/* does A begin with B? */
beginsWith: procedure(aa, b) returns(bit);
declare (a, aa, b) fixed decimal(6);
do a = aa repeat(a/10) while(a>b); end;
return(a = b);
end beginsWith;
/* find smallest square that begins with N */
smallestSquare: procedure(n) returns(fixed decimal(6));
declare (n, sqn) fixed decimal(6);
do sqn = 1 repeat(sqn+1) while(^beginsWith(sqn*sqn, n));
end;
return(sqn * sqn);
end smallestSquare;
declare n fixed;
do n = 1 to 49;
put skip list(n,':',smallestSquare(n));
end;
end smallestSquare;- Output:
1 : 1
2 : 25
3 : 36
4 : 4
5 : 529
6 : 64
7 : 729
8 : 81
9 : 9
10 : 100
11 : 1156
12 : 121
13 : 1369
14 : 144
15 : 1521
16 : 16
17 : 1764
18 : 1849
19 : 196
20 : 2025
21 : 2116
22 : 225
23 : 2304
24 : 2401
25 : 25
26 : 2601
27 : 2704
28 : 289
29 : 2916
30 : 3025
31 : 3136
32 : 324
33 : 3364
34 : 3481
35 : 35344
36 : 36
37 : 3721
38 : 3844
39 : 3969
40 : 400
41 : 41209
42 : 4225
43 : 4356
44 : 441
45 : 45369
46 : 4624
47 : 4761
48 : 484
49 : 49
PL/M
100H:
/* CP/M CALLS */
BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
/* PRINT A NUMBER */
PRINT$NUMBER: PROCEDURE (N);
DECLARE S (6) BYTE INITIAL ('.....$');
DECLARE (N, P) ADDRESS, C BASED P BYTE;
P = .S(5);
DIGIT:
P = P - 1;
C = N MOD 10 + '0';
N = N / 10;
IF N > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUMBER;
/* DOES A BEGIN WITH B? */
BEGINS$WITH: PROCEDURE (A, B) BYTE;
DECLARE (A, B) ADDRESS;
DO WHILE A > B;
A = A/10;
END;
RETURN A = B;
END BEGINS$WITH;
/* FIND SMALLEST SQUARE THAT BEGINS WITH N */
SMALLEST$SQUARE: PROCEDURE (N) ADDRESS;
DECLARE (N, SQN, SQ) ADDRESS;
SQN = 1;
DO WHILE 1;
SQ = SQN * SQN;
IF BEGINS$WITH(SQ, N) THEN
RETURN SQ;
SQN = SQN + 1;
END;
END SMALLEST$SQUARE;
DECLARE N ADDRESS;
DO N = 1 TO 49;
CALL PRINT$NUMBER(SMALLEST$SQUARE(N));
CALL PRINT(.(13,10,'$'));
END;
CALL EXIT;
EOF- Output:
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
Prolog
works with swi-prolog © 2024
firstSqr(Num, Sqr):-
Start is ceil(sqrt(Num)),
NumLen is floor(log10(Num)) + 1,
between(Start, inf, N),
Sqr is N * N,
SqrLen is floor(log10(Sqr)) + 1,
Num =:= Sqr div 10**(SqrLen - NumLen),!.
showList(List):-
findnsols(7, _, (member(NumSqr, List), writef('%3r ->%6r', NumSqr)), _),
nl,
fail.
showList(_).
do:-findall([Num, Sqr], (between(1, 49, Num), firstSqr(Num, Sqr)), NumSqrList),
showList(NumSqrList).
- Output:
?- time(do). 1 -> 1 2 -> 25 3 -> 36 4 -> 4 5 -> 529 6 -> 64 7 -> 729 8 -> 81 9 -> 9 10 -> 100 11 -> 1156 12 -> 121 13 -> 1369 14 -> 144 15 -> 1521 16 -> 16 17 -> 1764 18 -> 1849 19 -> 196 20 -> 2025 21 -> 2116 22 -> 225 23 -> 2304 24 -> 2401 25 -> 25 26 -> 2601 27 -> 2704 28 -> 289 29 -> 2916 30 -> 3025 31 -> 3136 32 -> 324 33 -> 3364 34 -> 3481 35 -> 35344 36 -> 36 37 -> 3721 38 -> 3844 39 -> 3969 40 -> 400 41 -> 41209 42 -> 4225 43 -> 4356 44 -> 441 45 -> 45369 46 -> 4624 47 -> 4761 48 -> 484 49 -> 49 % 10,519 inferences, 0.003 CPU in 0.003 seconds (99% CPU, 3934947 Lips) true.
Python
Iterate over prefixes
'''First square prefixed by digits of N'''
from itertools import count
# firstSquareWithPrefix :: Int -> Int
def firstSquareWithPrefix(n):
'''The first perfect square prefixed (in decimal)
by the decimal digits of N.
'''
pfx = str(n)
lng = len(pfx)
return int(
next(
s for s in (
str(x * x) for x in count(0)
)
if pfx == s[0:lng]
)
)
# ------------------------- TEST -------------------------
def main():
'''First matches for the range [1..49]'''
print('\n'.join([
str(firstSquareWithPrefix(x)) for x in range(1, 50)
]))
# MAIN ---
if __name__ == '__main__':
main()
- Output:
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
Iterate over squares
Generate each square (and its prefixes) only once, and stop when the dict has enough entries.
from itertools import accumulate, count
d = {}
for q in accumulate(count(1, 2)):
k = q
while k > 0 and k not in d:
if k < 50: d[k] = q
k //= 10
if len(d) == 49: break
print(*map(d.get, range(1, 50)))
- Output:
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
Quackery
[ dup * ] is squared ( n --> n )
[ 2dup = iff
[ 2drop true ]
done
2dup < iff
[ 2drop false ]
done
dip [ 10 / ]
again ] is starts ( n n --> b )
[ times
[ 0
[ 1+
dup squared
i^ 1+
starts iff
[ squared
echo sp ]
done
again ] ] ] is task ( n --> )
49 task- Output:
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
Raku
# 20210319 Raku programming solution
my @needles = (1..49);
my @haystack = (1..*) Z× (1..*);
# my @haystack = ( 1, 4, -> \a, \b { 2*b - a + 2 } ... * );
# my @haystack = ( 1, { (++$)² } ... * );
for @needles -> \needle {
for @haystack -> \hay {
{ say needle, " => ", hay and last } if hay.starts-with: needle
}
}
- Output:
1 => 1 2 => 25 3 => 36 4 => 4 5 => 529 6 => 64 7 => 729 8 => 81 9 => 9 10 => 100 11 => 1156 12 => 121 13 => 1369 14 => 144 15 => 1521 16 => 16 17 => 1764 18 => 1849 19 => 196 20 => 2025 21 => 2116 22 => 225 23 => 2304 24 => 2401 25 => 25 26 => 2601 27 => 2704 28 => 289 29 => 2916 30 => 3025 31 => 3136 32 => 324 33 => 3364 34 => 3481 35 => 35344 36 => 36 37 => 3721 38 => 3844 39 => 3969 40 => 400 41 => 41209 42 => 4225 43 => 4356 44 => 441 45 => 45369 46 => 4624 47 => 4761 48 => 484 49 => 49
As the desired range is so small, there is not much gained by caching the squares. Less efficient, but less verbose:
say $_ => ^Inf .map(*²).first: *.starts-with: $_ for 1..49;
Same output.
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>>;
};- Output:
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
REXX
A little extra code was added to display the results in a table, the number of columns in the table can be specified.
Also, the output display was generalized so that if a larger number is wider than expected, it won't be truncated.
/*REXX program finds and displays (positive integers) squares that begin with N. */
numeric digits 20 /*ensure that large numbers can be used*/
parse arg n cols . /*get optional number of primes to find*/
if n=='' | n=="," then n= 50 /*Not specified? Then assume default.*/
if cols=='' | cols=="," then cols= 10 /* " " " " " */
w= 10 /*width of a number in any column. */
say ' index │'center(" smallest squares that begin with N < " n, 1 + cols*(w+1) )
say '───────┼'center("" , 1 + cols*(w+1), '─')
#= 0; idx= 1 /*initialize count of found #'s and idx*/
$=; nn= n - 1 /*a list of additive primes (so far). */
do j=1 while #<nn /*keep searching 'til enough nums found*/
do k=1 until pos(j, k * k)==1 /*compute a square of some number. */
end /*k*/
#= # + 1 /*bump the count of numbers found. */
c= commas(k * k) /*calculate K**2 (with commas) and L */
$= $ right(c, max(w, length(c) ) ) /*add square to $ list, allow for big N*/
if #//cols\==0 then iterate /*have we populated a line of output? */
say center(idx, 7)'│' substr($, 2); $= /*display what we have so far (cols). */
idx= idx + cols /*bump the index count for the output*/
end /*j*/
if $\=='' then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/
say '───────┴'center("" , 1 + cols*(w+1), '─')
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
- output when using the default inputs:
index │ smallest squares that begin with N < 50 ───────┼─────────────────────────────────────────────────────────────────────────────────────────────────────────────── 1 │ 1 25 36 4 529 64 729 81 9 100 11 │ 1,156 121 1,369 144 1,521 16 1,764 1,849 196 2,025 21 │ 2,116 225 2,304 2,401 25 2,601 2,704 289 2,916 3,025 31 │ 3,136 324 3,364 3,481 35,344 36 3,721 3,844 3,969 400 41 │ 41,209 4,225 4,356 441 45,369 4,624 4,761 484 49 ───────┴───────────────────────────────────────────────────────────────────────────────────────────────────────────────
Ring
load "stdlib.ring"
see "working..." + nl
see "smallest squares that begin with n:" + nl
row = 0
limit1 = 49
limit2 = 45369
for n = 1 to limit1
strn = string(n)
lenn = len(strn)
for m = 1 to limit2
floor = sqrt(m)
bool = (m % floor = 0)
strm = string(m)
if left(strm,lenn) = n and bool = 1
row = row + 1
see "" + strm + " "
if row%5 = 0
see nl
ok
exit
ok
next
next
see nl + "done..." + nl- Output:
working... smallest squares that begin with n: 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 done...
RPL
≪ → n
≪ 1 WHILE DUP SQ DUP MANT n XPON ALOG * IP MIN n ≠ REPEAT 1 + END SQ
≫ ≫ ‘N2STN’ STO
≪ { } 1 49 FOR j j N2STN + NEXT ≫ EVAL
- Output:
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 5041 }
Ruby
def f(n)
if n < 1 then
return
end
i = 1
while true do
sq = i * i
while sq > n do
sq = (sq / 10).floor
end
if sq == n then
print "%3d %9d %4d\n" % [n, i * i, i]
return
end
i = i + 1
end
end
print("Prefix n^2 n\n")
print()
for i in 1 .. 49
f(i)
end
- Output:
Prefix n^2 n 1 1 1 2 25 5 3 36 6 4 4 2 5 529 23 6 64 8 7 729 27 8 81 9 9 9 3 10 100 10 11 1156 34 12 121 11 13 1369 37 14 144 12 15 1521 39 16 16 4 17 1764 42 18 1849 43 19 196 14 20 2025 45 21 2116 46 22 225 15 23 2304 48 24 2401 49 25 25 5 26 2601 51 27 2704 52 28 289 17 29 2916 54 30 3025 55 31 3136 56 32 324 18 33 3364 58 34 3481 59 35 35344 188 36 36 6 37 3721 61 38 3844 62 39 3969 63 40 400 20 41 41209 203 42 4225 65 43 4356 66 44 441 21 45 45369 213 46 4624 68 47 4761 69 48 484 22 49 49 7
SenseTalk
repeat with n = 1 to 49
put smallestNumberWhoseSquareBeginsWith(n) into num
put !"[[n]]: [[num squared]] is [[num]] squared"
end repeat
to handle smallestNumberWhoseSquareBeginsWith n
repeat forever
if the counter squared begins with n then return the counter
end repeat
end handler- Output:
1: 1 is 1 squared 2: 25 is 5 squared 3: 36 is 6 squared 4: 4 is 2 squared 5: 529 is 23 squared 6: 64 is 8 squared 7: 729 is 27 squared 8: 81 is 9 squared 9: 9 is 3 squared 10: 100 is 10 squared 11: 1156 is 34 squared 12: 121 is 11 squared 13: 1369 is 37 squared 14: 144 is 12 squared 15: 1521 is 39 squared 16: 16 is 4 squared 17: 1764 is 42 squared 18: 1849 is 43 squared 19: 196 is 14 squared 20: 2025 is 45 squared 21: 2116 is 46 squared 22: 225 is 15 squared 23: 2304 is 48 squared 24: 2401 is 49 squared 25: 25 is 5 squared 26: 2601 is 51 squared 27: 2704 is 52 squared 28: 289 is 17 squared 29: 2916 is 54 squared 30: 3025 is 55 squared 31: 3136 is 56 squared 32: 324 is 18 squared 33: 3364 is 58 squared 34: 3481 is 59 squared 35: 35344 is 188 squared 36: 36 is 6 squared 37: 3721 is 61 squared 38: 3844 is 62 squared 39: 3969 is 63 squared 40: 400 is 20 squared 41: 41209 is 203 squared 42: 4225 is 65 squared 43: 4356 is 66 squared 44: 441 is 21 squared 45: 45369 is 213 squared 46: 4624 is 68 squared 47: 4761 is 69 squared 48: 484 is 22 squared 49: 49 is 7 squared
SETL
program smallest_square_that_begins_with_n;
loop for n in [1..49] do
nprint(lpad(str smallest_prefix_square n, 7));
if n mod 10=0 then print; end if;
end loop;
print;
op begins_with(n, s);
loop while n>s do
n div:= 10;
end loop;
return n=s;
end op;
op smallest_prefix_square(n);
loop until s*s begins_with n do
s +:= 1;
end loop;
return s*s;
end op;
end program;- Output:
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
Sidef
1..49 -> map {|n|
[n, n.isqrt..Inf -> first {|j| Str(j**2).starts_with(n) }]
}.slices(5).each {|a|
say a.map { '%2d: %5d %-8s' % (_[0], _[1]**2, "(#{_[1]}^2)") }.join(' ')
}
- Output:
1: 1 (1^2) 2: 25 (5^2) 3: 36 (6^2) 4: 4 (2^2) 5: 529 (23^2) 6: 64 (8^2) 7: 729 (27^2) 8: 81 (9^2) 9: 9 (3^2) 10: 100 (10^2) 11: 1156 (34^2) 12: 121 (11^2) 13: 1369 (37^2) 14: 144 (12^2) 15: 1521 (39^2) 16: 16 (4^2) 17: 1764 (42^2) 18: 1849 (43^2) 19: 196 (14^2) 20: 2025 (45^2) 21: 2116 (46^2) 22: 225 (15^2) 23: 2304 (48^2) 24: 2401 (49^2) 25: 25 (5^2) 26: 2601 (51^2) 27: 2704 (52^2) 28: 289 (17^2) 29: 2916 (54^2) 30: 3025 (55^2) 31: 3136 (56^2) 32: 324 (18^2) 33: 3364 (58^2) 34: 3481 (59^2) 35: 35344 (188^2) 36: 36 (6^2) 37: 3721 (61^2) 38: 3844 (62^2) 39: 3969 (63^2) 40: 400 (20^2) 41: 41209 (203^2) 42: 4225 (65^2) 43: 4356 (66^2) 44: 441 (21^2) 45: 45369 (213^2) 46: 4624 (68^2) 47: 4761 (69^2) 48: 484 (22^2) 49: 49 (7^2)
- Numbered list item
TXR
One Pass Through Squares
In this solution we avoid calculating squares; no multiplication occurs in the code. We generate successive squares using a recurrence relation.
We also avoid doing a starts-with test using digits. Rather, we take each successive square and begin repeatedly dividing it by 10, with a truncating division. Whenever the quotient fits into the range 0 to 49 (valid index for our output table) we check whether the entry at that position is nil. If so, this is the smallest square which begins with the digits of that position and we put it into the table there. When 49 numbers have been placed, indicated by an incrementing counter, the algorithm ends. The [out 0] entry is left null.
(for ((cnt 49) (n 1) (sq 1) (st 3) (out (vector 50)))
((plusp cnt) (each ((x 1..50))
(put-line (pic "## ########" x [out x]))))
((inc sq st) (inc st 2) (inc n))
(for ((xsq sq)) ((plusp xsq)) ((set xsq (trunc xsq 10)))
(when (and (< xsq 50) (null [out xsq]))
(set [out xsq] sq)
(dec cnt))))- Output:
1 1 2 25 3 36 4 4 5 529 6 64 7 729 8 81 9 9 10 100 11 1156 12 121 13 1369 14 144 15 1521 16 16 17 1764 18 1849 19 196 20 2025 21 2116 22 225 23 2304 24 2401 25 25 26 2601 27 2704 28 289 29 2916 30 3025 31 3136 32 324 33 3364 34 3481 35 35344 36 36 37 3721 38 3844 39 3969 40 400 41 41209 42 4225 43 4356 44 441 45 45369 46 4624 47 4761 48 484 49 49
Terse
The following inefficient-but-terse solution produces the same output:
(each ((n 1..50))
(flow [mapcar* square 1]
(find-if (opip digits (starts-with (digits n))))
(pic "## ########" n)
put-line))Loopy
(each ((i 1..50))
(block search
(each ((j 1))
(for ((k (square j)))
((> k i) (when (eql k i)
(put-line (pic "## ########" i (square j)))
(return-from search)))
((set k (trunc k 10)))))))
Uiua
In best YAGNI style, just calculate sufficient squares for the task as specced (up to 220^2)
IsPrefix ← =⧻⟜(/+⬚@.=)
⊞◇IsPrefix °⋕↘1⇡50 °⋕.ⁿ2+1⇡220
⊏≡(⊢⊚)- Output:
[1 25 36 4 529 64 729 81 9 100 1156 ...etc...]
VTL-2
10 N=1
15 C=0
20 S=0
30 S=S+1
40 Q=S*S
50 R=Q
60 #=80
70 R=R/10
80 #=N<R*70
90 #=N=R=0*30
100 ?=Q
110 C=C+1
120 #=C/7*0+%=0*150
130 $=9
140 #=160
150 ?=""
160 N=N+1
170 #=N<50*20- Output:
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
Wren
Version 1
import "./fmt" for Fmt
var isSquare = Fn.new { |n|
var s = n.sqrt.floor
return s * s == n
}
var squares = []
for (i in 1..49) {
if (isSquare.call(i)) {
squares.add(i)
} else {
var n = i
var limit = 10
while (true) {
n = n * 10
var found = false
for (j in 0...limit) {
var s = n + j
if (isSquare.call(s)) {
squares.add(s)
found = true
break
}
}
if (found) break
limit = limit * 10
}
}
}
System.print("Smallest squares that begin with 'n' in [1, 49]:")
Fmt.tprint("$5d", squares, 10)
- Output:
Smallest squares that begin with 'n' in [1, 49]:
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
Version 2
import "./fmt" for Fmt
var lowSquareStartN = Fn.new { |n|
var sqrtN = n.sqrt
var sqrtN10 = (n * 10).sqrt
var pow10 = 1
while (true) {
for (i in [sqrtN.truncate, sqrtN10.truncate]) {
for (j in 0..1) {
var mySqr = (i * i / pow10).floor
if (mySqr == n) return i
i = i + 1
}
pow10 = pow10 * 10
}
sqrtN = sqrtN * 10
sqrtN10 = sqrtN10 * 10
if (sqrtN > 10 * n) break
}
}
System.print("Test 1 .. 49")
for (i in 1..49) {
var t = lowSquareStartN.call(i)
Fmt.write("$7d", t * t)
if (i % 10 == 0) System.print()
}
System.print("\n")
System.print("Test 999,991 .. 1,000,000")
for (i in 999991..1e6) {
var t = lowSquareStartN.call(i)
Fmt.print("$10d : $10d -> $14d", i, t, t * t)
}
- Output:
Similar to Pascal entry.
XPL0
int Count, N, M, Q;
[Count:= 0;
for N:= 1 to 49 do
[M:= 1;
loop [Q:= M*M;
while Q > N do \whittle off low digits
Q:= Q/10;
if Q = N then
[IntOut(0, M*M);
Count:= Count+1;
if rem(Count/10) = 0 then CrLf(0) else ChOut(0, 9\tab\);
quit;
];
M:= M+1;
];
];
]- Output:
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
Yabasic
// Rosetta Code problem: http://rosettacode.org/wiki/Smallest_square_that_begins_with_n
// by Galileo, 05/2022
FOR I = 1 TO 49
J = 1
DO
K = J * J
WHILE K > I K = INT(K / 10) : WEND
IF K = I PRINT J * J, : BREAK
J = J + 1
LOOP
NEXT I- Output:
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 ---Program done, press RETURN---
Zig
pub fn beginsWith(a: u16, b: u16) bool {
var aa = a;
while (aa > b) aa /= 10;
return aa == b;
}
pub fn smallestSquare(n: u16) u16 {
var sqn: u16 = 1;
while (true) : (sqn += 1) {
var sq = sqn * sqn;
if (beginsWith(sq, n)) return sq;
}
}
pub fn main() !void {
const stdout = @import("std").io.getStdOut().writer();
var n: u16 = 1;
while (n < 50) : (n += 1) {
try stdout.print("{d}\n", .{smallestSquare(n)});
}
}
- Output:
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
Categories:
- Draft Programming Tasks
- 11l
- ABC
- Action!
- ALGOL 68
- ALGOL W
- APL
- Arturo
- AutoHotkey
- AWK
- BASIC
- BASIC256
- True BASIC
- Bc
- BQN
- C
- C sharp
- C++
- CLU
- COBOL
- Comal
- Cowgol
- D
- Delphi
- SysUtils,StdCtrls
- Draco
- EasyLang
- Excel
- F Sharp
- Factor
- FOCAL
- FreeBASIC
- Go
- Haskell
- J
- Jq
- JavaScript
- Julia
- Lua
- MAD
- Mathematica
- Wolfram Language
- Miranda
- Modula-2
- Nim
- OCaml
- Pascal
- Free Pascal
- Perl
- Phix
- Picat
- PL/I
- PL/M
- Prolog
- Python
- Quackery
- Raku
- Refal
- REXX
- Ring
- RPL
- Ruby
- SenseTalk
- SETL
- Sidef
- TXR
- Uiua
- VTL-2
- Wren
- Wren-fmt
- XPL0
- Yabasic
- Zig