Iterated digits squaring: Difference between revisions

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)]

 

 

* [[Digital root]]

* [[Digital root/Multiplicative digital root]]

<br><br>

 

=={{header|ALGOL 68}}==

Brute-force with some caching.

 

# compute a table of the sum of the squared digits of the numbers 00 to 99 #

OD;

 

{{out}}

<pre>

Number of values whose squared digit sum is 89: 85744333

</pre>

 

{{works with|BBC BASIC for Windows}}

Three versions timed on a 2.50GHz Intel Desktop.

REM ---------------------------------------------------------

T%=TIME

PRINT "Version 3: ";N% " in ";(TIME-T%)/100 " seconds."

 

{{out}}

<pre>

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²^²). 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>-!>#^_

 

{{out}}

 

<pre>1..100000000 => 85744333</pre>

 

=={{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;

 

return 0;

{{out}}

<pre>

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

#include <stdio.h>

 

return 0;

}

{{out}}

<pre>85744333</pre>

 

=={{header|C++}}==

Slow (~10 seconds on my machine) brute force C++ implementation:

#include <iostream>

 

return 0;

}

{{out}}

<pre>85744333</pre>

 

=={{header|Ceylon}}==

function digitsSquaredSum(variable Integer n) {

}

print(eightyNines);

 

=={{header|Clojure}}==

===Direct Method===

(:require [clojure.math.numeric-tower :as math])

(:use [criterium.core])

 

(time (println (direct-method 8)))

{{Output}}

<pre>

</pre>

===Using Combinations===

(def DIGITS (range 0 10))

 

(println (itertools-comb 8))

;; Time obtained using benchmark library (i.e. (bench (itertools-comb 8)) )

{{{Output}}

<pre>

both tested on i7 CPU 920@2.67GHZ)

</pre>

=={{header|Common Lisp}}==

(defun square (number)

(expt number 2))

(incf count))

:finally (return count)))

 

{{out}}

 

*

</pre>

 

=={{header|D}}==

A simple memoizing partially-imperative brute-force solution:

 

uint step(uint x) pure nothrow @safe @nogc {

void main() {

iota(1, 100_000_000).filter!(x => x.iterate == 89).count.writeln;

{{out}}

<pre>85744333</pre>

 

A fast imperative brute-force solution:

import core.stdc.stdio: printf;

 

 

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

 

printf("%u\n", result);

The output is the same.

The run-time is about 0.04 seconds or less.

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 {

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|ERRE}}==

PROGRAM ITERATION

 

PRINT

END PROGRAM

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.

prettyprint sequences tools.time ;

IN: rosetta-code.iterated-digits-squaring

] loop

drop .

{{out}}

<pre>

85744333

Running time: 55.76544594 seconds

</pre>

 

=={{header|FreeBASIC}}==

 

' similar to C Language (first approach)

Print

Print "Press any key to quit"

 

{{out}}

 

=={{header|Frink}}==

total = 0

d = new dict

 

println[total]

 

{{out}}

85744333

</pre>

 

=={{header|Go}}==

It's basic. Runs in about 30 seconds on an old laptop.

 

 

import (

}

fmt.Println(u89)

{{out}}

<pre>

=={{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)

 

 

main = do

{{out}}

<pre>85744333</pre>

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.

 

 

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:

 

 

So we could write a routine which works for the intended range, and stops after the first iteration:

 

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.

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:

 

 

Of course, there are faster ways of obtaining that result. The fastest is probably this:

 

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.

 

=={{header|Java}}==

{{works with|Java|8}}

 

public class IteratedDigitsSquaring {

return n;

}

 

<pre>85744333</pre>

 

'''Part 1: Foundations'''

 

# Pick n items (with replacement) from the input array,

else . + [[$item, 1]]

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;

| if $cache[$ss] then . + ($digits|combinations($Dfactorial))

else .

'''Part 3: D=8'''

{{out}}

85744333

 

# Using jq 1.4:

# user 0m3.942s

 

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

fun endsWith89(n: Int): Boolean {

if (endsWith89(i)) count89 += sums[i]

println("There are $count89 numbers from 1 to 100 million ending with 89")

 

{{out}}

 

=={{header|Lua}}==

 

for i = 0, 9 do

end

 

{{out}}

<pre>85744333</pre>

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

stopValues = Join[{1}, NestList[sumDigitsSquared, 89, 7]];

iterate[n_Integer] :=

b}, {_?(MemberQ[iteratesToOne, #] &), _}][[All, 2]]];

 

 

{{out}}<pre>85744333</pre>

 

=={{header|Oberon-2}}==

MODULE DigitsSquaring;

IMPORT

END DigitsSquaring.

 

{{out}}

<pre>

sys 0m0.001s

 

</pre>

 

Brute force implementation

 

while (n 1 <> n 89 <> and ) [

0 while(n) [ n 10 /mod ->n dup * + ]

] n ;

 

 

{{out}}

 

=={{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;

{{out}}

<pre>%1 = 85744333</pre>

 

Tested with freepascal.

const

maxdigCnt = 14;

writeln('there are ',upperlimit-res,' 89s ');

end.

10e18

//658 small counts out of 1000000000

 

=={{header|Perl}}==

 

use strict;

 

}

 

85744333

 

=={{header|Phix}}==

{{trans|C}}

{{out}}

on 32 bit:

I realised I needed to do this in two stages.<br>

Phase 1. Make sure we can count.

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.

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

{{out}}

Sadly, while still very much faster than brute force, several times slower than the translated from C version.

There are 80 numbers from 1 to 10^2 ending with 89 (0.00s)

There are 857 numbers from 1 to 10^3 ending with 89 (0.00s)

There are 8581146 numbers from 1 to 10^7 ending with 89 (0.02s)

</pre>

 

=={{header|PicoLisp}}==

Brute force with caching

 

(de 1or89 (N)

(prog1

(1or89 N)

Test:

(for I 100000000

(and (=1 (1or89 I)) (inc 'Ones)) )

Output:

<pre>85744333</pre>

 

=={{header|PL/I}}==

test: procedure options (main, reorder); /* 6 August 2015 */

 

 

end test;

Output:

<pre>

=={{header|PureBasic}}==

{{Trans|C}}

Procedure is89(x)

Repeat

main()

Print("elapsed milliseconds= "+Str(ElapsedMilliseconds()-start))

{{out}}

<pre>1->10^1 : 7

elapsed milliseconds= 9</pre>

{{Trans|C++}}

Procedure sum_square_digits(n)

num=n : sum=0

main()

Print("elapsed milliseconds: "+Str(ElapsedMilliseconds()-start))

{{out}}

<pre>85744333

====Translation of D====

{{trans|D}}

 

def next_step(x):

print result

 

{{out}}

85744333

====Translation of Ruby====

{{trans|Ruby}}

from itertools import combinations_with_replacement

from array import array

print "\nD==" + str(D) + "\n " + str(z) + " numbers produce 1 and " + str(10**D-z) + " numbers produce 89"

print "Time ~= " + str(ee) + " secs"

{{out}}

<pre>

 

===Python: Simple caching===

>>> @lru_cache(maxsize=1024)

def ids(n):

>>> sum(ids(x) == 89 for x in range(1, 100000000))

85744333

 

This took a much longer time, in the order of hours.

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

>>> _ids.cache_info()

CacheInfo(hits=99991418, misses=5867462, maxsize=1024, currsize=1024)

 

This took tens of minutes to run.

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

 

 

x = sum(a[i] for i in range(len(a)) if is89[i])

 

=={{header|Racket}}==

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

 

(length (all-digit-lists 3)) => 220

(count-89s-in-100... 1000000) => 856929]

 

{{out}}

 

Ok, so maybe 131 seconds is not so flattering -- but I have not memoised or anything fancy like that, because even doing that isn't going to come anywhere near competing with 44ms.

 

=={{header|REXX}}==

===with memoization===

parse arg n . /*obtain optional arguments from the CL*/

if n=='' | n=="," then n=10 * 1000000 /*Not specified? Then use the default.*/

a.=.; #.=!. /*intermediate counts of some numbers. */

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, */

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. */

do f=1 for q; _=a.f; a._=s /*use the auxiliary arrays (for lookup)*/

end /*f*/

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

{{out|output|text=&nbsp; when using the default input:}}

<br>(ten million)

===process in chunks===

This version is about &nbsp; <big> 2½ </big> &nbsp; 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=0; $.00=0; $.000=0; $.0000=0; @.=$. /*short-cuts for sub-group summations. */

#.=0 /*count of 1 and 89 results so far.*/

#.s=#.s + 1 /*bump the counter for 1's or 89's. */

end /*j*/

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*/

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.*/

@.oy=a /*mark original Y as being summed. */

end

p=p + a /*add all the parts of number together.*/

end /*m*/

do until y=='' /*process each decimal digits in X.*/

parse var y _ +1 y; s=s + !._ /*get a dec. digit; sum the fast square*/

y=s /*substitute the sum for a "new" X. */

$.p=s /*use this for memoization for the sum.*/

{{out|output|text=&nbsp; when using the input of: &nbsp; <tt> 100000000 </tt>}}

<br>(one hundred million)

 

=={{header|Ring}}==

nr = 1000

num = 0

next

see "Total under 1000 is : " + num + nl

Output:

<pre>

Total under 1000 is : 41

</pre>

 

=={{header|Ruby}}==

def iterated_square_digit(d)

f = Array.new(d+1){|n| (1..n).inject(1, :*)} #Some small factorials

#An array: table[n]==0 means that n translates to 89 and 1 means that n translates to 1

iterated_square_digit(d)

puts " #{Time.now - t0} sec"

 

{{out}}

24.337392 sec

</pre>

 

=={{header|Rust}}==

 

'''Naive Recursion'''

let mut sum = 0;

while num != 0 {

let count = (1..100_000_000).filter(|&n| last_in_chain(n) == 89).count();

println!("{}", count);

{{out}}

<pre>85744333</pre>

 

'''With precomputation'''

let mut sum = 0;

while num != 0 {

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

===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 {

println(s"Runtime recursive loop. [total ${compat.Platform.currentTime - executionStart0} ms]")

 

 

=={{header|Swift}}==

With nth power support.

 

 

func is89(_ n: Int) -> Bool {

}

 

 

{{out}}

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}}]]

incr count [expr {[ids $i] == 89}]

}

===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}]} {

incr count [expr {[ids $i] == 89}]

}

===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} {

}

puts $count

 

=={{header|VBScript}}==

start_time = Now

cnt = 0

WScript.Echo "Elapse Time: " & DateDiff("s",start_time,end_time) &_

vbCrLf & "Count: " & cnt

 

{{Out}}

Count: 85744333

</pre>

 

=={{header|zkl}}==

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

 

}

}

{{out}}

<pre>85744333</pre>

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

110 NEXT i

120 PRINT "Version 1: ";n

{{out}}

<pre>Version 1: 857</pre>