Давайте определим последовательность: последовательность суммирования из n цифр (n-DSS) - это последовательность, которая начинается с n . Если последним числом было k , то следующим будет k + цифро-сумма (k) . Вот первые несколько 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...

Для 1 это A004207 , хотя первые несколько цифр отличаются из-за немного другого определения. Для 3 это A016052 ; для 9, A016096 .

Сегодня задача состоит в том, чтобы найти последовательность с наименьшей n-значной суммой, в которой присутствует данное число. Это называется «Обратной функцией Колумбии» и называется A036233 . Первые двадцать терминов, начиная с 1:

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

Некоторые другие хорошие тестовые случаи:

117: 9
1008: 918

Вам нужно обрабатывать только целые числа больше 0, и вы можете использовать ввод и вывод в любом стандартном формате. Как обычно, это код-гольф , поэтому выигрывает самый короткий ответ на каждом языке.

Haskell , 104 64 63 байта

(-26 благодаря H.PWiz, дополнительно -14 благодаря Sriotchilism O'Zaic, дополнительно -1 благодаря Коулу)

Это функция.

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

Попробуйте онлайн!

Объяснение:

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

Последовательность составных функций, которая возвращает y + цифровую сумму y. Сначала преобразуется в строку, затем выполняет гимнастику монады, чтобы получить сумму символов и оригинальное число (спасибо Коулу).

<*>Оператор в этом контексте имеет тип и определение

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

так что мы можем написать выше, как

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

Это read . pureпреобразует число Charв число, поэтому (+) . read . pure :: Char -> Int -> Intдобавляет цифру к накопленному значению. Это значение инициализируется указанным номером в сгибе.

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

untilповторно применяет функцию к своему результату (в данном случае, y + цифровая сумма y), пока она не удовлетворяет требованию, указанному функцией в первом аргументе. Это дает наименьший элемент y-DSS, который больше или равен x.

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

Бесконечный ленивый список y, такой, что наименьший элемент y-DSS> = x на самом деле x. Использует нотацию понимания списка Хаскеллом (о которой я также полностью забыл, спасибо вам всем).

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

Первый элемент этого списка, который является наименьшим y, удовлетворяющим требованию задачи.

Python 2 , 73 71 байт

-2 байта благодаря Эрику .

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

Попробуйте онлайн!

Perl 6 , 44 байта

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

Попробуйте онлайн!

Наивное решение, которое проверяет каждую последовательность, пока не найдет ту, которая содержит ввод

Объяснение:

->\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

Рубин , 51 байт

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

Попробуйте онлайн!

Желе , 11 байт

D+ƒ$С€œi⁸Ḣ

Попробуйте онлайн!

Полная программа.

MATL , 18 байт

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

Попробуйте онлайн! Или проверьте первые 20 значений .

объяснение

Для ввода iэто продолжает увеличиваться nдо тех пор, пока не будут включены первые iчлены n-ой последовательности i. Достаточно проверить iусловия для каждой последовательности, потому что последовательность увеличивается.

`         % 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)

Forth (gforth) , 106 байтов

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

Попробуйте онлайн!

Код Объяснение

: 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    

Pyth , 13 байт

fqQ.W<HQ+ssM`

Попробуйте здесь или проверьте набор тестов .

Как это работает

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. 

В большинстве языков было бы легче зацикливаться на множестве натуральных чисел, найти первое $n$$k$$1$$n$$n$$n$$k$

Желе , 9 байт

DS+)i$ƬṖṪ

Монадическая ссылка, принимающая положительное целое число, nкоторое дает положительное целое число, a(n)обратный колумбийский n.

Попробуйте онлайн! Или посмотрите набор тестов .

Как

По сути, мы работаем в обратном направлении, многократно ищем добавленную стоимость, пока не можем ее найти:

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

Используя 13в качестве примера ...

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

Python 2 , 85 байт

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

Попробуйте онлайн!

Это, безусловно, работает для всех тестовых случаев, плюс все записи 1..88, представленные в OEIS; но все - таки я не совсем уверен , что это доказуемо правильно. (Это одна из моих жалоб относительно Церкви модульного тестирования :)).

Wolfram Language (Mathematica) , 61 байт

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

Попробуйте онлайн!

MathGolf , 13 байт

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

Попробуйте онлайн!

Отличный вызов! Это заставило меня найти несколько ошибок в неявном поп-поведении MathGolf, что добавило 1-2 байта к решению.

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

Чтобы доказать, что это всегда будет работать, это легко увидеть n <= input, потому что inputэто первый элемент inputпоследовательности. Я технически не доказал, что это решение всегда верно, но оно проходит каждый тестовый пример, который я тестировал.

05AB1E , 13 байтов

L.ΔIGÐSO+})Iå

Попробуйте онлайн!

Чисто , 86 байт

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

Попробуйте онлайн!

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

Меня беспокоит, что digitToInt dэто дольше, чемtoInt d-48

C (gcc) , 102 байта

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;}

Попробуйте онлайн!

JavaScript, 65 байт

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

Попробуйте онлайн!

Он также работает как C, но стоит еще один байт

C (gcc) , 66 байт

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;}

Попробуйте онлайн!

C # (интерактивный компилятор Visual C #) , 83 , 82 байта

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

Попробуйте онлайн!

Japt , 15 14 байт

Тройка для обработки случаев, где input=outputменя раздражает!

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

Попытайся

@Ç?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

cQuents , 18 байтов

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

Попробуйте онлайн!

объяснение

=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

Forth (gforth) , 99 байтов

: f >r 0 begin 1+ dup begin dup i < while dup 20 for 10 /mod >r + r> next + repeat i = until r> . ;

Попробуйте онлайн!

Во многом похоже на представление Реффу (106 байт) . Части гольфа:

• Расчет суммы цифр (-6)
• Завершите очистку (-1), напечатав мусор на стандартный вывод. (Нет проблем, потому что результат возвращается на вершине стека.)

Как это работает

: dsum ( n -- n+digitsum ) \ Sub-function. Given n, add its digit sum to n.
  dup                      \ Copy n to form ( n m ) -> extract digits from m and add to n
  20 for                   \ Repeat 20 times (a 64-bit int is at most 20 digits)
    10 /mod >r + r>        \   n += m%10, m = m/10
  next + ;                 \ End loop and discard 0

: f ( n -- ans )    \ Main function.
  >r                \ Move n to the return stack, so it can be referenced using `i`
  0 begin 1+        \ Initialize counter and loop starting from 1
    dup begin       \   Copy the counter (v) and loop
      dup i < while \     break if v >= n
      dsum          \     v += digit sum of v
    repeat          \   End loop
  i = until         \ End loop if n == v
  r> . ;            \ Cleanup the return stack so the function can return correctly
                    \ `r> .` is one byte shorter than `rdrop`

Древесный уголь , 26 байт

ＮθＷ¬№υθ«ＵＭυ⁺κΣκ⊞υ⊕Ｌυ»Ｉ⊕⌕υθ

Попробуйте онлайн! Ссылка на подробную версию кода. Использует алгоритм @ ChasBrown. Если это окажется неверным, то для 29 байтов:

ＮθＷ¬№υθ«≔⊕ＬυηＷ‹ηθ≧⁺Σηη⊞υη»ＩＬυ

Попробуйте онлайн! Ссылка на подробную версию кода. Работает путем вычисления первого члена каждой последовательности суммирования цифр не менее чем n. Объяснение:

Ｎθ

Вход n.

Ｗ¬№υθ«

Цикл, пока мы не найдем последовательность суммирования цифр, содержащую n.

≔⊕Ｌυη

Следующая последовательность начинается на одну единицу больше, чем количество последовательностей.

Ｗ‹ηθ

Цикл, пока член последовательности меньше n.

≧⁺Σηη

Добавьте сумму цифр, чтобы получить следующий член последовательности.

⊞υη

Нажмите последний член в списке.

»ＩＬυ

Выведите количество вычисленных списков, пока мы не найдем один содержащий n.

Красный , 103 байта

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

Попробуйте онлайн!

CJam , 25 байтов

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

Попробуйте онлайн!

Gaia , 16 байт

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

Попробуйте онлайн!

Возвращает список, содержащий наименьшее целое число.

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 байт

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

Попробуйте онлайн!

Использует наблюдение, сделанное г-ном Xcoder . Он не короче другого, но, тем не менее, это интересный подход.

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 байт

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

Попробуйте онлайн!

Третий подход не использует N-find, #но все еще полагается на то же наблюдение, что и средний подход. Возвращает целое число, а не список.

Clojure , 106 байт

#(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)))))

Попробуйте онлайн!

Это 99 байт, но это приводит к переполнению стека на больших входах (возможно, поможет настройка JVM):

#((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)

C # (интерактивный компилятор Visual C #) , 75 байт

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

Попробуйте онлайн!

Шелуха , 14 10 байт

^{-4 благодаря @ H.PWiz}

V£⁰m¡SF+dN

Попробуйте онлайн!

чернила , 130 127 байт

-(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

Попробуйте онлайн!

• -3 bytes путем преобразования в полную программу, которая принимает унарный ввод.

Это слишком долго, чтобы не играть в гольф.

Ungolfed

// This program takes unary input. It passes through the same choice prompt as long as it recieves 1, and execution begins when it recieves 2
-(input_loop)
+(input_value)[+] -> input_loop                 // When this option (option 1) is selected, its read count is incremented. We can access this via the "input_value" variable. We then return to the prompt by going back to the "input_loop" gather
*(which_sequence)[{i}]                          // When this option (option 2) is selected, execution begins. Its read count also serves to keep track of which DSS we're checking.
~temp current_value = which_sequence            // The initial value for the n-DSS is n, of course.
-(sequence)                                     //
{current_value < input_value:                   // If we're still below the value we're looking for, we might find it.
    ~ current_value += digit_sum(current_value) // To get the next number, we add the current number's digit sum
    -> sequence                                 // Then we loop
}
{n > i: -> which_sequence}                      // If we get here, we're at or above our target number. If we're above it, we know it's the wrong sequence and move on to the next one by going back up to option 2. This increments its read count.
{which_sequence}                                // If we get here, we've found the target number, so we output the sequence's number.
// End of main stitch, program ends.

// A function to calculate the digit sum of a number
== function digit_sum(n) ==
{n > 9: // If given a number greater than 9, recurse
    ~ return (n % 10) + digit_sum(n / 10)
}
~ return n // Otherwise, return the input (it's a single digit)

C (gcc) , 80 79 78 байт

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

Попробуйте онлайн!

-2 от потолка