Steady squares
- Euler Project #284
- Task
The 3-digit number 376 in the decimal numbering system is an example of numbers with the special property that its square ends with the same digits: 376*376 = 141376. Let's call a number with this property a steady square. Find steady squares under 10.000
AWK
<lang AWK>
- syntax: GAWK -f STEADY_SQUARES.AWK
BEGIN {
start = 1 stop = 999999 for (i=start; i<=stop; i++) { n = i ^ 2 if (n ~ (i "$")) { printf("%6d^2 = %12d\n",i,n) count++ } } printf("\nSteady squares %d-%d: %d\n",start,stop,count) exit(0)
} </lang>
- Output:
1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376 90625^2 = 8212890625 109376^2 = 11963109376 890625^2 = 793212890625 Steady squares 1-999999: 11
C
<lang c>#include <stdio.h>
- include <stdbool.h>
bool steady(int n) {
int mask=1; for (int d=n; d; d/=10) mask*=10; return (n*n)%mask == n;
}
int main() {
for (int i=1; i<10000; i++) if (steady(i)) printf("%4d^2 = %8d\n", i, i*i); return 0;
}</lang>
- Output:
1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376
CLU
<lang clu>n_digits = proc (n: int) returns (int)
i: int := 0 while n>0 do i := i+1 n := n/10 end return(i)
end n_digits
steady = proc (n: int) returns (bool)
sq: int := n ** 2 return (sq // 10**n_digits(n) = n)
end steady
start_up = proc ()
po: stream := stream$primary_output() for i: int in int$from_to(1, 10000) do if ~steady(i) then continue end stream$putright(po, int$unparse(i), 4) stream$puts(po, "^2 = ") stream$putright(po, int$unparse(i**2), 8) stream$putl(po, "") end
end start_up</lang>
- Output:
1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376
F#
The Function
Implements No Search Required. large values may be produced using only integers. <lang fsharp> // Steady Squares. Nigel Galloway: December 21st., 2021 let fN g=let n=List.fold2(fun z n g->z+n*g) 0L g (g|>List.rev) in (n,g) let five,six=(5L,[|0L..9L|]),(6L,[|0L;9L;8L;7L;6L;5L;4L;3L;2L;1L|]) let stdySq(g0,N)=let rec fG n (g,l)=seq{let i=Array.item(int((n+g)%10L)) N in yield i; yield! (fG((n+g+2L*g0*i)/10L)(fN(i::l)))}
seq{yield g0; yield! fG(g0*g0/10L)(0L,[])}
</lang>
Some Exampleds
<lang fsharp> stdySq six|>Seq.take 80|>Seq.rev|>Seq.iter(printf "%d");printfn "" stdySq five|>Seq.take 80|>Seq.rev|>Seq.iter(printf "%d");printfn "" </lang>
- Output:
61490109937833490419136188999442576576769103890995893380022607743740081787109376 38509890062166509580863811000557423423230896109004106619977392256259918212890625
- Confirming Phix's example for 999 digits (in 11 thousands of sec).
<lang fsharp> stdySq six|>Seq.skip 920|>Seq.take 79|>Seq.rev|>Seq.iter(printf "%d");printfn "..." </lang>
- Output:
7218745998663099139651109156359761242340631780203738180821664795072958006751247... Real: 00:00:00.011
- 9999 digits
<lang fsharp> stdySq six|>Seq.skip 9920|>Seq.take 79|>Seq.rev|>Seq.iter(printf "%d");printfn "...";; </lang>
- Output:
8908826164991254342660560818535016604238201034937718562215376152130910068662033... Real: 00:00:00.330
- If you have 57secs to spare then do 99999 digits, I leave it to the faithless to prove that this a Steady Square.
<lang fsharp> stdySq six|>Seq.skip 99920|>Seq.take 79|>Seq.rev|>Seq.iter(printf "%d");printfn "...";; </lang>
- Output:
2755643458676224038154570844433833690960332159243668007360724907611570195135435... Real: 00:00:57.520
Factor
Only checking numbers that end with 1, 5, and 6. See Talk:Steady_Squares for more details.
<lang factor>USING: formatting kernel math math.functions math.functions.integer-logs prettyprint sequences tools.memory.private ;
- steady? ( n -- ? )
[ sq ] [ integer-log10 1 + 10^ mod ] [ = ] tri ;
1000 <iota> { 1 5 6 } [
[ 10 * ] dip + dup steady? [ dup sq commas "%4d^2 = %s\n" printf ] [ drop ] if
] cartesian-each</lang>
- Output:
1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5,776 376^2 = 141,376 625^2 = 390,625 9376^2 = 87,909,376
Fermat
<lang fermat>Func Isstead( n ) =
m:=n; d:=1; while m>0 do d:=d*10; m:=m\10; od; if n^2|d=n then Return(1) else Return(0) fi.;
for i = 1 to 9999 do
if Isstead(i) then !!(i,'^2 = ',i^2) fi;
od;</lang>
- Output:
1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376
FreeBASIC
<lang freebasic>function numdig( byval n as uinteger ) as uinteger
'number of decimal digits in n dim as uinteger d=0 while n d+=1 n\=10 wend return d
end function
function is_steady_square( n as const uinteger ) as boolean
dim as integer n2 = n^2 if n2 mod 10^numdig(n) = n then return true else return false
end function
for i as uinteger = 1 to 10000
if is_steady_square(i) then print using "####^2 = ########";i;i^2
next i</lang>
- Output:
1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376
jq
Works with gojq, the Go implementation of jq <lang jq># Input: an upper bound, or null for infinite def steady_squares:
range(0; . // infinite) | tostring as $i | select( .*. | tostring | endswith($i));
10000 | steady_squares</lang>
- Output:
0 1 5 6 25 76 376 625 9376
GW-BASIC
<lang gwbasic>10 FOR N = 1 TO 10000 20 M$ = STR$(N) 30 M2#=N*N 40 M$ = RIGHT$(M$,LEN(M$)-1) 50 N2$ = STR$(M2#) 60 A = LEN(M$) 70 IF RIGHT$(N2$,A)= M$ THEN PRINT M$,N2$ 80 NEXT N</lang>
- Output:
1 1 5 25 6 36 25 625 76 5776 376 141376 625 390625 9376 87909376
Haskell
<lang haskell>import Control.Monad (join) import Data.List (isSuffixOf)
NUMBERS WITH STEADY SQUARES --------------
p :: Int -> Bool p = isSuffixOf . show <*> (show . join (*))
TEST -------------------------
main :: IO () main =
print $ takeWhile (< 10000) $ filter p [0 ..]</lang>
- Output:
[0,1,5,6,25,76,376,625,9376]
Or, obtaining the squares by addition, rather than multiplication:
<lang haskell>import Control.Monad (join)
import Data.Bifunctor (bimap)
import Data.List (isSuffixOf)
NUMBERS WITH STEADY SQUARES --------------
steadyPair :: Int -> Int -> [(Int, (String, String))] steadyPair a b =
[ (a, ab) | let ab = join bimap show (a, b), uncurry isSuffixOf ab ]
TEST -------------------------
main :: IO () main =
putStrLn $ unlines ( uncurry ((<>) . (<> " -> ")) . snd <$> takeWhile ((10000 >) . fst) ( concat $ zipWith steadyPair [0 ..] (scanl (+) 0 [1, 3 ..]) ) )</lang>
- Output:
0 -> 0 1 -> 1 5 -> 25 6 -> 36 25 -> 625 76 -> 5776 376 -> 141376 625 -> 390625 9376 -> 87909376
MAD
<lang MAD> NORMAL MODE IS INTEGER
VECTOR VALUES FMT = $I4,7H **2 = ,I8*$ THROUGH LOOP, FOR I=1, 1, I.G.10000 THROUGH POW, FOR MASK=1, 0, MASK.G.I
POW MASK = MASK*10
SQ = I*I WHENEVER SQ-SQ/MASK*MASK.E.I PRINT FORMAT FMT, I, SQ END OF CONDITIONAL
LOOP CONTINUE
END OF PROGRAM</lang>
- Output:
1**2 = 1 5**2 = 25 6**2 = 36 25**2 = 625 76**2 = 5776 376**2 = 141376 625**2 = 390625 9376**2 = 87909376
Perl
<lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Steady_Squares use warnings;
($_ ** 2) =~ /$_$/ and printf "%5d %d\n", $_, $_ ** 2 for 1 .. 10000;</lang>
- Output:
1 1 5 25 6 36 25 625 76 5776 376 141376 625 390625 9376 87909376
Phix
A number n ending in 2,3,4,7,8, or 9 will have a square ending in 4,9,6,9,4 or 1 respectively.
Further a number ending in k 0s will have a square ending in 2*k 0s, and hence always fail, so all possible candidates must end in 1, 5, or 6.
Further, the square of any k-digit number n will end in the same k-1 digits as the square of the number formed from the last k-1 digits of n,
in other words every successful 3-digit n must end with one of the previously successful answers (maybe zero padded), and so on for 4 digits, etc.
I stopped after 8 digits to avoid the need to fire up gmp. Finishes near-instantly, of course.
with javascript_semantics sequence success = {1,5,6} -- (as above) atom p10 = 10 for digits=2 to 8 do for d=1 to 9 do for i=1 to length(success) do atom cand = d*p10+success[i] if remainder(cand*cand,p10*10)=cand then success &= cand end if end for end for p10 *= 10 end for printf(1,"%d such numbers < 100,000,000 found:\n",length(success)) for i=1 to length(success) do atom si = success[i] printf(1,"%,11d^2 = %,21d\n",{si,si*si}) end for
- Output:
15 such numbers < 100,000,000 found: 1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5,776 376^2 = 141,376 625^2 = 390,625 9,376^2 = 87,909,376 90,625^2 = 8,212,890,625 109,376^2 = 11,963,109,376 890,625^2 = 793,212,890,625 2,890,625^2 = 8,355,712,890,625 7,109,376^2 = 50,543,227,109,376 12,890,625^2 = 166,168,212,890,625 87,109,376^2 = 7,588,043,387,109,376
mpz (super fast to 1000 digits)
Obsessed with the idea the series could in fact be finite, I wheeled out gmp anyway... As per the talk page, it turns out that all steady squares (apart from 1) are in fact on a 5-chain and a 6-chain, which carry on forever. The following easily finishes in less than a second.
with javascript_semantics include mpfr.e constant limit = 1000 sequence success = {"1","5","6"} -- (as above) sequence squared = {"1","25","36"} -- (kiss) integer count = 3 mpz ch5 = mpz_init(5), -- the 5-chain ch6 = mpz_init(6), -- the 6-chain p10 = mpz_init(10), {d10,sqr,r10,t10,cand} = mpz_inits(5), ch for digits=2 to limit-1 do for d=1 to 9 do ch = ch5 mpz_mul_si(d10,p10,d) mpz_mul_si(t10,p10,10) for chain=5 to 6 do mpz_add(cand,d10,ch) mpz_mul(sqr,cand,cand) mpz_fdiv_r(r10,sqr,t10) if mpz_cmp(cand,r10)=0 then count += 1 if digits<=12 or digits>=limit-3 then success = append(success,shorten(mpz_get_str(cand))) squared = append(squared,shorten(mpz_get_str(sqr))) end if mpz_set(ch,cand) end if ch = ch6 end for end for mpz_mul_si(p10,p10,10) end for printf(1,"%d steady squares < 1e%d found:\n",{count,limit}) for i=1 to length(success) do printf(1,"%13s^2 = %25s\n",{success[i],squared[i]}) end for
No doubt you could significantly improve that by replacing the mul/div with mpz_powm_ui(r10, cand, 2, t10) and o/c not even trying to print any of the silly-length numbers.
- Output:
1783 steady squares < 1e1000 found: 1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376 90625^2 = 8212890625 109376^2 = 11963109376 890625^2 = 793212890625 2890625^2 = 8355712890625 7109376^2 = 50543227109376 12890625^2 = 166168212890625 87109376^2 = 7588043387109376 212890625^2 = 45322418212890625 787109376^2 = 619541169787109376 1787109376^2 = 3193759921787109376 8212890625^2 = 67451572418212890625 18212890625^2 = 331709384918212890625 81787109376^2 = 6689131260081787109376 918212890625^2 = 843114912509918212890625 18745998663099139651...07743740081787109376 (997 digits)^2 = 35141246587691473110...07743740081787109376 (1,993 digits) 81254001336900860348...92256259918212890625 (997 digits)^2 = 66022127332570868008...92256259918212890625 (1,994 digits) 21874599866309913965...07743740081787109376 (998 digits)^2 = 47849811931116570591...07743740081787109376 (1,995 digits) 78125400133690086034...92256259918212890625 (998 digits)^2 = 61035781460491829128...92256259918212890625 (1,996 digits) 27812540013369008603...92256259918212890625 (999 digits)^2 = 77353738199525217326...92256259918212890625 (1,997 digits) 72187459986630991396...07743740081787109376 (999 digits)^2 = 52110293793214504525...07743740081787109376 (1,998 digits)
Note that should this produce two steady squares of the same length that begin with the same digit, the one that ends in 5 would be shown first, even if it is numerically after then one that ends in 6, not that there are any such < 1e1000. In other words add a flag that effectively swaps the ch = ch5
and ch = ch6
lines.
Python
Procedural
<lang python>print("working...") print("Steady squares under 10.000 are:") limit = 10000
for n in range(1,limit):
nstr = str(n) nlen = len(nstr) square = str(pow(n,2)) rn = square[-nlen:] if nstr == rn: print(str(n) + " " + str(square))
print("done...")</lang>
- Output:
working... Steady squares under 10.000 are: 1 1 5 25 6 36 25 625 76 5776 376 141376 625 390625 9376 87909376 done...
Functional
<lang python>Steady squares
from itertools import count, takewhile
- isSteady :: Int -> Bool
def isSteady(x):
True if the square of x ends with the digits of x itself. return isSuffixOf( str(x) )( str(x ** 2) )
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
Roots of numbers with steady squares up to 10000 xs = takewhile( lambda x: 10000 > x, (x for x in count(0) if isSteady(x)) ) for x in xs: print(f'{x} -> {x ** 2}')
- ----------------------- GENERIC ------------------------
- isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
def isSuffixOf(needle):
True if needle is a suffix of haystack. def go(haystack): d = len(haystack) - len(needle) return d >= 0 and (needle == haystack[d:]) return go
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
0 -> 0 1 -> 1 5 -> 25 6 -> 36 25 -> 625 76 -> 5776 376 -> 141376 625 -> 390625 9376 -> 87909376
Or, defining the squares as an additive accumulation:
<lang haskell>Steady Squares
from itertools import accumulate, chain, count, takewhile from operator import add
def main():
Numbers up to 10000 which have steady squares print( '\n'.join( f'{a} -> {b}' for (a, b) in takewhile( lambda ab: 10000 > ab[0], enumerate( accumulate( chain([0], count(1, 2)), add ) ) ) if isSuffixOf(str(a))(str(b)) ) )
- ----------------------- GENERIC ------------------------
- isSuffixOf :: (Eq a) => [a] -> [a] -> Bool
def isSuffixOf(needle):
True if needle is a suffix of haystack. def go(haystack): d = len(haystack) - len(needle) return d >= 0 and (needle == haystack[d:]) return go
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
0 -> 0 1 -> 1 5 -> 25 6 -> 36 25 -> 625 76 -> 5776 376 -> 141376 625 -> 390625 9376 -> 87909376
Raku
<lang perl6>.say for ({$++²}…*).kv.grep( {$^v.ends-with: $^k} )[1..10]</lang>
- Output:
(1 1) (5 25) (6 36) (25 625) (76 5776) (376 141376) (625 390625) (9376 87909376) (90625 8212890625) (109376 11963109376)
REXX
<lang rexx>/* REXX */ Numeric Digits 50 Call time 'R' n=1000000000 Say 'Steady squares below' n Do i=1 To n
c=right(i,1) If pos(c,'156')>0 Then Do i2=i*i If right(i2,length(i))=i Then Say right(i,length(n)) i2 End End
Say time('E')</lang>
- Output:
Steady squares below 1000000000 1 1 5 25 6 36 25 625 76 5776 376 141376 625 390625 9376 87909376 90625 8212890625 109376 11963109376 890625 793212890625 2890625 8355712890625 7109376 50543227109376 12890625 166168212890625 87109376 7588043387109376 212890625 45322418212890625 787109376 619541169787109376 468.422000
Ring
<lang ring> see "working..." +nl see "Steady squatres under 10.000 are:" + nl limit = 10000
for n = 1 to limit
nstr = string(n) len = len(nstr) square = pow(n,2) rn = right(string(square),len) if nstr = rn see "" + n + " -> " + square + nl ok
next
see "done..." +nl </lang>
- Output:
working... Steady numbers under 10.000 are: 1 -> 1 5 -> 25 6 -> 36 25 -> 625 76 -> 5776 376 -> 141376 625 -> 390625 9376 -> 87909376 done...
Tiny BASIC
Because TinyBASIC is limited to signed 16-bit integers, we need to perform the squaring by repeated addition and then take modulus. That makes for a pretty inefficient solution.
<lang tinybasic>REM N = THE NUMBER TO BE SQUARED REM D = 10^THE NUMBER OF DIGITS IN N REM M = THE SQUARE OF N, MODULO D REM T = TEMP COPY OF N
LET N = 1 LET D = 10 10 IF N > 9 THEN LET D = 100 IF N > 99 THEN LET D = 1000 IF N > 999 THEN LET D = 10000 LET M = 0 LET T = N 20 LET M = M + N LET M = M - (M/D)*D LET T = T - 1 IF T > 0 THEN GOTO 20 rem PRINT N, " ", M IF M = N THEN PRINT N LET N = N + 1 IF N < 10000 THEN GOTO 10 END</lang>
- Output:
1 5 6 25 76 376 625
9376
Wren
Although it hardly matters for a small range such as this, one can cut down the numbers to be examined by observing that a steady square must end in 1, 5 or 6. <lang ecmascript>import "./fmt" for Fmt
System.print("Steady squares under 10,000:") var finalDigits = [1, 5, 6] for (i in 1..9999) {
if (!finalDigits.contains(i % 10)) continue var sq = i * i if (sq.toString.endsWith(i.toString)) Fmt.print("$,5d -> $,10d", i, sq)
}</lang>
- Output:
Steady squares under 10,000: 1 -> 1 5 -> 25 6 -> 36 25 -> 625 76 -> 5,776 376 -> 141,376 625 -> 390,625 9,376 -> 87,909,376
XPL0
<lang XPL0>int N, P; [for N:= 0 to 10000-1 do
[P:= 1; repeat P:= P*10 until P>N; if rem(N*N/P) = N then [IntOut(0, N); Text(0, "^^2 = "); IntOut(0, N*N); CrLf(0); ]; ];
]</lang>
- Output:
0^2 = 0 1^2 = 1 5^2 = 25 6^2 = 36 25^2 = 625 76^2 = 5776 376^2 = 141376 625^2 = 390625 9376^2 = 87909376