Steady squares: Difference between revisions
m (Output fixes) |
|||
Line 134: | Line 134: | ||
if Isstead(i) then !!(i,'^2 = ',i^2) fi; |
if Isstead(i) then !!(i,'^2 = ',i^2) fi; |
||
od;</lang> |
od;</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
1^2 = 1 |
1^2 = 1 |
||
5^2 = 25 |
5^2 = 25 |
||
Line 164: | Line 165: | ||
if is_steady_square(i) then print using "####^2 = ########";i;i^2 |
if is_steady_square(i) then print using "####^2 = ########";i;i^2 |
||
next i</lang> |
next i</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
1^2 = 1 |
1^2 = 1 |
||
5^2 = 25 |
5^2 = 25 |
||
Line 208: | Line 210: | ||
70 IF RIGHT$(N2$,A)= M$ THEN PRINT M$,N2$ |
70 IF RIGHT$(N2$,A)= M$ THEN PRINT M$,N2$ |
||
80 NEXT N</lang> |
80 NEXT N</lang> |
||
{{out}} |
{{out}} |
||
<pre> |
|||
1 1 |
1 1 |
||
5 25 |
5 25 |
Revision as of 11:02, 23 December 2021
- 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
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#
Implements Reduce search range by observation of the results <lang fsharp> // Steady Squares. Nigel Galloway: December 21st., 2021 let fN g=let rec fG n g=if n=0UL then true else match n%10UL=g%10UL with true->fG(n/10UL)(g/10UL) |_->false in fG g (g*g) let rec fG n g=seq{let e=[for n in n do for l in 1UL..9UL->n+g*l]|>List.filter fN in yield! e; yield! fG(n@e)(g*10UL)} seq{yield! [1UL;5UL;6UL]; yield! fG [1UL;5UL;6UL] 10UL|>Seq.takeWhile((>)1000000000UL)}|>Seq.iter(fun n->printfn "%9d->%d" n (n*n)) </lang>
- Output:
1->1 5->25 6->36 25->625 76->5776 625->390625 376->141376 9376->87909376 90625->8212890625 109376->11963109376 890625->793212890625 7109376->50543227109376 2890625->8355712890625 87109376->7588043387109376 12890625->166168212890625 787109376->619541169787109376 212890625->45322418212890625
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
Obsessed with the idea the series could in fact be finite, I wheeled out gmp anyway and found all n all
the way up to a (quite random) 548-digit n, so here it is.
(In other words I am now reasonably confident the series is indeed probably infinite, which would have been a pretty sensible prediction in the first place...)
with javascript_semantics include mpfr.e sequence success = {"1","5","6"} -- (as above) sequence squared = {"1","25","36"} -- (kiss) mpz p10 = mpz_init(10), {d10,sqr,r10} = mpz_inits(3) --for digits=2 to 8 do for digits=2 to 48 do --for digits=2 to 548 do -- (no real reason...) for d=1 to 9 do for i=1 to length(success) do mpz_mul_si(d10,p10,d) mpz cand = mpz_init(success[i]) mpz_add(cand,d10,cand) mpz_mul_si(d10,p10,10) mpz_mul(sqr,cand,cand) mpz_fdiv_r(r10,sqr,d10) if mpz_cmp(cand,r10)=0 then success = append(success,mpz_get_str(cand)) squared = append(squared,mpz_get_str(sqr)) end if end for end for mpz_mul_si(p10,p10,10) end for printf(1,"%d such numbers found:\n",length(success)) for i=1 to length(success) do string si = shorten(success[i]), sq = shorten(squared[i]) printf(1,"%12s^2 = %21s\n",{si,sq}) end for
Output is the same as the above, except for the number of them found and lots more output that no-one here should have any interest in seeing.
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)
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...
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
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