Compute the Digit Difference Sum of a Number

Question

Consider taking some non-negative integer such as 8675309 and computing the absolute values of the differences between all the pairs of neighboring digits.

For 8675309 we get |8-6| = 2, |6-7| = 1, |7-5| = 2, |5-3| = 2, |3-0| = 3, |0-9| = 9. Stringing these results together yields another, smaller non-negative integer: 212239. Repeating the process gives 11016, then 0115, which by the convention that leading zeros are not written simplifies as 115, which becomes 04 or 4, which can't be reduced any further. Summing all these values up we get 8675309 + 212239 + 11016 + 115 + 4 = 8898683.

Let's define the Digit Difference Sum (or DDS) as this operation of repeatedly taking the digit differences of a number to form a new number, then adding all the resulting numbers to the original.

Here are the first 20 values in the corresponding DDS sequence:

N   DDS(N)
0   0
1   1
2   2
3   3
4   4
5   5
6   6
7   7
8   8
9   9
10  11
11  11
12  13
13  15
14  17
15  19
16  21
17  23
18  25
19  27

Here are the first 10000 values, the graph for which is quite curious:

Especially since it looks the same when you plot it to 1000 or even 100:

(I'd call it the dentist's staircase...)

Challenge

Write a program or function that takes in a non-negative integer and prints or returns its DDS value. For example, if the input was 8675309, the output should be 8898683.

The shortest code in bytes wins.

Answer 1

Pyth, 17

s.ui.aM-VJjNTtJTQ

Try it here or run the Test Suite

Explanation:

s.u            Q   # Cumulative reduce, i.e. getting the intermediate values of each reduce
                     step and returning them as a list, then sum the list
   i ... T         # Convert the resulting list of numbers into a base 10 number
   .aM             # Get the absolute value of each element of ...
      -VJjNTtJ     # Perform vector subtraction on the lists given by
        JjNT       # assign J the number we currently have converted to its base 10 digits
            tJ     # and J[1:]. e.x. for 123 we get J = [1,2,3] then we do
                   # zip(J,J[1:]) which gives [[1,2],[2,3]] then element wise subtract
                   # to get [-1, -1]

Answer 2

Python 2, 73

Luckily, I managed to avoid any string operations.

t=lambda n:n>9and abs(n%10-n/10%10)+10*t(n/10)
g=lambda n:n and n+g(t(n))

g is the function that computes the answer.

Answer 3

Matlab, 101 105 bytes

Thanks a lot to @beaker for his suggestion to use polyval instead if base2dec. That allowed me to

• save 4 bytes;
• greatly simplify the generalization to arbitrary base (see below) and save 22 bytes there; and most of all,
• helped me realize that the code for the general case was wrong (leading zeros were not being removed). The code and the graphs are correct now.

Code:

function y=f(y)
x=+num2str(y);while numel(x)>1
x=polyval(abs(diff(x)),10);y=y+x;x=+dec2base(x,10);end

Example:

>> f(8675309)
ans =
     8898683

Bonus: arbitrary base

A small generalization allows one to use an arbitrary number base, not necessarily decimal:

• Arbitrary base from 2 to 10, 108 104 bytes

  function y=f(y,b)
  x=+dec2base(y,b);while numel(x)>1
  x=polyval(abs(diff(x)),b);y=y+x;x=+dec2base(x,b);end
  

  The reason why this works only for base up to 10 is that Matlab's dec2base function uses digits 0, 1, ..., 9, A, B, ..., and there's a jump in character (ASCII) codes from 9 to A.

• Arbitrary base from 2 to 36, 124 146 bytes

  The jump from 9 to A referred to above needs special treatment. The maximum base is 36 as per Matlab's dec2base function.

  function y=f(y,b)
  x=+dec2base(y,b);x(x>57)=x(x>57)-7;while numel(x)>1
  x=abs(diff(x));x=x(find(x,1):end);y=y+polyval(x,b);end
  

This is how the dentist's staircases look for different bases:

Answer 4

CJam, 22 21 bytes

ri_{\s2ew::-:zsi_@+}h

Note that this program exits with an error, which is allowed by default.

With the Java interpreter, errors can be suppressed by closing STDERR. If you try this code online in the CJam interpreter, ignore all output before the last line.

Thanks to @Sp3000 for pointing out an error in the original revision.

Thanks to @MartinBüttner for golfing off 1 byte.

Example run

$ cjam digit-difference.cjam 2>&- <<< 8675309     
8898683

How it works

ri_   e# Read an integer (I) from STDIN and push a copy (A).
{     e# Do:
  \   e#   Swap I on top of A.
  s   e#   Cast I to string.
      e#   For example, 123 -> "123".
  2ew e#   Push the overlapping slices of length 2 (pair of adjacent digits).
  ::- e#   Replace each pair by its difference.
  :z  e#   Apply absolute value to each difference.
  si  e#   Cast to string, then to integer. This is the new I.
      e#   For example, [1 2 3] -> "123" -> 123.
  _   e#   Push a copy of I.
  @   e#   Rotate A on top of the copy of I.
  +   e#   Add I to A, updating A.
}h    e# While A is truthy, repeat the loop.

A will always be truthy when checked by h. However, once I is a single-digit integer, 2ew will fail with an error after consuming the array it was called on. This leaves only the desired result on the stack, which is printed before exiting.

Answer 5

Labyrinth, 176 134 127 119 103 97 88 82 79 76 72 bytes

Thanks to Sp3000 for saving 1 byte and paving the way for 2 more.

This could probably still be shortened, but hey, it beats Java Matlab Python...

?
_
)/:}+{:`};!
9       "
_ :}-"" :_10
;;{: `" "  :
  {  (_:/=%}
  0+;`"

Try it online.

This terminates with an error but the error message is written to STDERR (which is why you don't see it in TIO).

The implementation is fairly straight-forward. We add the current value to a running total. If the current value was greater than 9, we compute its base-10 digits (via repeated div-mod), and form a new number from the absolute differences. If we get to 9 or less, we print the running total.

The digits of the current number are collected on the auxiliary stack with the most significant digit on top.

Well, the fancy implementation of abs(...) I had here turned out to be ridiculously complicated compared to the new solution... I'll add an updated explanation when I'm done golfing this further.

Answer 6

Julia, 81 60 bytes

n->(s=n;while n>9 s+=n=int(join(abs(diff(["$n"...]))))end;s)

Ungolfed:

function f(n::Int)
    # Initialize a sum to the input
    s = n

    while n > 9
        # Get absolute values of the pairwise differences of the
        # digits of n, join as a string, convert it to an integer,
        # and reassign n
        n = int(join(abs(diff(["$n"...]))))

        # ["$n"...] actually splits n as a string into a vector
        # of its characters, but the difference between ASCII
        # codes is the same as the difference between the numbers
        # so it works as expected

        # Add the new n to the running sum
        s += n
    end

    # Return the sum
    return s
end

Try it online

Saved 21 bytes thanks to feersum and Glen O!

Answer 7

Java - 300 bytes

Golfed Version

static Long t=new Scanner(System.in).nextLong();static char[]c=t.toString().toCharArray();public static void main(String[]z){while(c.length>1)s();System.out.print(t);}static void s(){String s="";for(int i=0;i<c.length-1;)s+=Math.abs(c[i]-c[++i]);Long a=new Long(s);t+=a;c=a.toString().toCharArray();}

Ungolfed / Full version

import java.util.Scanner;

public class DigitDifference {

    static Long t = new Scanner(System.in).nextLong();
    static char[] c = t.toString().toCharArray();

    public static void main(String[] args){
        while( c.length > 1 )
            s();
        System.out.print(t);
    }

    static void s(){
        String s="";
        for(int i = 0; i < c.length-1;)
            s += Math.abs(c[i]-c[++i]);
        Long a = new Long(s);
        t += a;
        c = a.toString().toCharArray();
    }
}

Answer 8

oK, 37 32 24 23 bytes

+/(10/{%x*x}1_-':.:'$)\

In action:

  +/(10/{%x*x}1_-':.:'$)\8675309
8898683

  (+/(10/{%x*x}1_-':.:'$)\)'!20
0 1 2 3 4 5 6 7 8 9 11 11 13 15 17 19 21 23 25 27

K5 has a few features which are well suited to this- "encode" and "decode" can perform base conversion, each-pair (':) pairs up sequential elements in a list and fixed point scan (\) can produce the iterated sequence until it stops changing. The lack of a primitive abs() leads to some unsightly bulk in the form of {(x;-x)x<0}', though.

Edit:

Instead of {(x;-x)x<0}', I can (somewhat wastefully) take the square root of the square of the sequence ({%x*x}, saving 5 bytes.

Edit 2:

Inspired by @maurinus' APL solution, I can replace the "decode" (((#$x)#10)\x) with evaluating each character of the string representation of the number- .:'$x! This also lets me use a tacit form of the whole expression, saving additional characters.

Answer 9

Python 2, 87 bytes

f=lambda n:n and n+f(int('0'+''.join(`abs(int(a)-int(b))`for a,b in zip(`n`,`n`[1:]))))

Recursively adds the current number and takes the digits differences. Lots of converting between numbers and strings. Probably can be improved.

Answer 10

Julia, 55 48 bytes

h=n->(n>9&&h(int(join(abs(diff(["$n"...]))))))+n

Ungolfed:

function h(n)
  if n>9
    # If multiple digits, find the digit difference...
    digitdiff=int(join(abs(diff(["$n"...]))))
    # ... recurse the function...
    downsum=h(digitdiff)
    # ... and return the sum so far (working up from the bottom)
    return downsum+n
  else
    # If single digit, no further recursion, return the current number
    return n
  end
end

Essentially, this recurses down to the single-digit level (where no digit difference can be performed), then sums back up as it exits the recursion, level by level.

Answer 11

Haskell, 140 bytes

d does the job.

import Data.Char
d n=sum.m(read.m intToDigit).fst.span(/=[]).iterate s.m digitToInt.show$n
s l@(h:t)=snd$span(==0)$m abs$zipWith(-)l t
m=map

Does anyone know how to avoid importing the long conversion functions?

Answer 12

Mathematica, 72 69 65 bytes

Tr@FixedPointList[FromDigits@*Abs@*Differences@*IntegerDigits,#]&

I'm open to suggestions here.

Answer 13

K5, 50 bytes

+/{(r;x)@~r:.,/"0",{$(0;-r;r)@(~^r)+0<r:x-y}':$x}\

Answer 14

APL (22)

{⍵≤9:⍵⋄⍵+∇10⊥|2-/⍎¨⍕⍵}

Explanation:

• ⍵≤9:⍵: if ⍵ ≤ 9, return ⍵ unchanged.
• ⍎¨⍕⍵: convert ⍵ to a string, then evaluate each character
• 2-/: subtract every two adjacent numbers
• |: take the absolute values
• 10⊥: turn the array into a base-10 number
• ⍵+∇: call the function recursively with this new value, and add the result to the input

Answer 15

Python 3, 125 bytes

I used to like the shortness of regex until I tried to use it for this challenge...re.findall('\d\d',s,overlapped=True) is not on ;)

s=input()
p=int
x=p(s)
while p(s)>9:g=str(s);s=p(''.join(str(abs(p(g[i])-p(g[i+1])))for i in range(len(g)-1)));x+=s 
print(x)

Cheers @Todd :)

Answer 16

JavaScript ES6, 73 bytes

t=n=>(b=10,M=Math).ceil(n&&n+t((j=n=>n>9&&M.abs(n%b-n/b%b)+b*j(n/b))(n)))

This isn't getting any shorter :/ I'll try more approaches but this is the shortest one so far

Answer 17

JavaScript (ES6), 69

Test running the snippet below in an EcmaScript 6 compliant browser (but not Chrome as it still does not support the spread operator ...) MS Edge maybe?

f=n=>n&&(n+=r='',[...n].map(d=>(r+=d>p?d-p:p-d,p=d),p=n[0]),+n+f(+r))

function test()
{
  var i=+I.value
  O.innerHTML = i+' -> '+f(i) + '\n' + O.innerHTML 
}

<input id=I value=8675309><button onclick=test()>-></button>
<pre id=O></pre>

Alternative, using array comprehension that is now targeted EcmaScript 2016 (ES7), 67 bytes:

f=n=>n&&(n+=r='',p=n[0],[for(d of n)(r+=d>p?d-p:p-d,p=d)],+n+f(+r))

Answer 18

J, 70 bytes

 +/([:10&#.[:(2|@:-/\])[:10&(]#:~[#~[:>.[^.])])`]@.(11&>)^:a:".(1!:1)3

Answer 19

C 162 bytes

golfed:

main(int argc,char **argv){char *c=argv[1];int u=atoi(c),d;do{while(c[1]!=0){*c=abs(*c-*(c+1))+48;c++;}*c=0;c=argv[1];d=atoi(c);u+=d;}while(d>9);printf("%d",u);}

ungolfed:

main(int argc, char **argv)
{
    char *c=argv[1];
    int u=atoi(c),d;

    do
    {
        while(c[1]!=0)
        {
            *c=abs(*c-*(c+1))+48;
            c++;
        }

        *c=0;
        c=argv[1];
        d=atoi(c);
        u+=d;
    }
    while(d>9);

    printf("%d\n",u);
}

Answer 20

MATLAB (141)(137)

EDIT: 4 bytes less, thanks to @Andras

function[s j]=n(T,b,c),if(T/b>9),u=fix(T/10);[x e]=n(T,b*10,0);y=n(u,b,0);[w z]=n(u,b,c);s=abs(x-y);j=s+e+10*c*z;else,s=mod(T,10);j=s;end

• This doest beat @LuisMendo 's answer but atleast I could reduce execution time, which by, I would have just tried to diversify ways of tackling this problem.
• I could reduce it more but as I go for less time, i waste more bytes, so here is the principle:

The program is summing up digits of same row before inlined digits , it does mean it used integer division "n/10" log_10(n) times only, complexity is O(N).

If n= a b c d

a          b           c           d
   |a-b|       |b-c|       |c-d|
    ||a-b|-|b-c|| ||b-c|-|c-d||
   ....

My program calculates:

a+|a-b| + | |a-b|-|b-c| |  +  |  | |a-b|-|b-c| | - | |b-c|-|c-d| |  |
+10*(
b+|b-c| + | |b-c|-|c-d| |
+10*(
c+|c-d|
+10*(
d
)
)
)

Usage:

  [a b]=n(13652,1,1)

a =

1

 b =

   16098

Answer 21

R, 134 Bytes

Code

f=function(x){z=x;while(z>9){n=seq(nchar(z));z=abs(diff(strtoi(substring(z,n,n))));z=sum(z*10**(rev(seq(length(z)))-1));x=x+z};cat(k)}

Test it online.

Ungolfed

f=function(x){
  z=x;
  while(z>9){
    n=seq(nchar(z));
    z=abs(diff(strtoi(substring(z,n,n))));
    z=sum(z*10**(rev(seq(length(z)))-1));
    x=x+z
  };
  cat(x)
}

Here is the plot of the difference of the "Digit Difference Sum of a Number" series from f(1) to f(1m). Just because I love to diff.

Plot code

s <- seq(1,100000)
serie <- sapply(s,f)
plot(diff(ts(serie)),xlab="",ylab="")

Answer 22

Prolog, 143 bytes

Code:

q(X,N):-X<9,N=0;A is abs(X mod 10-X//10 mod 10),Y is X//10,q(Y,M),N is A+M*10.
r(X,N):-X<9,N=X;q(X,Y),r(Y,M),N is X+M.
p(X):-r(X,N),write(N).

Explained:

q(X,N):-X<9,N=0;                                                         % If only one digit, the difference is 0
        A is abs(X mod 10-X//10 mod 10),Y is X//10,q(Y,M),N is A+M*10.   % Else, the difference is the difference between the last 2 digits + the recursive difference of the number without the last digit
r(X,N):-X<9,N=X;                                                         % If we only have 1 digit the final answer is that digit
        q(X,Y),r(Y,M),N is X+M.                                          % Else, the final answer is the current number + the recursive difference of that number
p(X):-r(X,N),write(N).         

q does the calculations that convert a number into it's Digit Difference.
r recursively calls q and sums up the results to find the Digit Difference Sum.
p is the entry point. Takes a number, calls r and prints the answer.

Example:

>p(8675309).
8898683

Try it online here.

Answer 23

PHP - 198 bytes

<?$x=$t=$_GET['V'];function z($x){global$t;for($i=0;$i<strlen($x)-1;$i++){$z=str_split($x);$r.=str_replace('-','',$z[$i]-$z[$i+1]);}$r=ltrim($r,'0');$t+=$r;return strlen($r)>1?z($r):0;}z($x);echo$t;

Ungolfed

<?
$x=$t=$_GET['V']; // Gets the value from input
function z($x){
    global$t;
    for($i=0;$i<strlen($x)-1;$i++){
        $z=str_split($x); //Turns the string into an array
        $r.=str_replace('-','',$z[$i]-$z[$i+1]); // Sums the two values and removes the minus signal
    }
    $r=ltrim($r,'0'); // Remove trailing zeroes
    $t+=$r; // Adds to global var
    return strlen($r)>1?z($r):0; // Checks the size of the string. If >1, calls the function again
}

z($x);
echo$t;

Answer 24

Perl 6, 56 bytes

{[+] $_,{+.comb.rotor(2=>-1)».map((*-*).abs).join}…0} # 56 bytes

usage:

my &code = {...} # insert code from above

(180..190).map: &code;
# (259 258 259 260 261 262 263 264 265 266 280)

say code 8675309; # 8898683