# Compute the Digit Difference Sum of a Number

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.

• dentist's staircase? – Martijn Sep 20 '15 at 12:47
• @MartijnR Dentist's staircase. – Calvin's Hobbies Sep 20 '15 at 13:14
• @Calvin'sHobbies Orthodontist's staircase? – Beta Decay Sep 21 '15 at 16:03
• @BetaDecay Dentist's staircase. – Alex A. Sep 21 '15 at 17:08

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

• What language is this? So cryptic! T_T – asgs Nov 25 '15 at 11:45
• @asgs Welcome to PPCG :) It's called Pyth, you can find an interpreter and some documentation at its Github page. Most of the users of this language are active on this site, so if you have questions about it feel free to ask in chat or the room dedicated to it :) – FryAmTheEggman Nov 25 '15 at 18:46

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

• What is this black magic?! – Beta Decay Sep 20 '15 at 8:38
• @BetaDecay I believe it's called "math". – lirtosiast Sep 21 '15 at 5:23
• I don't know Python quite well enough to tell, but can you apply the remainder operation to both terms in one hit? That is, would (n-n/10)%10 operate the same as n%10-n/10%10? Or maybe even (9*n/10)%10? – Glen O Sep 21 '15 at 11:25
• @GlenO In Python, % is a true modulus operator, not a remainder, so that wouldn't work. – feersum Sep 21 '15 at 12:37

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

• This is what I would have done... time to think of another answer lol. +1. – rayryeng Sep 20 '15 at 21:43
• @rayryeng :-) Thanks – Luis Mendo Sep 20 '15 at 21:44
• @BetaDecay Thanks! :-) They're pretty indeed – Luis Mendo Sep 25 '15 at 20:52

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

$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. • Posted in 7 minutes flat :O – Calvin's Hobbies Sep 20 '15 at 5:21 # Labyrinth, 1761341271191039788827976 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. ## 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(); } }  • @Loovjo, Cheers.. – The Coder Sep 20 '15 at 13:32 • Welcome to PPCG! This can still be golfed a lot. I haven't looked at the logic much but: 1) Pull all of this into one function since you don't really need a separate one (or a full program/class for that matter) 2) Get rid of the statics after pulling them in 3) (a+"") is generally the same as a.toString(), but shorter 4) You don't need a Scanner if it's just a function, simply take a long as input. – Geobits Sep 22 '15 at 16:48 • For example, without changing much of the working, and just removing cruft, it's around 164: long f(long t){long a=t;char[]c;while((c=(a+"").toCharArray()).length>1){String s="";for(int i=0;i<c.length-1;)s+=Math.abs(c[i]-c[++i]);t+=a=new Long(s);}return t;}  – Geobits Sep 22 '15 at 16:59 • @Geobits, that was amazing buddy. I'm new to Code Golf, so I'll try to improve my codign efficiency. Cherrs.. – The Coder Sep 23 '15 at 4:57 # 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!

• Is there any reason ndigits(n)>1 is different than n>9 ? – feersum Sep 20 '15 at 8:18
• Suggestion: int(join(abs(diff(["$n"...])))) saves 9 bytes. Switch to n>9 as suggested by feersum for another 9 bytes saved. Save three more bytes by performing both assignments in the while loop in one step (and removing the extra, now unnecessary semicolon): n->(s=n;while n>9 s+=n=int(join(abs(diff(["$n"...]))))end;s) – Glen O Sep 20 '15 at 14:21
• @feersum Um, nope. Thanks! – Alex A. Sep 20 '15 at 20:14
• @GlenO Awesome, thanks! – Alex A. Sep 20 '15 at 20:16

# oK, 373224 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. ## 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. # 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. # 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? • intToDigit is toEnum.(+48) and digitToInt is (\i->fromEnum i-48). You can also turn s to a pointfree version with =<< in list context: s=snd.span(==0).m abs.(zipWith(-)=<<tail). Finally, (==0) is (<1), because we're working with non-negative integers. – nimi Sep 20 '15 at 16:01 • ... oh, and if s is pointfree, there's not need to give it a name. Call it directly: iterate(snd.span ... tail)) – nimi Sep 20 '15 at 16:08 • ... it's me again to correct a mistake in my first comment: =<< is used in function context, not list context, sorry. – nimi Sep 20 '15 at 16:34 • Brilliant! Also, is it common procedure here to use GHC extensions? NoMonomorphismRestriction will let me have d pointfree, too. – Leif Willerts Sep 20 '15 at 18:20 • chr and ord are both in Data.Char, so you can't omit the import. Compiler flags are counted as bytes, too, so NoMonomorphismRestriction increases your score by 25. – nimi Sep 20 '15 at 20:27 # K5, 50 bytes +/{(r;x)@~r:.,/"0",{$(0;-r;r)@(~^r)+0<r:x-y}':$x}\  # 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 # Mathematica, 7269 65 bytes Tr@FixedPointList[FromDigits@*Abs@*Differences@*IntegerDigits,#]&  I'm open to suggestions here. • Tr@FixedPointList[FromDigits@*Abs@*Differences@*IntegerDigits,#]& – alephalpha Nov 25 '15 at 3:09 • @alephalpha Interesting concept, creating extra zeroes... – LegionMammal978 Nov 25 '15 at 11:20 # 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 • If you just leave it as an anonymous function instead of assigning it to t it's still valid and saves you 2 bytes. – Patrick Roberts Sep 21 '15 at 14:04 • @PatrickRoberts yes but I'm using recursion so I need to name it – Downgoat Sep 21 '15 at 14:13 • Oh, missed that, fair enough. – Patrick Roberts Sep 21 '15 at 14:23 # 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))  # 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 :) • You can perform inplace addition on an integer rather than a list which will remove the need to square brackets and the final sum. 's=p(input())' will allow you the remove the int conversion on the while loop and assignment to x. Also consider looping through the zip of g and g[1:] which should save some bytes. – Todd Sep 21 '15 at 14:09 # J, 70 bytes  +/([:10&#.[:(2|@:-/\])[:10&(]#:~[#~[:>.[^.])])]@.(11&>)^:a:".(1!:1)3  # 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); }  # 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="")  ## 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  • You can spare 4 bytes by omitting the optional ,end of the function declaration. – Andras Deak Sep 24 '15 at 21:50 • Please consider revising the grammar of your post. I can't quite understand what you have said. – rayryeng Sep 24 '15 at 21:52 # 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. # 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;  ## 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