21
\$\begingroup\$

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 , so the shortest code in each language (scored in bytes) wins!

\$\endgroup\$
7
  • \$\begingroup\$ Inspired by this challenge, although it might not seem related at first. \$\endgroup\$
    – Mr. Xcoder
    Aug 16, 2017 at 9:02
  • 3
    \$\begingroup\$ 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. \$\endgroup\$
    – Ray
    Aug 16, 2017 at 22:13
  • \$\begingroup\$ while 8987868546 is a valid input, it will break your test tool, and also many (if not all) of the answers... \$\endgroup\$
    – Mischa
    Aug 17, 2017 at 6:55
  • \$\begingroup\$ @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) \$\endgroup\$
    – Mr. Xcoder
    Aug 17, 2017 at 7:10
  • \$\begingroup\$ 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). \$\endgroup\$
    – Mischa
    Aug 17, 2017 at 7:16

21 Answers 21

6
\$\begingroup\$

05AB1E, 13 12 bytes

[¼DSO‰0Kθ©#®

Try it online!

Explanation

[               # start loop
 ¼              # 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
\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
3
5
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Save some more bytes by using divMod and dropping the where: Try it online! \$\endgroup\$
    – Laikoni
    Aug 16, 2017 at 13:33
  • \$\begingroup\$ @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. :) \$\endgroup\$ Aug 16, 2017 at 13:47
  • \$\begingroup\$ sum[read[d]|d<-show n] saves a byte \$\endgroup\$
    – nimi
    Aug 16, 2017 at 17:05
5
\$\begingroup\$

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>

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Could you save some bytes by summing the digits using eval(array.join`+`)? \$\endgroup\$ Aug 16, 2017 at 10:13
  • \$\begingroup\$ I could indeed, @JustinMariner - you ninjaed me to it! Thanks :) \$\endgroup\$
    – Shaggy
    Aug 16, 2017 at 10:16
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

Japt, 22 19 17 bytes

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


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

Try it online!

\$\endgroup\$
3
  • 1
    \$\begingroup\$ <s>20 bytes</s> 19 bytes \$\endgroup\$
    – Shaggy
    Aug 16, 2017 at 16:56
  • 1
    \$\begingroup\$ Actually, you can change s_¬ to ì to save another two bytes :-) \$\endgroup\$ Aug 18, 2017 at 21:29
  • \$\begingroup\$ @ETHproductions Oh, that's really cool, thanks! \$\endgroup\$ Aug 18, 2017 at 21:32
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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)&
\$\endgroup\$
2
  • \$\begingroup\$ Can ==0 be replaced with <1? \$\endgroup\$
    – Mr. Xcoder
    Aug 16, 2017 at 10:47
  • \$\begingroup\$ @Mr.Xcoder yes, of course! I made a sorter version... \$\endgroup\$
    – ZaMoC
    Aug 16, 2017 at 10:53
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

Ruby, 46 bytes

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

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!

\$\endgroup\$
0
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

Jelly, 12 bytes

dDS$Ṛȯ/µÐĿL’

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Interesting approach! Now we're waiting for Jonathan :P \$\endgroup\$
    – Mr. Xcoder
    Aug 16, 2017 at 10:46
  • \$\begingroup\$ @Mr.Xcoder I don't think so this time :) \$\endgroup\$ Aug 16, 2017 at 10:47
  • \$\begingroup\$ Nor do I, that was a joke :) \$\endgroup\$
    – Mr. Xcoder
    Aug 16, 2017 at 10:48
1
\$\begingroup\$

Pyth, 20 14 bytes

tl.ue-.DNsjNT0

Try it here.

\$\endgroup\$
0
1
\$\begingroup\$

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
\$\endgroup\$
6
  • \$\begingroup\$ Is the -pl on top supposed to be a command-line flag instead? \$\endgroup\$ Aug 16, 2017 at 10:55
  • \$\begingroup\$ yes they are perl options \$\endgroup\$ Aug 16, 2017 at 10:57
  • \$\begingroup\$ You should be counting the -pl flag according to this post. \$\endgroup\$ Aug 16, 2017 at 11:53
  • \$\begingroup\$ I counted 69 bytes +2 for pl options, is it correct? \$\endgroup\$ Aug 16, 2017 at 12:00
  • \$\begingroup\$ 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. \$\endgroup\$
    – Xcali
    Aug 16, 2017 at 13:34
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.