Steady squares: Difference between revisions
(→{{header|Wren}}: Correction - can't end in 0 in fact.) |
(→{{header|Phix}}: added gmp version) |
||
Line 186: | Line 186: | ||
87,109,376^2 = 7,588,043,387,109,376 |
87,109,376^2 = 7,588,043,387,109,376 |
||
</pre> |
</pre> |
||
===mpz=== |
|||
Obsessed with the idea the series could in fact be finite, I wheeled out gmp anyway and found examples all |
|||
the way up to a (quite random) 548-digit n, so here it is. |
|||
<!--<lang Phix>(phixonline)--> |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">success</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"6"</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (as above)</span> |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">squared</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"1"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"25"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"36"</span><span style="color: #0000FF;">}</span> <span style="color: #000080;font-style:italic;">-- (kiss)</span> |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">p10</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">),</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">d10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sqr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r10</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #000080;font-style:italic;">--for digits=2 to 8 do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">digits</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">48</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #000080;font-style:italic;">--for digits=2 to 548 do -- (no real reason...)</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">success</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cand</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">success</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cand</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cand</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cand</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cand</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #7060A8;">mpz_fdiv_r</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sqr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d10</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cand</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r10</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">success</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">success</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cand</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #000000;">squared</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">squared</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sqr</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d such numbers < 100,000,000 found:\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">success</span><span style="color: #0000FF;">))</span> |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">success</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">si</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">success</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]),</span> |
|||
<span style="color: #000000;">sq</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">squared</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%12s^2 = %21s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">si</span><span style="color: #0000FF;">,</span><span style="color: #000000;">sq</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<!--</lang>--> |
|||
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, and obviously that hard-coded 1e8 limit is now nonsense. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 16:06, 21 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#
<lang fsharp> // Steady Squares. Nigel Galloway: December 21st., 2021 let rec fG n g=match g with 0->true |g when n%10=g%10->fG(n/10)(g/10) |_->false [for n in 0..999 do for g in [1;5;6]->10*n+g]|>List.filter(fun n->fG(n*n)n)|>List.iter(printf "%d ") </lang>
- Output:
1 5 6 25 76 376 625 9376
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
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 = 3906259376^2 = 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 examples all the way up to a (quite random) 548-digit n, so here it is.
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 < 100,000,000 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, and obviously that hard-coded 1e8 limit is now nonsense.
Python
<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...
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...
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