Steady squares

Steady squares 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.

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>

1. 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>

1. 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.

Works with: Factor version 0.99 2021-06-02

<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: 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

1. 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)
   )

1. ------------------------- TEST -------------------------
2. 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}')

1. ----------------------- GENERIC ------------------------

1. 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

1. 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))
       )
   )

1. ----------------------- GENERIC ------------------------

1. 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

1. 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

Library: Wren-fmt

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