27
\$\begingroup\$

Let's define a sequence: The n digit summing sequence (n-DSS) is a sequence that starts with n. If the last number was k, then the next number is k + digit-sum(k). Here are the first few n-DSS:

1-DSS: 1, 2, 4, 8, 16, 23, 28, 38, 49, 62, 70...
2-DSS: 2, 4, 8, 16, 23, 28, 38, 49, 62, 70, 77...
3-DSS: 3, 6, 12, 15, 21, 24, 30, 33, 39, 51, 57...
4-DSS: 4, 8, 16, 23, 28, 38, 49, 62, 70, 77, 91...
5-DSS: 5, 10, 11, 13, 17, 25, 32, 37, 47, 58, 71...
6-DSS: 6, 12, 15, 21, 24, 30, 33, 39, 51, 57, 69...
7-DSS: 7, 14, 19, 29, 40, 44, 52, 59, 73, 83, 94...
8-DSS: 8, 16, 23, 28, 38, 49, 62, 70, 77, 91, 101...
9-DSS: 9, 18, 27, 36, 45, 54, 63, 72, 81, 90, 99...

For 1, this is A004207, although the first few digits are different due to a slightly different definition. For 3, it's A016052; for 9, A016096.

Today's challenge is to find the lowest n digit sum sequence that a given number appears in. This is called the "Inverse Colombian Function", and is A036233. The first twenty terms, starting with 1 are:

1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 5, 3, 5, 7, 3, 1, 5, 9, 7, 20

Some other good test cases:

117: 9
1008: 918

You only have to handle integers greater than 0, and you can take input and output in any standard format. As usual, this is , so shortest answer in each language wins.

\$\endgroup\$

28 Answers 28

12
\$\begingroup\$

Haskell, 104 64 63 bytes

(-26 thanks to H.PWiz, additional -14 thanks to Sriotchilism O'Zaic, additional -1 thanks to cole)

This is a function.

f x=[y|y<-[1..],x==until(>=x)(foldr((+).read.pure)<*>show)y]!!0

Try it online!


Explanation:

(foldr((+).read.pure)<*>show)

Sequence of composited functions that returns y+digital sum of y. Converts to string first, then does some monad gymnastics to get the sum of the characters and the original number (thanks to Cole).

The <*> operator in this context has type and definition

(<*>) :: (a -> b -> c) -> (a -> b) -> c
f <*> g = \x -> f x (g x)

so we can write the above as

\x -> foldr ((+) . read . pure) x (show x)

This read . pure converts a Char into a number, so (+) . read . pure :: Char -> Int -> Int adds a digit to an accumulated value. This value is initialized to the given number in the fold.

until (>=x) {- digital sum function -} y

until repeatedly applies a function to its result (in this case, the y+digital sum y) until it meets a requirement specified by a function in the first argument. This gives the smallest y-DSS element that's greater or equal to x.

[y | y<-[1..]; x == {- smallest y-DSS element >= x -} ]

Infinite lazy list of y's such that the smallest y-DSS element >= x is actually x. Uses Haskell's list comprehension notation (which I'd also totally forgotten about, thank y'all).

f x = {- aforementioned list -} !! 0

First element of that list, which is the smallest y that satisfies the requirement of the challenge.

\$\endgroup\$
  • 1
    \$\begingroup\$ Here is how I golfed it. \$\endgroup\$ – H.PWiz Jul 23 at 2:38
  • 1
    \$\begingroup\$ @H.PWiz This should be the same no? I would think so but your use of fmap in the first place confuses me a bit. \$\endgroup\$ – Sriotchilism O'Zaic Jul 23 at 3:08
  • 1
    \$\begingroup\$ OK it took a lot of fenangling but I abused the reader monad to shave off a single byte. Woohoo pointfree code! TIO \$\endgroup\$ – cole Jul 23 at 7:06
  • \$\begingroup\$ @SriotchilismO'Zaic Cool. I just golfed the code mechanically, without thinking about it \$\endgroup\$ – H.PWiz Jul 23 at 11:43
  • 1
    \$\begingroup\$ Not sure how to edit request on mobile so I just edited in an explanation of my code - feel free to change or roll back. \$\endgroup\$ – cole Jul 23 at 20:02
5
\$\begingroup\$

Python 2, 73 71 bytes

-2 bytes thanks to Erik.

n=input();k=K=1
while n-k:K+=k>n;k=[k+sum(map(int,`k`)),K][k>n]
print K

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Perl 6, 44 bytes

->\a{+(1...{a∈($_,{$_+.comb.sum}...*>a)})}

Try it online!

Naive solution that checks every sequence until it finds one that contains the input

Explanation:

->\a{                                    }  # Anonymous code block taking input as a
     +(1...{                           })   # Find the first number
            a∈(                       )     # Where the input is an element of
                                ...         # The sequence
               $_,                          # Starting with the current number
                  {            }   # Where each element is
                   $_+             # Is the previous element plus
                      .comb.sum    # The digit sum
                                   *>a      # Until the element is larger than the input
\$\endgroup\$
3
\$\begingroup\$

Ruby, 51 bytes

->n{(1..n).find{|i|i+=i.digits.sum while i<n;i==n}}

Try it online!

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

Jelly, 11 bytes

D+ƒ$С€œi⁸Ḣ

Try it online!

Full program.

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

MATL, 18 bytes

`@G:"ttFYAs+]vG-}@

Try it online! Or verify the first 20 values.

Explanation

For input i, this keeps increqsing n until the first i terms of n-th sequence include i. It is sufficient to test i terms for each sequence because the sequence is increasing.

`         % Do...while
  @       %   Push iteration index, n. This is the firsrt term of the n-th sequence
  G:      %   Push [1 2 ... i], where i is the input
  "       %   For each (i.e., do the following i times)
    tt    %     Duplicate twice
    FYA   %     Convert to digits
    s     %     Sum
    +     %     Add to previous term. This produces a new term of the n-th sequence
  ]       %   End
  v       %   Concatenate all terms into a column vector
  G-      %   Subtract i, element-wise. This is the do...while loop condition (*).
}         % Finally (this is executed right before exiting the loop)
  @       %   Push current n. This is the output, to be displayed
          % End (implicit). A new iteration will start if all terms of (*) are nonzero
          % Display (implicit)
\$\endgroup\$
3
\$\begingroup\$

Pyth, 13 bytes

fqQ.W<HQ+ssM`

Try it here or check out the test suite.


How it works

fqQ.W<HQ+ssM`     Full program. Takes input Q from STDIN, writes to STDOUT.
f{...}            Loop over 1,2,3,... and find the first number to yield truthy results when
                     applying the function {...} (whose variable is T = the current integer).
 qQ.W<HQ+ssM`     The function {...}, which will be analysed separately.
   .W             Functional while. While condition A is true, do B.
     <HQ          Cond. A (var: H - starts at T): Checks if H is less than Q.
        +ssM`     Func. B (var: G - G & H are the same): If A, G & H become G+digit sum(G)
                  The last value of this functional while will be the least possible number N
                  in the T-DSS that is greater than or equal to Q.
                  If N = Q, then Q ∈ T-DSS. Else (if N > Q), then Q ∉ T-DSS.
 q                That being said, check whether N == Q. 

In most languages, it would be easier to loop on the set of the natural numbers, find the first \$n\$ terms of the \$k\$-DSS (because the digit sum is always at least \$1\$ so the repeated addition of this type of quantity cannot result in a value smaller than \$n\$) and check if \$n\$ belongs in those first \$n\$ terms of the \$k\$-DSS. In Pyth, however, the available control-flow structures actually make it easier to generate terms until a certain condition is met, rather than a fixed number of terms.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nicely done, I had fqQ.W<HQ+sjZ10 for 14. I keep forgetting about ` and s as a way of getting digits from an integer! \$\endgroup\$ – Sok Jul 23 at 19:48
3
\$\begingroup\$

Jelly, 9 bytes

DS+)i$ƬṖṪ

A monadic Link accepting a positive integer n which yields a positive integer, a(n), the Inverse Colombian of n.

Try it online! Or see the test-suite.

How

Effectively we work backwards, repeatedly looking for the value we added to until we cannot find one:

DS+)i$ƬṖṪ - Link: integer n
      Ƭ   - Repeat until a fixed point, collecting up:
     $    -   last two links as a monad - f(n):
   )      -     left links as a monad for each - [g(x) for x in [1..n]]:
D         -       decimal digits of x
 S        -       sum
  +       -       add x
    i     -     first (1-indexed) index of n in that list, or 0 if no found
       Ṗ  - pop of the rightmost value (the zero)
        Ṫ - tail

Using 13 as an example...

D  )  = [[1],[2],[3],[4],[5],[6],[7],[8],[9],[1,0],[1,1],[1,2],[1,3]]
 S    = [  1,  2,  3,  4,  5,  6,  7,  8,  9,    1,    2,    3,    4]
  +   = [  2,  4,  6,  8, 10, 12, 14, 16, 18,   11,   13,   15,   17]
    i 13 = .......................................... 11
    i 11 = .................................... 10
    i 10 = ............... 5
    i 5 = not found = 0 
    i 0 = not found = 0
    Ƭ -> [13, 11, 10, 5, 0]
    Ṗ =  [13, 11, 10, 5]
    Ṫ =               5
\$\endgroup\$
2
\$\begingroup\$

Python 2, 85 bytes

f=lambda n,a=[]:n in a and a.index(n)or f(n,[k+sum(map(int,`k`))for k in a]+[len(a)])

Try it online!

This certainly works for all the test cases, plus all of the 1..88 entries given at OEIS; but still I'm not quite sure it's provably correct. (This is one of my complaints regarding the Church Of Unit Testing :)).

\$\endgroup\$
  • \$\begingroup\$ This is hardly a truly rigorous proof but: Let \$d(x)\$ be the digits of \$x\$ and \$C_i(s)\$ be the Columbian function starting from \$i\$ after taking \$s\$ steps, that is, \$C_i(0)=i; C_i(s)=C_i(s-1)+\Sigma d(C_i(s-1))\$. Now, for any \$x>1\$ it holds that \$\exists e\in d(x) (e\geq1)\$ and \$\forall e\in d(x) (e\geq0)\$, which means that \$\Sigma d(x)\geq1\$. (1/2) \$\endgroup\$ – Value Ink Jul 23 at 20:57
  • \$\begingroup\$ Now, define \$S(i)\$ such that \$C_i(S(i))=n\$. Because of our earlier conclusion \$\Sigma d(C_i(s-1))\geq1\$, we can intuit that for any \$i<i'\leq n\$ where \$S(i),S(i')\$ are defined, \$S(i')-S(i)\leq i'-i\$. This leads to the conclusion that for your function, the smallest such index \$i\$ will equal \$n\$ in at most as many steps as it takes to reach the next such \$i\$, in which case a.index(n) will prioritize the smaller of the two. (2/2) \$\endgroup\$ – Value Ink Jul 23 at 20:57
  • \$\begingroup\$ @Value Ink: Roger! That totally works. Thanks! \$\endgroup\$ – Chas Brown Jul 24 at 6:22
2
\$\begingroup\$

Wolfram Language (Mathematica), 61 bytes

For[j=i,#>=j,j=j+Tr@IntegerDigits@j,j/.#->Return@i]~Do~{i,#}&

Try it online!

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

MathGolf, 13 bytes

╒môk(É∙Σ+=k/)

Try it online!

Great challenge! It caused me to find a few bugs within the implicit pop behavior of MathGolf, which added 1-2 bytes to the solution.

Explanation (using input \$3\$)

╒               range(1,n+1) ([1, 2, 3])
 mô             explicit map using 6 operators
   k(           push input-1 to TOS
     É          start block of length 3 (repeat input-1 times)
      ∙Σ+       triplicate TOS, take digit sum of top copy, and add that to second copy
                This transforms the array items to their respective sequences instead
                Array is now [1, 2, 4, 2, 4, 8, 3, 6, 12]
         =      get index of element in array (the index of 3 is 6)
          k/    divide by input (gives 2)
            )   increment (gives the correct answer 3)

To prove that this will always work, it is easy to see that n <= input, because input is the first element of the inputth sequence. I have technically not proved that this solution is always valid, but it does pass every test case that I have tested.

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

05AB1E, 13 bytes

L.ΔIGÐSO+})Iå

Try it online!

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

Forth (gforth), 106 bytes

: f
>r 0 begin 1+ dup begin dup i < while dup begin 10 /mod >r + r> ?dup 0= until repeat i = until rdrop
;

Try it online!

Code Explanation

: f                \ start a new word definition
  >r               \ store the input on the return stack for easy access
  0                \ set up a counter
  begin            \ start an indefinite loop
    1+ dup         \ add 1 to the counter and duplicate
    begin          \ start a 2nd indefinite loop
      dup i <      \ check if current value is less than the input value
    while          \ if it is, continue with the inner loop
      dup          \ duplicate the current value
      begin        \ innermost loop, used to get the digit-wise sum of a number
        10 /mod    \ get quotient and remainder of dividing by 10
        >r + r>    \ add remainder to current list value
        ?dup 0=    \ check if quotient is 0
      until        \ end the innermost loop if it is
    repeat         \ go back to the beginning of the 2nd loop
    i =            \ check if the "last" value of the current list = the input value
  until            \ if it does, we're done
  rdrop            \ remove the input value from the return stack
;                  \ end the word definition    
\$\endgroup\$
1
\$\begingroup\$

Clean, 86 bytes

import StdEnv
$n=hd[i\\i<-[1..]|n==while((>)n)(\j=j+sum[toInt d-48\\d<-:toString j])i]

Try it online!

Expanded:

$ n                    // function `$` of `n` is
 = hd [                // the first
   i                   // integer `i`
  \\                   // for
   i <- [1..]          // each integer from 1 upwards
  |                    // where 
   n ==                // `n` is equal to
   while ((>) n) (     // the highest value not more than `n` from
    \j = j + sum [     // `j` plus the sum of
      toInt d - 48     // the digital value
     \\                // for each
      d <-: toString j // digit in the string form of `j`
     ]                 // where `j` is the previous term
    )                  // of the sequence
   i                   // starting with term `i`
  ]

It bothers me that digitToInt d is longer than toInt d-48

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

C (gcc), 102 bytes

f(n,i,s){for(i=1;n^s;)for(s=i++;s<n;){char*p,j=0,l=asprintf(&p,"%d",s);for(;j<l;)s+=p[j++]-48;}n=~-i;}

Try it online!

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

JavaScript, 65 bytes

n=>eval('for(i=p=1;n-p;p=p>n?++i:p)for(j=p;j;j=j/10|0)p+=j%10;i')

Try it online!


It also works as C, but cost one more byte

C (gcc), 66 bytes

i,p,j;f(n){for(i=p=1;n-p;p=p>n?++i:p)for(j=p;j;j/=10)p+=j%10;n=i;}

Try it online!

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

C# (Visual C# Interactive Compiler), 83, 82 bytes

n=>Enumerable.Range(1,n).First(x=>{for(;x<n;x+=(x+"").Sum(c=>c-48));return x==n;})

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ 82 bytes \$\endgroup\$ – Expired Data Jul 23 at 10:39
  • \$\begingroup\$ @ExpiredData ah yes how did I forget using the literal value x) \$\endgroup\$ – Innat3 Jul 23 at 10:40
1
\$\begingroup\$

Japt, 15 14 bytes

The ternary to handle cases where input=output is annoying me!

@Ç?X±ìx:XÃøU}a

Try it

@Ç?X±ìx:XÃøU}a     :Implicit input of integer U
@                  :A function taking an integer X as its argument
 Ç                 :  Map each Z in the range [0,U)
  ?                :    If Z>0
   X±              :      Increment X by
     ì             :      Convert X to digit array
      x            :      Reduce by addition
       :X          :    Else X
         Ã         :  End map
          øU       :  Contains U
            }      :End function
             a     :Return the first integer that returns true when passed through that function
\$\endgroup\$
1
\$\begingroup\$

cQuents, 18 bytes

#|1:#bN;A
=A?Z+UDZ

Try it online!

Explanation

=A?Z+UDZ      second line - helper function
               first input = A
               second input = n
=A            first term is A
  ?           mode=query, return true if n in sequence, false if n not in sequence
              each term in the sequence equals
   Z+          previous term +
     U   )                     sum (                          )
      D )                            digits (               )
       Z                                      previous term

#|1:#bN;A     main program
               first input = A  (user input)
               second input = n
#|1           n = 1
   :          mode=sequence, return the nth term in the sequence
    #     )   conditional - next term equals next N that evaluates to true
              N increments, any terms that evaluate to true are added to the sequence
               conditional (                      )
     b   )                   second line (      )
      N;A                                  N, A
\$\endgroup\$
0
\$\begingroup\$

Charcoal, 26 bytes

NθW¬№υθ«UMυ⁺κΣκ⊞υ⊕Lυ»I⊕⌕υθ

Try it online! Link is to verbose version of code. Uses @ChasBrown's algorithm. If that turns out to be invalid, then for 29 bytes:

NθW¬№υθ«≔⊕LυηW‹ηθ≧⁺Σηη⊞υη»ILυ

Try it online! Link is to verbose version of code. Works by calculating the first member of each digit summing sequence not less than n. Explanation:

Nθ

Input n.

W¬№υθ«

Loop until we find a digit summing sequence containing n.

≔⊕Lυη

The next sequence begins with one more than the number of sequences so far.

W‹ηθ

Loop while the member of the sequence is less than n.

≧⁺Σηη

Add the digit sum to get the next member of the sequence.

⊞υη

Push the final member to the list.

»ILυ

Print the number of lists computed until we found one containing n.

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

Red, 103 bytes

func[n][m: 1 loop n[k: m until[if k = n[return m]s: k
foreach d to""k[s: s + d - 48]n < k: s]m: m + 1]]

Try it online!

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

CJam, 25 bytes

q~:T,{[){__Ab:++}T*]T&}#)

Try it online!

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

Gaia, 16 bytes

1⟨⟨:@<⟩⟨:Σ+⟩↺=⟩#

Try it online!

Returns a list containing the smallest integer.

1⟨	      ⟩#	% find the first 1 positive integers where the following is truthy:
	     =		% DSS equal to the input?
  	    ↺		% while
  ⟨:@<⟩			% is less than the input
       ⟨:Σ+⟩		% add the digital sum to the counter

Gaia, 16 bytes

1⟨w@⟨:):Σ++⟩ₓĖ⟩#

Try it online!

Uses the observation made by Mr. Xcoder. It's not shorter than the other, but it's an interesting approach nonetheless.

1⟨	      ⟩#	% find the first 1 integers z where:
  	     Ė		% the input (n) is an element of
  w@⟨:):Σ++⟩ₓ		% the first n terms of the z-th Digital Sum Sequence

Gaia, 16 bytes

┅ẋ⟨@⟨:):Σ++⟩ₓĖ⟩∆

Try it online!

Third approach not using N-find, #, but still relying on the same observation as the middle approach. Returns an integer rather than a list.

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

Clojure, 106 bytes

#(loop[j 1 i 1](if(= j %)i(if(< j %)(recur(apply + j(for[c(str j)](-(int c)48)))i)(recur(inc i)(inc i)))))

Try it online!

This is 99 bytes but results in Stack Overflow on larger inputs (maybe tweaking the JVM would help):

#((fn f[j i](if(= j %)i(if(< j %)(f(apply + j(for[c(str j)](-(int c)48)))i)(f(inc i)(inc i)))))1 1)
\$\endgroup\$
0
\$\begingroup\$

ink, 130 127 bytes

-(l)
+(i)[+]->l
*(w)[{i}]
~temp n=w
-(o){n<i:
~n+=s(n)
->o
}{n>i:->w}{w}
==function s(n)
{n>9:
~return n%10+s(n/10)
}
~return n

Try it online!

  • -3 bytes by converting to a full program which takes unary input.

This feels too long to be ungolfable.

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

C (gcc), 80 79 bytes

i,j;r;v;f(n){for(r=v=n;--r;v=n-i?v:r)for(i=r;i<n;)for(j=i;i+=j%10,j/=10;);n=v;}

Try it online!

-1 from ceilingcat

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

C# (Visual C# Interactive Compiler), 75 bytes

n=>{int a=0,b=0;for(;b!=n;)for(b=++a;b<n;)b+=(b+"").Sum(x=>x-48);return a;}

Try it online!

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

Husk, 14 10 bytes

-4 thanks to @H.PWiz

V£⁰m¡SF+dN

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Here is 10 bytes: €mΩ≥¹SF+dN (I still feel that there is shorter) \$\endgroup\$ – H.PWiz Jul 29 at 14:49
  • \$\begingroup\$ Or V£⁰m¡SF+dN \$\endgroup\$ – H.PWiz Jul 29 at 14:55

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.