20
\$\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\$
  • \$\begingroup\$ Inspired by this challenge, although it might not seem related at first. \$\endgroup\$ – Mr. Xcoder Aug 16 '17 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 '17 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 '17 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 '17 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 '17 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\$
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\$
  • \$\begingroup\$ Save some more bytes by using divMod and dropping the where: Try it online! \$\endgroup\$ – Laikoni Aug 16 '17 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\$ – Cristian Lupascu Aug 16 '17 at 13:47
  • \$\begingroup\$ sum[read[d]|d<-show n] saves a byte \$\endgroup\$ – nimi Aug 16 '17 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\$
  • 1
    \$\begingroup\$ Could you save some bytes by summing the digits using eval(array.join`+`)? \$\endgroup\$ – Justin Mariner Aug 16 '17 at 10:13
  • \$\begingroup\$ I could indeed, @JustinMariner - you ninjaed me to it! Thanks :) \$\endgroup\$ – Shaggy Aug 16 '17 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\$
  • 1
    \$\begingroup\$ <s>20 bytes</s> 19 bytes \$\endgroup\$ – Shaggy Aug 16 '17 at 16:56
  • 1
    \$\begingroup\$ Actually, you can change s_¬ to ì to save another two bytes :-) \$\endgroup\$ – ETHproductions Aug 18 '17 at 21:29
  • \$\begingroup\$ @ETHproductions Oh, that's really cool, thanks! \$\endgroup\$ – Justin Mariner Aug 18 '17 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\$
  • \$\begingroup\$ Can ==0 be replaced with <1? \$\endgroup\$ – Mr. Xcoder Aug 16 '17 at 10:47
  • \$\begingroup\$ @Mr.Xcoder yes, of course! I made a sorter version... \$\endgroup\$ – J42161217 Aug 16 '17 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\$
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\$
  • \$\begingroup\$ Interesting approach! Now we're waiting for Jonathan :P \$\endgroup\$ – Mr. Xcoder Aug 16 '17 at 10:46
  • \$\begingroup\$ @Mr.Xcoder I don't think so this time :) \$\endgroup\$ – Erik the Outgolfer Aug 16 '17 at 10:47
  • \$\begingroup\$ Nor do I, that was a joke :) \$\endgroup\$ – Mr. Xcoder Aug 16 '17 at 10:48
1
\$\begingroup\$

Pyth, 20 14 bytes

tl.ue-.DNsjNT0

Try it here.

\$\endgroup\$
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\$
  • \$\begingroup\$ Is the -pl on top supposed to be a command-line flag instead? \$\endgroup\$ – Erik the Outgolfer Aug 16 '17 at 10:55
  • \$\begingroup\$ yes they are perl options \$\endgroup\$ – Nahuel Fouilleul Aug 16 '17 at 10:57
  • \$\begingroup\$ You should be counting the -pl flag according to this post. \$\endgroup\$ – Erik the Outgolfer Aug 16 '17 at 11:53
  • \$\begingroup\$ I counted 69 bytes +2 for pl options, is it correct? \$\endgroup\$ – Nahuel Fouilleul Aug 16 '17 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 '17 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, privacy policy and cookie policy

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