Smallest square that begins with n
- Task
Find the smallest (decimal integer) squares that begin with n for 0 < n < 50
ALGOL W
<lang algolw>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.</lang>
- 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
<lang 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;
}</lang>
- 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
F#
<lang fsharp> // 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 "" </lang>
- 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
<lang 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</lang>
- 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)
FreeBASIC
<lang 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</lang>
- 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
<lang 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()
}
}</lang>
- 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
Julia
<lang julia>function squaresstartingupto(n, verbose=true)
res, numfound = zeros(Int, n), 0
p_int = collect(1:n)
p_string = string.(p_int)
for i in 1:typemax(Int)
sq = i * i
sq_s = string(sq)
for (j, s) in enumerate(p_string)
if res[j] == 0 && length(sq_s) >= length(s) && sq_s[1:length(s)] == s
res[j] = sq
numfound += 1
end
end
if numfound == n
if verbose
for p in enumerate(res)
print(rpad(p[2], 6), p[1] % 10 == 0 ? "\n" : "")
end
end
break
end
end
return res
end
squaresstartingupto(49)
</lang>
- 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
Perl
<lang 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
}</lang>
- 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
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)
Raku
<lang perl6># 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
}
}</lang>
- 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:
<lang perl6>say $_ => ^Inf .map(*²).first: *.starts-with: $_ for 1..49;</lang>
Same output.
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. <lang rexx>/*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.*/ 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 ?</lang>
- 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
<lang 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 </lang>
- 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...
Wren
<lang ecmascript>import "/seq" for Lst 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]:") for (chunk in Lst.chunks(squares, 10)) Fmt.print("$5d", chunk)</lang>
- 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