Fold the integer to save space!

Question

The crazy mathematician owns a wide collection of numbers, and therefore the space he has left is quite limited. To save some, he must fold his integers, but unfortunately he is really lazy. Your task, if you wish to help him, is to create a function / program that folds a given positive integer for our number maniac.

How to fold an integer?

If it is evenly divisible by the sum of its digits, divide it by the sum of its digits. If it doesn't meet that requirement, take its remainder when divided by the sum of its digits. Repeat the process until the result reaches 1. The folded integer is the number of operations you had to perform. Let's take an example (say 1782):

1. Get the sum of its digits: 1 +たす 7 +たす 8 +たす 2 =わ 18. 1782 is evenly divisible by 18, so the next number is 1782 / 18 = 99.

2. 99 is not evenly divisible by 9 + 9 = 18, hence we take the remainder: 99 % 18 = 9.

3. 9 is obviously divisible by 9, so we divide it and obtain 1.

The result is 3, because 3 operations were required in order to reach 1.

Rules and Specs

• Some integers might have the sum of digits equal to 1, such as 10 or 100. Your program doesn't need to handle such cases. That means, you will be guaranteed that the integer given as input doesn't have the sum of digits equal to 1, and no operation with the given integer will result in a number whose sum of digits is 1 (except for 1 itself, which is the "target"). For example, you will never receive 10 or 20 as input.

• The input will be a positive integer higher than 1.

• Default Loopholes apply.

• You can take input and provide output by any standard mean .

---

Test Cases

Input -> Output
2 -> 1
5 -> 1
9 -> 1
18 -> 2
72 -> 2
152790 -> 2
152 -> 3
666 -> 3
777 -> 3
2010 -> 3
898786854 -> 4

Here is a program that lets you visualize the process and try more test cases.

---

This is code-golf, so the shortest code in each language (scored in bytes) wins!

• Mr. Xcoder: Inspired by this challenge , although it might not seem related at first.
• Ray: This will work as a stopgap solution, but in the long term, the mathematician should really consider purchasing one of Hilbert's Hotels. You can always find some unused room in one of those.
• Mischa: while 8987868546 is a valid input, it will break your test tool, and also many (if not all) of the answers...
• Mr. Xcoder: @MischaBehrend Your example is not a valid input. I think you miscopied my last test case. The valid input was 898786854, not 8987868546 (you have added a 6 at the end)
• Mischa: nvm... should read the whole first rule ... leaving this here so you know why i thought it is valid: it was not a mistake... I changed it intentional to test these scripts... and reading the rules it is a valid input. The sum of all the digits in 8987868546 is not 1 (Rule 1 met) and 8987868546 is a positive integer higher than 1 (Rule 2 met).

Answer 1

05AB1E, (削除) 13 (削除ここまで) 12 bytes

[1⁄4DSO‰0Kθ©#®

Try it online!

Explanation

[ # start loop
 1⁄4 # increment counter
 D # duplicate current value
 SO # sum the digits in the copy
 ‰ # divmod the current value by its digit-sum
 0K # remove 0 from the resulting list
 θ # pop the last element
 © # store a copy in register
 # # if the current value is 1, break
 ® # push the copy from register
 # implicitly output counter

Answer 2

Python 2, (削除) 63 (削除ここまで) 57 bytes

-1 thanks to totallyhuman
-1 thanks to Mr. Xcoder
-4 thanks to reffu

def f(n):a=sum(map(int,`n`));return n>1and-~f(n%a or n/a)

Try it online!

• totallyhuman: 62 bytes, although this approach isn't usually the shortest...
• Mr. Xcoder: 61 bytes, using bitwise tricks
• reffu: 57 bytes Also my apologies for making this my own answer at first. It makes more sense as a comment

Answer 3

Haskell, (削除) 85 (削除ここまで) 78 bytes

f 1=0
f n|r<1=1+f(n`div`s)|1<2=1+f r where s=sum(read.pure<$>show n);r=n`rem`s

Saved 7 bytes thanks to Bruce Forte.

Try it online.

• Laikoni: Save some more bytes by using divMod and dropping the where: Try it online!
• Cristian Lupascu: @Laikoni Wow, that's quite an improvement! Please post it as a different answer; it's different enough from mine. BTW: I was looking for a trick to get rid of the where. I will use this in the future. :)
• nimi: sum[read[d]|d<-show n] saves a byte

Answer 4

JavaScript (ES6), (削除) 66 (削除ここまで) (削除) 58 (削除ここまで) (削除) 51 (削除ここまで) 49 bytes

Takes input as an integer. Returns false for 0 or 1 and throws an overflow error when it encounters any number whose digits add up to 1.

f=n=>n>1&&f(n%(x=eval([...""+n].join`+`))||n/x)+1

• 8 bytes saved with help from Justin.

---

Test it

o.innerText=(
f=n=>n>1&&f(n%(x=eval([...""+n].join`+`))||n/x)+1
)(i.value=898786854);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

• Justin Mariner: Could you save some bytes by summing the digits using eval(array.join`+`)?
• Shaggy: I could indeed, @JustinMariner - you ninjaed me to it! Thanks :)

Answer 5

Husk, 12 bytes

←1ドル¡Ṡ§|÷%oΣd

Try it online!

Explanation

←1ドル¡Ṡ§|÷%oΣd Implicit input, e.g. n=1782
 Ṡ§|÷%oΣd This part defines the transformation.
 oΣ Sum of
 d digits: s=18
 Ṡ % n mod s: 0
 §| or (take this branch if last result was 0)
 ÷ n divided by s: 99
 ¡ Iterate the transformation: [1782,99,9,1,1,1,...
 1ドル Index of 1 (1-based): 4
← Decrement: 3
 Print implicitly.

Answer 6

C# (.NET Core), 87 bytes

n=>{int i=0,k,l;for(;n>1;++i){for(l=n,k=0;l>0;l/=10)k+=l%10;n=n%k>0?n%k:n/k;}return i;}

Try it online!

Lambda function that takes and returns an integer.

Answer 7

Japt, (削除) 22 (削除ここまで) (削除) 19 (削除ここまで) 17 bytes

-3 bytes thanks to @Shaggy.
-2 bytes thanks to @ETHproductions

ìx>1©1+ßU%VaU/V

Try it online!

• Shaggy: <s>20 bytes</s> 19 bytes
• ETHproductions: Actually, you can change s_¬ to ì to save another two bytes :-)
• Justin Mariner: @ETHproductions Oh, that's really cool, thanks!

Answer 8

Retina, 100 bytes

$
;
{`(.+);
1ドル$*1;$&
(?<=;.*)\d(?=.*;)
$*
.*;1;(.*)
$.1
r`(1)*(3円)*;(1+);
$#1;$#2;1
0;(.*);|;.*;
1ドル;

Try it online! Link only includes smaller test cases as the larger ones take too long.

Answer 9

Mathematica, 73 bytes

(t=#;For[r=0,t>1,r++,If[(s=Mod[t,g=Tr@IntegerDigits@t])<1,t=t/g,t=s]];r)&

• Mr. Xcoder: Can ==0 be replaced with <1?
• ZaMoC: @Mr.Xcoder yes, of course! I made a sorter version...

Answer 10

PHP, 68+1 bytes

unary output:

for($n=$argn;$n>1;$n=$n%($s=array_sum(str_split($n)))?:$n/$s)echo 1;

decimal output, 73+1 bytes:

for($n=$argn;$n>1;$i++)$n=$n%($s=array_sum(str_split($n)))?:$n/$s;echo$i;

Run as pipe with -nR or try it online.

---

The Elvis operator requires PHP 5.3 or later. For older PHP, replace ?: with ?$n%$s: (+5 bytes).

Answer 11

Ruby, 46 bytes

f=->n{s=n.digits.sum;n<2?0:1+f[n%s<1?n/s:n%s]}

Answer 12

Haskell, (削除) 94 (削除ここまで) (削除) 93 (削除ここまで) (削除) 89 (削除ここまで) 88 bytes

This feels really long..

length.fst.span(/=1).iterate g
g x|(d,m)<-x`divMod`sum[read[d]|d<-show x]=last$m:[d|m<1]

Try it online!

Thanks @Laikoni & @nimi for golfing off 1 byte each!

Answer 13

C (gcc), (削除) 83 (削除ここまで) (削除) 81 (削除ここまで) (削除) 76 (削除ここまで) 73 bytes

i,k,s;f(n){k=n;for(i=0;k>1;i++,n=k=k%s?:k/s)for(s=0;n;n/=10)s+=n%10;n=i;}

Try it online!

Answer 14

Jelly, 12 bytes

dDS$Ṛȯ/μÐL·L’

Try it online!

• Mr. Xcoder: Interesting approach! Now we're waiting for Jonathan :P
• Erik the Outgolfer: @Mr.Xcoder I don't think so this time :)
• Mr. Xcoder: Nor do I, that was a joke :)

Answer 15

Pyth, (削除) 20 (削除ここまで) 14 bytes

tl.ue-.DNsjNT0

Try it here.

Answer 16

Perl, (削除) 71 (削除ここまで) bytes, (削除) 64 (削除ここまで) bytes, 63 bytes

-pl
$c=0;while($_>1){$s=0;$s+=$_ for/./g;$_=$_%$s?$_%$s:$_/$s;++$c};$_=$c

Try it online

EDIT: saved 7 bytes, thanks to Xcali's comment

-p
while($_>1){$s=0;$s+=$_ for/./g;$_=$_%$s?$_%$s:$_/$s;++$c}$_=$c

EDIT: since 5.14 non destructive substitution s///r

-pl
while($_>1){$s=eval s/\B/+/gr;$_=$_%$s?$_%$s:$_/$s;++$c}$_=$c

• Erik the Outgolfer: Is the -pl on top supposed to be a command-line flag instead?
• Nahuel Fouilleul: yes they are perl options
• Erik the Outgolfer: You should be counting the -pl flag according to this post.
• Nahuel Fouilleul: I counted 69 bytes +2 for pl options, is it correct?
• Xcali: You can golf this down a bit. $c doesn't need to be initialized. It will start at undef which is 0. The semicolon after the while closure can go. Also, you don't need -l. It's not required to take multiple inputs in one run.

Answer 17

Dyalog APL, 36 bytes

{x←+/⍎ ̈⍕⍵⋄1=⍵:0⋄0=x|⍵:1+∇⍵÷x⋄1+∇x|⍵}

Try it online!

How?

{
 x←+/⍎ ̈⍕⍵ ⍝ x = digit sum
 1=⍵:0 ⍝ if arg = 1: bye
 0=x|⍵:1+∇⍵÷x ⍝ if arg divisible by x: recurse with arg/x
 1+∇x|⍵ ⍝ recurse with arg mod x
}

Answer 18

Gaia, 13 bytes

-@{:ΣZ¤∨)‡}°\

Try it online!

Explanation

- Push -1 (this will be the counter)
 @ Push input (the starting number)
 {:ΣZ¤∨)‡}° Repeat this block until the results of 2 consecutive runs are the same:
 : Copy the number
 Σ Digital sum
 Z Divmod number by digital sum
 ¤ Swap
 ∨ Logical or: left-most non-zero out of (number mod sum, number div sum)
 )‡ Increment the counter
 \ Delete the final 1, implicitly print the counter

Answer 19

Matlab, 150 bytes

function[d]=X(x) 
d=0;while ~strcmp(x,'1')z='sum(str2num(x(:)))';a=eval(['rem(',x,',',z,')']);y=num2str(a*(a>0)+eval([x,'/',z])*(a==0));x=y;d=d+1;end

Inputs should be given to the function as a string, such as X('152').

The function works by while looping and incrementing d. The x=y; line was necessary to avoid an error of Matlab trying to read and overwrite a variable value at the same time, apparently, which was a new one on me.

Ungolfed:

function[d]=X(x) 
d=0;
while ~strcmp(x,'1')
 z='sum(str2num(x(:)))';
 a=eval(['rem(',x,',',z,')']);
 y=num2str(a*(a>0)+eval([x,'/',z])*(a==0));
 x=y;
 d=d+1;
end

Answer 20

Haskell, 68 bytes

f 1=0
f n=1+[f x|x<-[mod n,div n]<*>[sum$read.pure<$>show n],x>0]!!0

Try it online! Based on w0lf's answer.

Answer 21

R, 85 bytes

function(n){while(n>1){n="if"(x<-n%%(d=sum(n%/%10^(nchar(n):0)%%10)),x,n/d)
F=F+1}
F}

Anonymous function that returns the required output.

Verify all test cases!