Iterated digits squaring: Difference between revisions
→{{header|Fōrmulæ}}
m (Updated description and link for Fōrmulæ solution) |
|||
| (19 intermediate revisions by 15 users not shown) | |||
Line 7:
An example in Python:
<
>>> iterate = lambda x: x if x in [1, 89] else iterate(step(x))
>>> [iterate(x) for x in xrange(1, 20)]
[1, 89, 89, 89, 89, 89, 1, 89, 89, 1, 89, 89, 1, 89, 89, 89, 89, 89, 1]</
Line 27:
* [[Digital root]]
* [[Digital root/Multiplicative digital root]]
* [[Happy numbers]]
<br><br>
Line 32 ⟶ 33:
{{trans|Python}}
<
V result = 0
L x > 0
Line 82 ⟶ 83:
result += check(number)
print(result)</
{{out}}
Line 90 ⟶ 91:
=={{header|Ada}}==
<
procedure Digits_Squaring is
Line 129 ⟶ 130:
end loop;
Put_Line ("In range 1 .. 99_999_999: " & Count'Image);
end Digits_Squaring;</
{{out}}
Line 137 ⟶ 138:
=={{header|ALGOL 68}}==
Brute-force with some caching.
<
# compute a table of the sum of the squared digits of the numbers 00 to 99 #
Line 185 ⟶ 186:
OD;
print( ( "Number of values whose squared digit sum is 89: ", whole( count 89, -10 ), newline ) )</
{{out}}
<pre>
Number of values whose squared digit sum is 89: 85744333
</pre>
=={{header|Arturo}}==
{{trans|Nim}}
<syntaxhighlight lang="rebol">gen: function [n][
result: n
while [not? in? result [1 89]][
s: new 0
loop digits result 'd ->
's + d*d
result: s
]
return result
]
chainsEndingWith89: function [ndigits][
[prevCount,currCount]: #[]
loop 0..9 'i -> prevCount\[i*i]: 1
res: new 0
loop 2..ndigits 'x [
currCount: #[]
loop prevCount [val,cnt][
v: to :integer val
loop 0..9 'newDigit [
mm: v + newDigit*newDigit
if not? key? currCount mm -> currCount\[mm]: 0
currCount\[mm]: currCount\[mm] + cnt
]
]
prevCount: currCount
]
loop currCount [val,cnt][
v: to :integer val
if and? [v <> 0] [89=gen v] ->
'res + cnt
]
return res
]
print [
"Number chains for integers <100000000 that end with an 89 value:"
chainsEndingWith89 8
]</syntaxhighlight>
{{out}}
<pre>Number chains for integers <100000000 that end with an 89 value: 85744333</pre>
=={{header|AWK}}==
We use a brute-force approach with buffering for better performance. Numbers are assumed to be double precision floats, which is true for most implementations. It runs in about 320 s on an Intel i5.
<
BEGIN {
# Setup buffer for results up to 9*9*8
Line 220 ⟶ 269:
}
return r
}</
{{out}}
<pre>
Line 237 ⟶ 286:
{{works with|BBC BASIC for Windows}}
Three versions timed on a 2.50GHz Intel Desktop.
<
REM ---------------------------------------------------------
T%=TIME
Line 294 ⟶ 343:
PRINT "Version 3: ";N% " in ";(TIME-T%)/100 " seconds."
END</
{{out}}
<pre>
Line 305 ⟶ 354:
This is just a brute force solution, so it's not very fast. A decent interpreter will probably take a minute or two for a 1,000,000 iterations. If you want to test with 100,000,000 iterations, change the <tt>::**</tt> (100³) near the end of the first line to <tt>:*:*</tt> (100²<sup>²</sup>). With that many iterations, though, you'll almost certainly want to be using a compiler, otherwise you'll be waiting a long time for the result.
<
v0:\+<_:55+%:*^^"d":+1$<:
>\`!#^ _$:"Y"-#v_$\1+\:^0
>01-\0^ @,+55.<>:1>-!>#^_
>,,,$." >=",,,^ >>".1">#<</
{{out}}
Line 316 ⟶ 365:
<pre>1..100000000 => 85744333</pre>
=={{header|BQN}}==
A simple solution is to compute all square-digit sums in the desired range as an addition table, then repeatedly select from this list using itself as an index so that all values that end at 1 converge (those that reach 89 will find some point in the cycle, but not always the same one).
<syntaxhighlight lang="bqn"> +´1?1? ?˜?(?2???) ?+?´6?<ט?10
856929</syntaxhighlight>
It will take a lot of memory and many seconds to compute the count under 1e8 this way. The following program computes the count for numbers below <code>10???</code> by using dynamic programming to determine how many numbers have each possible digit sum. Then it finds the fate of each number in this greatly reduced set. This gives an exact result for inputs up to 16, taking a fraction of a millisecond for each.
<syntaxhighlight lang="bqn">DigSq ? {
d ? ט ?10 # Digit values
m ? 1+81×2??? # One plus maximum digit sum
c ? (+´ d ??0?»¨ <)??? m??1 # Count of numbers having each sum
s ? m ? ? d +??(?10??m) 0 # Sum for each sum
e ? 1??˜?(?2???)s # Which sums end at 89
¯1 +´ c×e # Total up; subtract 1 to exclude 0
}</syntaxhighlight>
<syntaxhighlight lang="bqn"> >??DigSq¨ 1+?16
+-
? 1 7
2 80
3 857
4 8558
5 85623
6 856929
7 8581146
8 85744333
9 854325192
10 8507390852
11 84908800643
12 850878696414
13 8556721999130
14 86229146720315
15 869339034137667
16 8754780882739336
+</syntaxhighlight>
=={{header|C}}==
C99, tested with "gcc -std=c99". Record how many digit square sum combinations there are. This reduces <math>10^n</math> numbers to <math>81n</math>, and the complexity is about <math>O(n^2)</math>. The 64 bit integer counter is good for up to <math>10^{19}</math>, which takes practically no time to run.
<
typedef unsigned long long ull;
Line 365 ⟶ 452:
return 0;
}</
{{out}}
<pre>
Line 390 ⟶ 477:
</pre>
Fast C implementation (<1 second my machine), which performs iterated digits squaring only once for each unique 8 digit combination. The cases 0 and 100,000,000 are ignored since they don't sum to 89:
<syntaxhighlight lang="c">
#include <stdio.h>
Line 473 ⟶ 560:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>85744333</pre>
Line 480 ⟶ 567:
The largest sum possible for any number is 9*9*9, so the first 730 numbers are calculated and stored in an array.<br/>
The rest is then looked up. A limit of 100 million takes about 6 seconds. int.MaxValue takes about 2 and a half minutes.
<
public static class IteratedDigitsSquaring
{
Line 513 ⟶ 600:
}
}</
{{out}}
<pre>
Line 524 ⟶ 611:
{{Libheader|System.Numerics}}
Translation of the first C version, with BigIntegers. This can get pretty far in six seconds, even on Tio.run.
<
using System.Numerics;
Line 561 ⟶ 648:
Console.WriteLine("{0} seconds elapsed.", (DateTime.Now - st).TotalSeconds);
}
}</
{{out}}
<pre style="height:30ex;overflow:scroll">1->10^1 : 7
Line 797 ⟶ 884:
=={{header|C++}}==
Slow (~10 seconds on my machine) brute force C++ implementation:
<
#include <iostream>
Line 835 ⟶ 922:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>85744333</pre>
=={{header|Ceylon}}==
<
function digitsSquaredSum(variable Integer n) {
Line 867 ⟶ 954:
}
print(eightyNines);
}</
=={{header|Clojure}}==
===Direct Method===
<
(:require [clojure.math.numeric-tower :as math])
(:use [criterium.core])
Line 908 ⟶ 995:
(time (println (direct-method 8)))
</syntaxhighlight>
{{Output}}
<pre>
Line 915 ⟶ 1,002:
</pre>
===Using Combinations===
<syntaxhighlight lang="lisp">
(def DIGITS (range 0 10))
Line 963 ⟶ 1,050:
(println (itertools-comb 8))
;; Time obtained using benchmark library (i.e. (bench (itertools-comb 8)) )
</syntaxhighlight>
{{{Output}}
<pre>
Line 972 ⟶ 1,059:
=={{header|Common Lisp}}==
<
(defun square (number)
(expt number 2))
Line 1,005 ⟶ 1,092:
(incf count))
:finally (return count)))
</syntaxhighlight>
{{out}}
Line 1,018 ⟶ 1,105:
*
</pre>
=={{header|Craft Basic}}==
<syntaxhighlight lang="basic">for i = 1 to 1000
let j = i
do
let k = 0
do
let k = int(k + (j % 10) ^ 2)
let j = int(j / 10)
wait
loop j <> 0
let j = k
loopuntil j = 89 or j = 1
if j > 1 then
let n = n + 1
endif
print "iterations: ", i
next i
print "count result: ", n
end</syntaxhighlight>
{{out}}
<pre>
857
</pre>
=={{header|D}}==
A simple memoizing partially-imperative brute-force solution:
<
uint step(uint x) pure nothrow @safe @nogc {
Line 1,039 ⟶ 1,167:
void main() {
iota(1, 100_000_000).filter!(x => x.iterate == 89).count.writeln;
}</
{{out}}
<pre>85744333</pre>
Line 1,045 ⟶ 1,173:
A fast imperative brute-force solution:
<
import core.stdc.stdio: printf;
Line 1,085 ⟶ 1,213:
printf("%u\n", magicCount);
}</
The output is the same.
The run-time is less than 3 seconds compiled with ldc2.
A more efficient solution:
<
enum factorial = (in uint n) pure nothrow @safe @nogc
Line 1,163 ⟶ 1,291:
printf("%u\n", result);
}</
The output is the same.
The run-time is about 0.04 seconds or less.
Line 1,171 ⟶ 1,299:
A purely functional version, from the Haskell code. It includes two functions currently missing in Phobos used in the Haskell code.
{{trans|Haskell}}
<
auto divMod(T)(T x, T y) pure nothrow @safe @nogc {
Line 1,230 ⟶ 1,358:
void main() {
iota(1u, 100_000u).filter!(n => n.iter == 89).count.writeln;
}</
With a small back-porting (to run it with the Phobos of LDC2 2.065) it runs in about 15.5 seconds.
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
Takes 16 seconds to complete on an a Ryzen 7 Win11 machine
<syntaxhighlight lang="Delphi">
function SumSquaredDigits(N: integer): integer;
{Sum the squares of the digits in a number}
var T: integer;
begin
Result:=0;
repeat
begin
T:=N mod 10;
N:=N div 10;
Result:=Result+T*T;
end
until N<1;
end;
function TestNumber(N: integer): integer;
{Sum the squares of the digits of number, and do it again}
{with tne new number until the result is either 89 or 1}
begin
Result:=N;
repeat Result:=SumSquaredDigits(Result);
until (Result=89) or (Result=1);
end;
procedure TestSquareDigitsSum(Memo: TMemo);
{Count the number of square digit sums end up 89}
var I,Cnt: integer;
begin
Cnt:=0;
for I:=1 to 100000000 do
if TestNumber(I)=89 then Inc(Cnt);
Memo.Lines.Add(IntToStr(Cnt));
end;
</syntaxhighlight>
{{out}}
<pre>
85744333
</pre>
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM ITERATION
Line 1,253 ⟶ 1,430:
PRINT
END PROGRAM
</syntaxhighlight>
This program verifies a number only. With a FOR..END FOR loop it's possible to verify a number range.
=={{header|Factor}}==
A brute-force approach with some optimizations. It uses the fact that the first digit-square-sum of any number < 100,000,000 is, at most, 648. These few chains are rapidly memoized as the results for all hundred-million numbers are calculated for the first time or looked up.
<syntaxhighlight lang="factor">USING: kernel math math.ranges math.text.utils memoize
prettyprint sequences tools.time ;
IN: rosetta-code.iterated-digits-squaring
Line 1,274 ⟶ 1,451:
] loop
drop .
] time</
{{out}}
<pre>
85744333
Running time: 55.76544594 seconds
</pre>
=={{header|Forth}}==
<syntaxhighlight lang="forth">
Tested for VFX Forth and GForth in Linux
\ To explain the algorithm: Each iteration is performed in set-count-sumsq below.
\ sum square of digits for 1 digit numbers are
\ Base 1 2 3 4 5 6 7 8 9
\ Sumsq: 1 4 9 16 25 36 49 54 81
\ Adding 10 to the base adds 1 to the sumsq,
\ Adding 20 to the base adds 4
\ ||
\ Adding 90 adds 81
\ Similarly for n00, n000 etc..
\ Worked example for base 3 ( to keep the lists short ).
\ The base 10 version performs 1.1 .. 1.9 with shifts of 1, 4, 9 .. 81 cells
\
\ Ix 0 1 2 3 4 5 6 7 8
\ 0 [ 1 ]
\ 1.1 [ 1 ] Previous result shifted 1 cell ( 1**2 )
\ 1.2 [ 1 ] Previous result shifted 4 cells ( 2** 2 )
\ ------------------------------
\ Sum [ 1, 1, 0, 0, 1 ]
\ 2.1 [ 1, 1, 0, 0, 1 ] Previous result shifted 1 cell ( 1**2 )
\ 2.2 [ 1, 1, 0, 0, 1 ] Previous result shifted 4 cells ( 2** 2 )
\ --------------------------------------------
\ Sum [ 1, 2, 1, 0, 2, 2, 0, 0, 1 ] Number of integers with ix as first iteration sum of digits sq
CELL 8 * 301 * 1000 / CONSTANT max-digits \ 301 1000 / is log10( 2 )
\ 19 for a 64 bit Forth and 9 for a 32 bit one.
\ **********************************
\ **** Create a counted array ****
\ **********************************
: counted-array \ create: #elements -- ; does> -- a ;
CREATE
HERE SWAP 1+ CELLS DUP ALLOT ERASE
DOES> ;
\ ***********************************
\ **** Array manipulation words. ****
\ ***********************************
: arr-copy \ a-src a-dest -- ; \ Copy array array at a-src to array at a-dest
OVER @ 1+ CELLS CMOVE ;
: arr-count \ a -- a' ct ;
\ Fetch the count of cells in the array and shift addr to point to element 0.
DUP CELL+ SWAP @ ;
: th-element \ a ix -- a' ; \ Leave address of the ix th element of array at a on the stack
1+ CELLS + ;
: arr-empty \ a -- ; \ Sets all array elements to zero and zero length
dup @ 1+ CELLS ERASE ;
: arr+ \ a-src a-dest count -- ;
\ Add each cell from a-src to the cells from a-dest for count elements
\ Storing the result in a-dest
CELLS 0 DO
OVER I + @ OVER I + +! \ I is a byte count offset into either array
CELL +LOOP
2DROP ; \ DROP the two base addresses
: arr. \ a -- ; \ Print the array. Used to debug.
." [ " arr-count CELLS BOUNDS ?DO i @ . CELL +LOOP ." ]" ;
\ ***********************************
\ **** Sum digit squared words ****
\ ***********************************
: sum-digit-sq \ n -- n' ;
0 SWAP
BEGIN DUP WHILE
10 /MOD >R DUP * + R>
REPEAT DROP ;
: 89or1<> \ n -- f ; \ True if n not equal to 89 or 1.
DUP 89 <> AND 1 > ;
: iterated-89= \ n -- f ; \ True if n iterates to 89, false once it iterates to 1 ( or 0 ).
BEGIN DUP 89or1<> WHILE
sum-digit-sq
REPEAT 89 = ;
\ *****************************************************
\ **** Create `count-sumsq` and `sumsq-old` arrays ****
\ *****************************************************
max-digits 81 * 1+ counted-array count-sumsq
max-digits 1- 81 * 1+ counted-array sumsq-old
: init-count-sumsq \ -- ; \ Initialise the count-sumsq to [ 1 ]
count-sumsq arr-empty \ Ensure all zero
1 count-sumsq ! \ Set the length of the count-sumsq to 1 cell.
1 count-sumsq 0 th-element ! ; \ Store 1 in the first element.
: set-count-sumsq \ #digits -- ; \ The main work. Only called with valid #digits
init-count-sumsq
0 ?DO
count-sumsq sumsq-old arr-copy \ copy count-sumsq to sumsq-old
81 count-sumsq +! \ Extend count-sumsq by 81 (9*9) cells
10 1 DO
sumsq-old arr-count ( a-sumsq-old' len )
count-sumsq I DUP * th-element SWAP arr+
LOOP
LOOP ;
: count-89s \ #digits -- n ;
DUP max-digits U> IF
." Number of digits must be between 0 and " max-digits .
DROP 0
ELSE
set-count-sumsq
0 count-sumsq @ 0 DO
count-sumsq I th-element @ ( cum ith-count )
I iterated-89= \ True if the index delivers 89.
AND + \ True is -1 ( all bits set ) AND with the count and add to the cum.
LOOP
THEN ;
: test \ #digits :
CR max-digits min 1+ 1 ?DO
I 5 .r 2 SPACES I count-89s . CR
LOOP ;
</syntaxhighlight>
{{out}}
<pre>
19 test
1 7
2 80
3 857
4 8558
5 85623
6 856929
7 8581146
8 85744333
9 854325192
10 8507390852
11 84908800643
12 850878696414
13 8556721999130
14 86229146720315
15 869339034137667
16 8754780882739336
17 87975303595231975
18 881773944919974509
19 8816770037940618762
</pre>
=={{header|FreeBASIC}}==
<
' similar to C Language (first approach)
Line 1,328 ⟶ 1,654:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,337 ⟶ 1,663:
=={{header|Frink}}==
<
total = 0
d = new dict
Line 1,368 ⟶ 1,694:
println[total]
</syntaxhighlight>
{{out}}
Line 1,377 ⟶ 1,703:
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Iterated_digits_squaring}}
'''Solution'''
The following function returns the end value (either 1 or 89) of a given number:
[[File:Fōrmulæ - Iterated digits squaring 01.png]]
The following function calculates the number of 89 endings, from 1 to a given number:
[[File:Fōrmulæ - Iterated digits squaring 02.png]]
'''Test case'''
[[File:Fōrmulæ - Iterated digits squaring 03.png]]
[[File:Fōrmulæ - Iterated digits squaring 04.png]]
=={{header|Go}}==
It's basic. Runs in about 30 seconds on an old laptop.
<
import (
Line 1,415 ⟶ 1,753:
}
fmt.Println(u89)
}</
{{out}}
<pre>
Line 1,423 ⟶ 1,761:
=={{header|Haskell}}==
Basic solution that contains just a little more than the essence of this computation. This runs in less than eight minutes:
<
import Data.Tuple (swap)
Line 1,435 ⟶ 1,773:
main = do
print $ length $ filter ((== 89) . iter) [1 .. 99999999]</
{{out}}
<pre>85744333</pre>
Line 1,443 ⟶ 1,781:
Here's an expression to turn a number into digits:
<
And here's an expression to square them and find their sum:
<
But note that while the task description claims "you always end with either 1 or 89", that claim is somewhat arbitrary.
:But only somewhat the loop is 89
:: You should move this comment (and my reply here) to the talk page. --[[User:Rdm|Rdm]] ([[User talk:Rdm|talk]]) 03:01, 26 September 2022 (UTC)
<
15 26 40 16 37 58 89 145 42 20 4 16 37 58 89 145</
Here, after the initial three values, the final digit repeats with a period of 8 (so it does not end).
<syntaxhighlight lang=J> 10 8$sumdigsq^:(i.80) 15
15 26 40 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145
42 20 4 16 37 58 89 145</syntaxhighlight>
You could just as easily claim that you always end with either 1 or 4. So here's a routine which repeats the sum-square process until the sequence converges, or until it reaches the value 4:
<
But we do not actually need to iterate. The largest value after the first iteration would be:
<
648</
So we could write a routine which works for the intended range, and stops after the first iteration:
<
digsq1e8=:(I.itdigsq1 i.649) e.~ sumdigsq</
In other words, if the result after the first iteration is any of the numbers in the range 0..648 which converges to 1, it's not a result which would converge to the other loop. This is considerably faster than trying to converge 1e8 sequences, and also evades having to pick an arbitrary stopping point for the sequence which loops for the bulk computation.
Line 1,471 ⟶ 1,824:
And this is sufficient to find our result. We don't want to compute the entire batch of values in one pass, however, so let's break this up into 100 batches of one million each:
<
85744333</
Of course, there are faster ways of obtaining that result. The fastest is probably this:
<
85744333</
This might be thought of as representing the behavior of a highly optimized compiled program. We could abstract this further by using the previous expression at compile time, so we would not have to hard code it.
Line 1,482 ⟶ 1,835:
=={{header|Java}}==
{{works with|Java|8}}
<
public class IteratedDigitsSquaring {
Line 1,505 ⟶ 1,858:
return n;
}
}</
<pre>85744333</pre>
Line 1,517 ⟶ 1,870:
'''Part 1: Foundations'''
<
# Pick n items (with replacement) from the input array,
Line 1,539 ⟶ 1,892:
else . + [[$item, 1]]
end
end ) ;</
'''Part 2: The Generic Task'''
Count how many number chains beginning with n (where 0 < n < 10^D) end with a value 89.
<
# sum of the squared digits
def ssdigits: tostring | explode | map(. - 48 | .*.) | add;
Line 1,570 ⟶ 1,923:
| if $cache[$ss] then . + ($digits|combinations($Dfactorial))
else .
end) ;</
'''Part 3: D=8'''
<syntaxhighlight lang
{{out}}
<
85744333
Line 1,583 ⟶ 1,936:
# Using jq 1.4:
# user 0m3.942s
# sys 0m0.009s</
=={{header|Julia}}==
{{works with|Julia|0.6}}
'''Brute force solution''':
<
while m != 1 && m != 89
s = 0
Line 1,599 ⟶ 1,952:
return m
end
itercount(k::Integer) = count(x -> iterate(x) == 89, 1:k)</
'''More clever solution''':
<
function itercountcombos(ndigits::Integer)
cnt = 0
Line 1,629 ⟶ 1,982:
end
return cnt
end</
'''Benchmarks'''
<
@time itercountcombos(8)
@time itercountcombos(17)</
{{out}}
<pre> 8.866063 seconds (4.32 k allocations: 232.908 KiB)
Line 1,642 ⟶ 1,995:
=={{header|Kotlin}}==
{{trans|FreeBASIC}}
<
fun endsWith89(n: Int): Boolean {
Line 1,677 ⟶ 2,030:
if (endsWith89(i)) count89 += sums[i]
println("There are $count89 numbers from 1 to 100 million ending with 89")
}</
{{out}}
Line 1,685 ⟶ 2,038:
=={{header|Lua}}==
<
for i = 0, 9 do
Line 1,731 ⟶ 2,084:
end
print(counter)</
{{out}}
<pre>85744333</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
stopValues = Join[{1}, NestList[sumDigitsSquared, 89, 7]];
iterate[n_Integer] :=
Line 1,772 ⟶ 2,125:
b}, {_?(MemberQ[iteratesToOne, #] &), _}][[All, 2]]];
(10^numberOfDigits - 1) - onesCount</
{{out}}<pre>85744333</pre>
Line 1,781 ⟶ 2,134:
We provide the result for 8 digits and also for 50 digits. The result is obtained in 7 ms.
<
iterator digits(n: int): int =
Line 1,825 ⟶ 2,178:
echo "For 8 digits: ", chainsEndingWith89(8)
echo "For 50 digits: ", chainsEndingWith89(15)</
{{out}}
Line 1,832 ⟶ 2,185:
=={{header|Oberon-2}}==
{{works with|oo2c Version 2}}
<
MODULE DigitsSquaring;
IMPORT
Line 1,867 ⟶ 2,220:
END DigitsSquaring.
</syntaxhighlight>
{{out}}
<pre>
Line 1,879 ⟶ 2,232:
=={{header|Objeck}}==
<
function : Main(args : String[]) ~ Nil {
Count89s(1000000)->PrintLine();
Line 1,922 ⟶ 2,275:
return sum;
}
}</
Output:
Line 1,934 ⟶ 2,287:
Brute force implementation
<
while (n 1 <> n 89 <> and ) [
0 while(n) [ n 10 /mod ->n dup * + ]
Line 1,940 ⟶ 2,293:
] n ;
: iterDigits | i | 0 100000000 loop: i [ i sq_digits 89 &= + ] . ;</
{{out}}
Line 1,948 ⟶ 2,301:
=={{header|PARI/GP}}==
<
happy(n)=while(n>6, n=ssd(n)); n==1;
ct(n)=my(f=n!,s=10^n-1,d); forvec(v=vector(9,i,[0,n]), d=vector(9,i, if(i>8,n,v[i+1])-v[i]); if(happy(sum(i=1,9,d[i]*i^2)), s-=f/prod(i=1,9,d[i]!)/v[1]!), 1); s;
ct(8)</
{{out}}
<pre>%1 = 85744333</pre>
Line 1,968 ⟶ 2,321:
Tested with freepascal.
<
const
maxdigCnt = 14;
Line 2,104 ⟶ 2,457:
writeln('there are ',upperlimit-res,' 89s ');
end.
</
10e18
//658 small counts out of 1000000000
Line 2,124 ⟶ 2,477:
{{trans|Raku}}
<
use strict;
Line 2,147 ⟶ 2,500:
}
print $cnt;</
85744333
Line 2,153 ⟶ 2,506:
=={{header|Phix}}==
{{trans|C}}
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAXINT</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">machine_bits</span><span style="color: #0000FF;">()=</span><span style="color: #000000;">32</span><span style="color: #0000FF;">?</span><span style="color: #000000;">53</span><span style="color: #0000FF;">:</span><span style="color: #000000;">64</span><span style="color: #0000FF;">))</span>
Line 2,162 ⟶ 2,516:
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</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: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">*</span><span style="color: #000000;">j</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i1</span><span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i1ms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">s</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">
<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: #004080;">atom</span> <span style="color: #000000;">count89</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</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: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">81</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">digit</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">w</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">w</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
Line 2,178 ⟶ 2,532:
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">89</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count89</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">sums</span><span style="color: #0000FF;">[</span><span style="color: #000000;">
<span style="color: #008080;">if</span> <span style="color: #000000;">count89</span><span style="color: #0000FF;">></span><span style="color: #000000;">MAXINT</span> <span style="color: #008080;">then</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;">"counter overflow for 10^%d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 2,195 ⟶ 2,549:
<span style="color: #000000;">main</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<!--</
{{out}}
on 32 bit:
Line 2,230 ⟶ 2,584:
I realised I needed to do this in two stages.<br>
Phase 1. Make sure we can count.
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">comb</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">set</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">at</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">={})</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">digits</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</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;">chosen</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">idx</span><span style="color: #0000FF;">]+=</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">chosen</span><span style="color: #0000FF;">))</span>
Line 2,256 ⟶ 2,612:
<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;">"%V\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">comb</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">},</span><span style="color: #000000;">nums</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</
Starting with the combinations method from http://rosettacode.org/wiki/Combinations_with_repetitions#Phix converted to a function, make sure we
are covering all the numbers correctly by checking that we have indeed found power(10,n) of them, and show we are looking at significantly fewer combinations.
Line 2,272 ⟶ 2,628:
Phase 2. Add in the rest of the logic, as suggested count 1's in preference to 89's and subtract from 10^n to get the answer.<br>
[PS There is an eerie similarity between this and the 2nd C version, but I swear it is not a copy, and I noticed that later.]
<!--<syntaxhighlight lang
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">is1</span>
Line 2,282 ⟶ 2,639:
<span style="color: #004080;">integer</span> <span style="color: #000000;">ci</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chosen</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">sumsq</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">ci</span><span style="color: #0000FF;">*</span><span style="color: #000000;">ci</span>
<span style="color: #000000;">
<span style="color: #000000;">digits</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ci</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sumsq</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">is1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">sumsq</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
Line 2,332 ⟶ 2,690:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t00</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
Sadly, while still very much faster than brute force, several times slower than the translated from C version.
Line 2,357 ⟶ 2,715:
=={{header|PicoLisp}}==
Brute force with caching
<
(de 1or89 (N)
Line 2,365 ⟶ 2,723:
(prog1
(1or89 N)
(idx '*Idx1or89 (cons N @) T) ) ) ) )</
Test:
<
(for I 100000000
(and (=1 (1or89 I)) (inc 'Ones)) )
(println (- 100000000 Ones)) )</
Output:
<pre>85744333</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="pl/i">
test: procedure options (main, reorder); /* 6 August 2015 */
Line 2,405 ⟶ 2,763:
end test;
</syntaxhighlight>
Output:
<pre>
Line 2,414 ⟶ 2,772:
=={{header|PureBasic}}==
{{Trans|C}}
<
Procedure is89(x)
Repeat
Line 2,451 ⟶ 2,809:
main()
Print("elapsed milliseconds= "+Str(ElapsedMilliseconds()-start))
Input()</
{{out}}
<pre>1->10^1 : 7
Line 2,475 ⟶ 2,833:
elapsed milliseconds= 9</pre>
{{Trans|C++}}
<
Procedure sum_square_digits(n)
num=n : sum=0
Line 2,505 ⟶ 2,863:
main()
Print("elapsed milliseconds: "+Str(ElapsedMilliseconds()-start))
Input()</
{{out}}
<pre>85744333
Line 2,514 ⟶ 2,872:
====Translation of D====
{{trans|D}}
<
def next_step(x):
Line 2,569 ⟶ 2,927:
print result
main()</
{{out}}
85744333
Line 2,575 ⟶ 2,933:
====Translation of Ruby====
{{trans|Ruby}}
<syntaxhighlight lang="python">
from itertools import combinations_with_replacement
from array import array
Line 2,618 ⟶ 2,976:
print "\nD==" + str(D) + "\n " + str(z) + " numbers produce 1 and " + str(10**D-z) + " numbers produce 89"
print "Time ~= " + str(ee) + " secs"
</syntaxhighlight>
{{out}}
<pre>
Line 2,639 ⟶ 2,997:
===Python: Simple caching===
<
>>> @lru_cache(maxsize=1024)
def ids(n):
Line 2,652 ⟶ 3,010:
>>> sum(ids(x) == 89 for x in range(1, 100000000))
85744333
>>> </
This took a much longer time, in the order of hours.
Line 2,658 ⟶ 3,016:
===Python: Enhanced caching===
Notes that the order of digits in a number does not affect the final result so caches the digits of the number in sorted order for more hits.
<
>>> @lru_cache(maxsize=1024)
def _ids(nt):
Line 2,676 ⟶ 3,034:
>>> _ids.cache_info()
CacheInfo(hits=99991418, misses=5867462, maxsize=1024, currsize=1024)
>>> </
This took tens of minutes to run.
Line 2,682 ⟶ 3,040:
===Count digit sums===
If we always count up to powers of 10, it's faster to just record how many different numbers have the same digit square sum. The <code>check89()</code> function is pretty simple-minded, because it doesn't need to be fancy here.
<
from itertools import count
Line 2,701 ⟶ 3,059:
x = sum(a[i] for i in range(len(a)) if is89[i])
print("10^%d" % n, x)</
=={{header|QBasic}}==
{{works with|QBasic}}
{{works with|QuickBasic}}
{{trans|BBC BASIC}}
<syntaxhighlight lang="qbasic">REM Version 1: Brute force
T = TIMER
n1 = 0
FOR i = 1 TO 10000000
j = i
DO
k = 0
DO
k = INT(k + (j MOD 10) ^ 2)
j = INT(j / 10)
LOOP WHILE j <> 0
j = k
LOOP UNTIL j = 89 OR j = 1
IF j > 1 THEN n1 = n1 + 1
NEXT i
PRINT USING "Version 1: ####### in ##.### seconds."; n1; (TIMER - T)
END</syntaxhighlight>
=={{header|Quackery}}==
<
[ base share /mod
dup *
Line 2,720 ⟶ 3,102:
[ i^ 1+ chainends
89 = + ]
echo</
{{out}}
Line 2,730 ⟶ 3,112:
This contains two versions (in one go). The naive version which can (and should, probably) be used for investigating a single number. The second version can count the IDSes leading to 89 for powers of 10.
<
;; Tim-brown 2014-09-11
Line 2,825 ⟶ 3,207:
(length (all-digit-lists 3)) => 220
(count-89s-in-100... 1000000) => 856929]
}</
{{out}}
Line 2,851 ⟶ 3,233:
This fairly abstract version does caching and filtering to reduce the number of values it needs to check and moves calculations out of the hot loop, but is still interminably slow... even for just up to 1,000,000.
<syntaxhighlight lang="raku"
my $cnt = 0;
Line 2,864 ⟶ 3,246:
}
say $cnt;</
{{out}}
<pre>856929</pre>
All is not lost, however. Through the use of gradual typing, Raku scales down as well as up, so this jit-friendly version is performant enough to brute force the larger calculation:
<syntaxhighlight lang="raku"
@cache[1] = 1;
@cache[89] = 89;
Line 2,900 ⟶ 3,282:
$cnt = $cnt + 1 if Euler92($n) == 89;
}
say $cnt;</
{{out}}
<pre>85744333</pre>
Line 2,907 ⟶ 3,289:
The biggest gains are often from choosing the right algorithm.
<syntaxhighlight lang="raku"
my $digit;
my $sum = 0;
Line 2,939 ⟶ 3,321:
my $ends-with-one = sum flat @sums[(1 .. $k*81).grep: { endsWithOne($_) }], +endsWithOne(10**$k);
say 10**$k - $ends-with-one;</
{{out}}
Line 2,945 ⟶ 3,327:
=={{header|REXX}}==
{Both REXX versions don't depend on a specific
===with memoization===
<
parse arg n . /*obtain optional arguments from the CL*/
if n=='' | n=="," then n=10 * 1000000 /*Not specified? Then use the default.*/
!.=0; do m=1 for 9; !.m=m**2; end /*m*/ /*build a
a.=.; #.=!. /*intermediate counts of some numbers. */
do j=1 for n; x=j /* [
do q=1 until s==89 | s==1; s=0 /*add sum of the squared decimal digits*/
do until x=='' /*process each of the dec. digits in X.*/
parse var x _ +1 x; s=s + !._ /*get a digit; sum the fast square, */
end /*until x ··· */ /* [
z.q=s /*assign sum to a temporary auxiliary. */
if a.s\==. then do; s=a.s; leave; end /*Found a previous sum? Then use that.*/
x=s /*substitute the sum for the "new" X. */
end /*q*/ /* [
do f=1 for q; _=a.f; a._=s /*use the auxiliary arrays (for lookup)*/
end /*f*/
Line 2,968 ⟶ 3,350:
do k=1 by 88 for 2; @k=right('"'k'"', 5) /*display two results; define a literal*/
say 'count of' @k " chains for all natural numbers up to " n ' is:' #.k
end /*k*/ /*stick a fork in it, we're all done. */</
{{out|output|text= when using the default input:}}
<br>(ten million)
Line 2,978 ⟶ 3,360:
===process in chunks===
This version is about <big> 2½ </big> times faster than the previous REXX version.
<
parse arg n . /*obtain optional arguments from the CL*/
if n=='' | n=="," then n=10 * 1000000 /*Not specified? Then use the default.*/
!.=0; do m=1 for 9; !.m=m**2; end /*m*/ /*build a
$.=.; $.0=0; $.00=0; $.000=0; $.0000=0; @.=$. /*short-cuts for sub-group summations. */
#.=0 /*count of 1 and 89 results so far.*/
do j=1 for n; s=sumDs(j) /* [
#.s=#.s + 1 /*bump the counter for 1's or 89's. */
end /*j*/
Line 2,992 ⟶ 3,374:
end /*k*/ /*stick a fork in it, we're all done. */
exit /*stick a fork in it, we're all done. */
/*--------------------------------------------------------------------------------------*/
sumDs: parse arg z; chunk=3 /*obtain the number (for adding digits)*/
p=0 /*set partial sum of the decimal digits*/
do m=1 by chunk to length(z) /*process the number, in chunks of four*/
y=substr(z, m, chunk) /*extract a
if @.y==. then do; oy=y; a=0 /*Not done before? Then sum the number*/
do until y=='' /*process each of the dec. digits in Y.*/
parse var y _ +1 y /*obtain a decimal digit; add it to A.*/
a=a + !._ /*obtain a decimal digit; add it to A.*/
end /*until y ···*/ /* [
@.oy=a /*mark original Y as being summed. */
end
else a=@.y /*use the
p=p + a /*add all the parts of number together.*/
end /*m*/
Line 3,013 ⟶ 3,395:
do until y=='' /*process each decimal digits in X.*/
parse var y _ +1 y; s=s + !._ /*get a dec. digit; sum the fast square*/
end /*until y ···*/ /* [
y=s /*substitute the sum for a "new" X. */
end /*until s ···*/ /* [
$.p=s /*use this for memoization for the sum.*/
return s</
{{out|output|text= when using the input of: <tt> 100000000 </tt>}}
<br>(one hundred million)
Line 3,026 ⟶ 3,408:
=={{header|Ring}}==
<
nr = 1000
num = 0
Line 3,037 ⟶ 3,419:
next
see "Total under 1000 is : " + num + nl
</syntaxhighlight>
Output:
<pre>
Line 3,081 ⟶ 3,463:
Total under 1000 is : 41
</pre>
=={{header|RPL}}==
{{trans|C}}
The <code>IS89?</code> subroutine handles unsigned integers rather than floating point numbers: it is a little bit longer, but rounding errors are then avoided.
{{works with|Halcyon Calc|4.2.9}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪ { # 1d # 89d } → goal
≪ R→B '''DO'''
0 SWAP
'''WHILE''' DUP # 0d ≠ '''REPEAT'''
DUP 10 / SWAP OVER 10 * -
DUP * ROT + SWAP
'''END''' DROP
'''UNTIL''' goal OVER POS '''END'''
# 89d ==
≫ ≫ '<span style="color:blue">IS89?</span>' STO
≪ → ndig
≪ { } ndig 81 * 1 + + 0 CON 1 1 PUT '<span style="color:green">SUMS</span>' STO
1 ndig '''FOR''' n
n 81 * 1 '''FOR''' ii
1 9 '''FOR''' j
j SQ
'''IF''' DUP ii > '''THEN''' DROP 9 'j' STO
'''ELSE'''
<span style="color:green">SUMS</span> ii 1 + GET LAST 4 ROLL - GET +
'<span style="color:green">SUMS</span>' ii 1 + ROT PUT
'''END'''
'''NEXT''' -1 '''STEP NEXT'''
0
2 <span style="color:green">SUMS</span> SIZE 1 GET '''FOR''' j
'''IF''' j 1 - <span style="color:blue">IS89?</span> '''THEN''' SUMS j GET + '''END NEXT'''
≫ ≫ '<span style="color:blue">CNT89</span>' STO
|
<span style="color:blue">IS89?</span> ''( x → boolean )''
convert to integer and loop
s = 0
while x ≠ 0
get last digit
square it and add it to s
clean stack
until x = 1 or x = 89
return boolean
<span style="color:blue">CNT89</span> ''( nb_digits → count )''
sums[32*81 + 1] = {1, 0};
for (int n = 1; ; n++) {
for (int i = n*81; i; i--) {
for (int j = 1; j < 10; j++) {
int s = j*j;
if (s > i) break;
sums[i+1] += sums[i-s+1];
count89 = 0;
for (int j = 1; j < n*81 + 1; j++) {
if (!js89(i)) continue; count89 += sums[j+1];
}
|}
8 <span style="color:blue">CNT89</span>
{{out}}
<pre>
1: 85744333
</pre>
Runs in 49 seconds on a iPhone Xr. A basic HP-28 needs 930 seconds for <code>3 CNT89</code>, giving 85, whilst the emulator needs only 5 seconds, meaning that the 8 digits would probably need 2 h 30 on the HP-28.
=={{header|Ruby}}==
<
def iterated_square_digit(d)
f = Array.new(d+1){|n| (1..n).inject(1, :*)} #Some small factorials
g = -> (n) { res =
#An array: table[n]==0 means that n translates to 89 and 1 means that n translates to 1
Line 3,112 ⟶ 3,561:
iterated_square_digit(d)
puts " #{Time.now - t0} sec"
end</
{{out}}
Line 3,139 ⟶ 3,588:
'''Naive Recursion'''
<
let mut sum = 0;
while num != 0 {
Line 3,158 ⟶ 3,607:
let count = (1..100_000_000).filter(|&n| last_in_chain(n) == 89).count();
println!("{}", count);
}</
{{out}}
<pre>85744333</pre>
Line 3,164 ⟶ 3,613:
'''With precomputation'''
<
let mut sum = 0;
while num != 0 {
Line 3,185 ⟶ 3,634:
let count = (1..100_000_000).filter(|&n| prec[dig_sq_sum(n)] == 89).count();
println!("{}", count);
}</
Runtime: 1.7s on a 2500k @ 4Ghz
{{out}}
Line 3,193 ⟶ 3,642:
===Naïve Version, conventional iteration and (tail) recursive in one===
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/3XRtgEE/0 ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/6HeszTpxTXOqvrytzShUzg Scastie (remote JVM)] to compare the run times.
<
object Euler92 extends App {
Line 3,235 ⟶ 3,684:
println(s"Runtime recursive loop. [total ${compat.Platform.currentTime - executionStart0} ms]")
}</
=={{header|Sidef}}==
<
if ((n == 1) || (n == 89)) {
Line 3,247 ⟶ 3,696:
}
say (1..1e6 -> count_by { digit_square_sum_iter(_) == 89 })</
{{out}}
<pre>
Line 3,259 ⟶ 3,708:
With nth power support.
<
func is89(_ n: Int) -> Bool {
Line 3,311 ⟶ 3,760:
}
iterSquare(upToPower: 8)</
{{out}}
Line 3,326 ⟶ 3,775:
All three versions below produce identical output (<tt>85744333</tt>), but the third is fastest and the first is the slowest, both by substantial margins.
===''Very'' Naïve Version===
<
while {$n != 1 && $n != 89} {
set n [tcl::mathop::+ {*}[lmap x [split $n ""] {expr {$x**2}}]]
Line 3,335 ⟶ 3,784:
incr count [expr {[ids $i] == 89}]
}
puts $count</
===Intelligent Version===
Conversion back and forth between numbers and strings is slow. Using math operations directly is much faster (around 4 times in informal testing).
<
while {$n != 1 && $n != 89} {
for {set m 0} {$n} {set n [expr {$n / 10}]} {
Line 3,350 ⟶ 3,799:
incr count [expr {[ids $i] == 89}]
}
puts $count</
===Substantially More Intelligent Version===
Using the observation that the maximum value after 1 step is obtained for <tt>999999999</tt>, which is <math>9^3=729</math>. Thus, running one step of the reduction and then using a lookup table (which we can construct quickly at the start of the run, and which has excellent performance) is much faster overall, approximately 3–4 times than the second version above (and over 12 times faster than the first version).
<!-- It takes about 200 seconds on my machine, but I can't compare with anyone else's system… -->
:Donald, you have 1 too many 9's the value after step 1 is 81*8 = 648. Not that that is the problem here, you can not afford to go around this loop 100 million times. Notice that IDS[21] == IDS[12], IDS[123] == IDS[132] == IDS[213} ... etc, etc. The Ruby version takes about a tenth of a second.--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 12:47, 31 August 2014 (UTC)
<
proc ids n {
while {$n != 1 && $n != 89} {
Line 3,386 ⟶ 3,835:
}
puts $count
}}</
=={{header|VBScript}}==
<syntaxhighlight lang="vb">
start_time = Now
cnt = 0
Line 3,410 ⟶ 3,859:
WScript.Echo "Elapse Time: " & DateDiff("s",start_time,end_time) &_
vbCrLf & "Count: " & cnt
</syntaxhighlight>
{{Out}}
Line 3,421 ⟶ 3,870:
=={{header|Wren}}==
{{trans|FreeBASIC}}
<
var digit = 0
var sum = 0
Line 3,458 ⟶ 3,907:
}
}
System.print("Took %(((System.clock - start)*1000).round) milliseconds.")</
{{out}}
Line 3,469 ⟶ 3,918:
=={{header|X86 Assembly}}==
{{works with|nasm}}
<
section .data
count dd 0
Line 3,522 ⟶ 3,971:
mov eax, 0
ret
</syntaxhighlight>
=={{header|XPL0}}==
Simple minded brute force takes 30 seconds on Pi4.
<syntaxhighlight lang "XPL0">int C, N, M, S;
[C:= 0;
for N:= 1 to 100_000_000-1 do
[M:= N;
loop [S:= 0;
repeat M:= M/10;
S:= S + rem(0)*rem(0);
until M = 0;
if S = 89 then
[C:= C+1; quit];
if S = 1 then quit;
M:= S;
];
];
IntOut(0, C);
]</syntaxhighlight>
{{out}}
<pre>
85744333</pre>
=={{header|zkl}}==
Line 3,529 ⟶ 4,000:
{{trans|D}}
{{trans|http://www.mathblog.dk/project-euler-92-square-digits-number-chain/}}
<
candidate:=number.reduce(fcn(sum,n){ sum*10 + n },0); // digits to int
Line 3,560 ⟶ 4,031:
}
}
println(result);</
{{out}}
<pre>85744333</pre>
Line 3,567 ⟶ 4,038:
{{trans|BBC_BASIC}}
Very, very slow. Use a ZX Spectrum emulator and run with maximum speed option enabled.
<
20 FOR i=1 TO 1000
30 LET j=i
Line 3,580 ⟶ 4,051:
110 NEXT i
120 PRINT "Version 1: ";n
200 DEF FN m(a,b)=a-INT (a/b)*b: REM modulo</
{{out}}
<pre>Version 1: 857</pre>
| |||