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

{{trans|Python}}

 

V result = 0

L x > 0

 

=={{header|Ada}}==

 

procedure Digits_Squaring is

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

Brute-force with some caching.

 

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

=={{header|Arturo}}==

{{trans|Nim}}

result: n

while [not? in? result [1 89]][

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

{{works with|BBC BASIC for Windows}}

Three versions timed on a 2.50GHz Intel Desktop.

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

T%=TIME

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

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

 

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.

 

d ? ט ?10 # Digit values

m ? 1+81×2??? # One plus maximum digit sum

}</syntaxhighlight>

 

+-

? 1 7

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

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

 

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

{

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

 

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

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

#include <iostream>

 

 

=={{header|Ceylon}}==

function digitsSquaredSum(variable Integer n) {

=={{header|Clojure}}==

===Direct Method===

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

(:use [criterium.core])

 

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

(defun square (number)

(expt number 2))

=={{header|D}}==

A simple memoizing partially-imperative brute-force solution:

 

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

 

A fast imperative brute-force solution:

import core.stdc.stdio: printf;

 

 

A more efficient solution:

 

enum factorial = (in uint n) pure nothrow @safe @nogc

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 {

 

=={{header|ERRE}}==

PROGRAM ITERATION

 

</pre>

=={{header|Forth}}==

Tested for VFX Forth and GForth in Linux

\ To explain the algorithm: Each iteration is performed in set-count-sumsq below.

 

=={{header|FreeBASIC}}==

 

' similar to C Language (first approach)

 

=={{header|Frink}}==

total = 0

d = new dict

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

 

 

import (

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

 

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 ? 145 ? 42 ? 20 ? 4 ? 16 ? 37 ? 58 ? 89, so it only ends with 1 or one of the numbers in this loop. 42 is of course far more significant and the one I would choose!!--[[User:Nigel Galloway|Nigel Galloway]] ([[User talk:Nigel Galloway|talk]]) 10:12, 16 September 2014 (UTC)

 

15 26 40 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</syntaxhighlight>

 

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

 

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

 

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

85744333</syntaxhighlight>

 

=={{header|Java}}==

{{works with|Java|8}}

 

public class IteratedDigitsSquaring {

 

'''Part 1: Foundations'''

 

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

 

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;

end) ;</syntaxhighlight>

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

{{out}}

85744333

 

{{works with|Julia|0.6}}

'''Brute force solution''':

while m != 1 && m != 89

s = 0

 

'''More clever solution''':

function itercountcombos(ndigits::Integer)

cnt = 0

 

'''Benchmarks'''

@time itercountcombos(8)

@time itercountcombos(17)</syntaxhighlight>

=={{header|Kotlin}}==

{{trans|FreeBASIC}}

 

fun endsWith89(n: Int): Boolean {

 

=={{header|Lua}}==

 

for i = 0, 9 do

 

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

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

iterate[n_Integer] :=

We provide the result for 8 digits and also for 50 digits. The result is obtained in 7 ms.

 

 

iterator digits(n: int): int =

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

{{works with|oo2c Version 2}}

MODULE DigitsSquaring;

IMPORT

 

=={{header|Objeck}}==

function : Main(args : String[]) ~ Nil {

Count89s(1000000)->PrintLine();

Brute force implementation

 

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

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

 

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

 

Tested with freepascal.

const

maxdigCnt = 14;

{{trans|Raku}}

 

use strict;

 

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

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>

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

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

=={{header|PicoLisp}}==

Brute force with caching

 

(de 1or89 (N)

(idx '*Idx1or89 (cons N @) T) ) ) ) )</syntaxhighlight>

Test:

(for I 100000000

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

 

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

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

 

=={{header|PureBasic}}==

{{Trans|C}}

Procedure is89(x)

Repeat

elapsed milliseconds= 9</pre>

{{Trans|C++}}

Procedure sum_square_digits(n)

num=n : sum=0

====Translation of D====

{{trans|D}}

 

def next_step(x):

====Translation of Ruby====

{{trans|Ruby}}

from itertools import combinations_with_replacement

from array import array

 

===Python: Simple caching===

>>> @lru_cache(maxsize=1024)

def ids(n):

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

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

 

{{works with|QuickBasic}}

{{trans|BBC BASIC}}

 

T = TIMER

=={{header|Quackery}}==

 

[ base share /mod

dup *

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

 

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.

 

my $cnt = 0;

 

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

@cache[1] = 1;

@cache[89] = 89;

The biggest gains are often from choosing the right algorithm.

 

my $digit;

my $sum = 0;

{Both REXX versions don't depend on a specific end-number.}

===with memoization===

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

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

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

 

=={{header|Ring}}==

nr = 1000

num = 0

 

=={{header|Ruby}}==

def iterated_square_digit(d)

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

 

'''Naive Recursion'''

let mut sum = 0;

while num != 0 {

 

'''With precomputation'''

let mut sum = 0;

while num != 0 {

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

 

=={{header|Sidef}}==

 

if ((n == 1) || (n == 89)) {

With nth power support.

 

 

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

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

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

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

 

=={{header|VBScript}}==

start_time = Now

cnt = 0

=={{header|Wren}}==

{{trans|FreeBASIC}}

var digit = 0

var sum = 0

=={{header|X86 Assembly}}==

{{works with|nasm}}

section .data

count dd 0

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

 

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