Zdefiniujmy sekwencję: Sekwencja sumowania n cyfr (n-DSS) to sekwencja rozpoczynająca się od n . Jeśli ostatnią liczbą było k , to następną liczbą jest k + cyfra-suma (k) . Oto kilka pierwszych 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...

Dla 1 jest to A004207 , chociaż kilka pierwszych cyfr jest różnych z powodu nieco innej definicji. Dla 3 jest to A016052 ; dla 9, A016096 .

Dzisiejsze wyzwanie polega na znalezieniu sekwencji o najniższej liczbie cyfr, w której pojawia się dana liczba. Nazywa się to „odwrotną funkcją kolumbijską” i jest to A036233 . Pierwsze dwadzieścia terminów, zaczynając od 1, to:

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

Kilka innych dobrych przypadków testowych:

117: 9
1008: 918

Musisz obsługiwać liczby całkowite większe niż 0 i możesz przyjmować dane wejściowe i wyjściowe w dowolnym standardowym formacie. Jak zwykle jest to gra w golfa , więc wygrywa najkrótsza odpowiedź w każdym języku.

Haskell , 104 64 63 bajtów

(-26 dzięki H.PWiz, dodatkowe -14 dzięki Sriotchilism O'Zaic, dodatkowe -1 dzięki Cole)

To jest funkcja.

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

Wypróbuj online!

Wyjaśnienie:

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

Sekwencja złożonych funkcji, która zwraca y + cyfrowa suma y. Najpierw konwertuje na ciąg, a następnie wykonuje gimnastykę monad, aby uzyskać sumę znaków i oryginalny numer (dzięki Cole).

<*>Operator w tym kontekście ma rodzaj i definicję

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

więc możemy napisać powyższe jako

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

To read . purekonwertuje Charna liczbę, więc (+) . read . pure :: Char -> Int -> Intdodaje cyfrę do skumulowanej wartości. Ta wartość jest inicjalizowana do podanej liczby w zakładce.

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

untilwielokrotnie stosuje funkcję do swojego wyniku (w tym przypadku y + suma cyfrowa y), dopóki nie spełni wymagania określonego przez funkcję w pierwszym argumencie. Daje to najmniejszy element y-DSS, który jest większy lub równy x.

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

Nieskończona leniwa lista y, tak że najmniejszy element y-DSS> = x to w rzeczywistości x. Używa notacji ze zrozumieniem listy Haskella (o której też całkowicie zapomniałem, dziękuję wam wszystkim).

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

Pierwszy element tej listy, który jest najmniejszy i spełnia wymagania wyzwania.

Python 2 , 73 71 bajtów

-2 bajty dzięki Erikowi .

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

Wypróbuj online!

Perl 6 , 44 bajtów

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

Wypróbuj online!

Naiwne rozwiązanie, które sprawdza każdą sekwencję, dopóki nie znajdzie takiej, która zawiera dane wejściowe

Wyjaśnienie:

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

Rubinowy , 51 bajtów

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

Wypróbuj online!

Galaretka , 11 bajtów

D+ƒ$С€œi⁸Ḣ

Wypróbuj online!

Pełny program

MATL , 18 bajtów

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

Wypróbuj online! Lub sprawdź pierwsze 20 wartości .

Wyjaśnienie

W przypadku danych wejściowych jest ito coraz częstsze, ndopóki nie zostaną uwzględnione pierwsze iwarunki n-tej sekwencji i. Wystarczy przetestować iwarunki dla każdej sekwencji, ponieważ sekwencja rośnie.

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

Dalej (gforth) , 106 bajtów

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

Wypróbuj online!

Objaśnienie kodu

: 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 bajtów

fqQ.W<HQ+ssM`

Wypróbuj tutaj lub sprawdź pakiet testowy .

Jak to działa

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$

Galaretka , 9 bajtów

DS+)i$ƬṖṪ

Monadyczny link przyjmujący dodatnią liczbę całkowitą, nktóra daje dodatnią liczbę całkowitą, a(n)odwrotny kolumbijski z n.

Wypróbuj online! Lub zobacz zestaw testowy .

W jaki sposób

Skutecznie pracujemy wstecz, wielokrotnie szukając wartości, którą dodaliśmy, dopóki jej nie znajdziemy:

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

Używając 13jako przykład ...

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 bajtów

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

Wypróbuj online!

To z pewnością działa dla wszystkich przypadków testowych, a także dla wszystkich wpisów 1..88 podanych w OEIS; ale nadal nie jestem całkiem pewien, że to provably poprawne. (To jedna z moich skarg na Church of Unit Testing :)).

Wolfram Language (Mathematica) , 61 bajtów

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

Wypróbuj online!

MathGolf , 13 bajtów

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

Wypróbuj online!

Świetne wyzwanie! Spowodowało to, że znalazłem kilka błędów w niejawnym popowym zachowaniu MathGolf, który dodał 1-2 bajty do rozwiązania.

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

Aby udowodnić, że to zawsze zadziała, łatwo to zauważyć n <= input, ponieważ inputjest to pierwszy element inputsekwencji. Technicznie nie udowodniłem, że to rozwiązanie jest zawsze ważne, ale przechodzi każdy testowany przypadek.

05AB1E , 13 bajtów

L.ΔIGÐSO+})Iå

Wypróbuj online!

Czysty , 86 bajtów

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

Wypróbuj online!

Rozszerzony:

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

Niepokoi mnie digitToInt dto, że jest dłużej niżtoInt d-48

C (gcc) , 102 bajty

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

Wypróbuj online!

JavaScript, 65 bajtów

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

Wypróbuj online!

Działa również jako C, ale kosztuje jeszcze jeden bajt

C (gcc) , 66 bajtów

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

Wypróbuj online!

C # (interaktywny kompilator Visual C #) , 83 , 82 bajtów

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

Wypróbuj online!

Japt , 15 14 bajtów

Trójskładnik do obsługi przypadków, które input=outputmnie denerwują!

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

Spróbuj

@Ç?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 bajtów

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

Wypróbuj online!

Wyjaśnienie

=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

Dalej (gforth) , 99 bajtów

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

Wypróbuj online!

W dużej mierze podobny do przesłania reffu (106 bajtów) . Części do gry w golfa to:

• Obliczanie sumy cyfr (-6)
• Końcowe czyszczenie (-1) poprzez wydrukowanie śmieci na standardowe wyjście. (Nie ma problemu, ponieważ wynik jest zwracany na górze stosu).

Jak to działa

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

Węgiel drzewny , 26 bajtów

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

Wypróbuj online! Link jest do pełnej wersji kodu. Wykorzystuje algorytm @ ChasBrown. Jeśli okaże się to nieważne, to dla 29 bajtów:

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

Wypróbuj online! Link jest do pełnej wersji kodu. Działa poprzez obliczenie pierwszego elementu każdej sekwencji sumowania cyfr nie mniej niż n. Wyjaśnienie:

Ｎθ

Wejście n.

Ｗ¬№υθ«

Pętla, aż znajdziemy cyfrową sekwencję sumującą zawierającą n.

≔⊕Ｌυη

Następna sekwencja zaczyna się o jedną więcej niż liczba dotychczasowych sekwencji.

Ｗ‹ηθ

Pętla, gdy element sekwencji jest mniejszy niż n.

≧⁺Σηη

Dodaj sumę cyfr, aby uzyskać następny element sekwencji.

⊞υη

Wciśnij ostatniego członka na listę.

»ＩＬυ

Wydrukuj liczbę wyliczonych list, dopóki nie znajdziemy jednej zawierającej n.

Czerwony , 103 bajty

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

Wypróbuj online!

CJam , 25 bajtów

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

Wypróbuj online!

Gaia , 16 bajtów

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

Wypróbuj online!

Zwraca listę zawierającą najmniejszą liczbę całkowitą.

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 bajtów

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

Wypróbuj online!

Korzysta z obserwacji poczynionej przez pana Xcodera . Nie jest krótszy od drugiego, ale mimo to jest interesującym podejściem.

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 bajtów

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

Wypróbuj online!

Trzecie podejście nie wykorzystuje N-find, #ale nadal opiera się na tej samej obserwacji, co podejście środkowe. Zwraca liczbę całkowitą zamiast listy.

Clojure , 106 bajtów

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

Wypróbuj online!

Jest to 99 bajtów, ale powoduje przepełnienie stosu dla większych danych wejściowych (być może poprawienie JVM pomogłoby):

#((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 # (interaktywny kompilator Visual C #) , 75 bajtów

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

Wypróbuj online!

Łuska , 14 10 bajtów

^{-4 dzięki @ H.PWiz}

V£⁰m¡SF+dN

Wypróbuj online!

atrament , 130 127 bajtów

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

Wypróbuj online!

• -3 bytes poprzez konwersję do pełnego programu, który pobiera jednoargumentowy wkład.

To wydaje się zbyt długie, aby nie można było grać w golfa.

Nie golfił

// 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 bajtów

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

Wypróbuj online!

-2 od sufitu