Fungsi Kolombia terbalik

28

Mari kita mendefinisikan urutan: Urutan penjumlahan n digit (n-DSS) adalah urutan yang dimulai dengan n . Jika angka terakhir adalah k , maka angka selanjutnya adalah k + digit-sum (k) . Berikut adalah beberapa n-DSS pertama:

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

Untuk 1, ini adalah A004207 , meskipun beberapa digit pertama berbeda karena definisi yang sedikit berbeda. Untuk 3, ini A016052 ; untuk 9, A016096 .

Tantangan hari ini adalah menemukan urutan penjumlahan n digit terendah yang diberikan angka. Ini disebut "Fungsi Kolombia Terbalik", dan A036233 . Dua puluh istilah pertama, dimulai dengan 1 adalah:

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

Beberapa test case bagus lainnya:

117: 9
1008: 918

Anda hanya perlu menangani bilangan bulat lebih besar dari 0, dan Anda dapat mengambil input dan output dalam format standar apa pun. Seperti biasa, ini adalah , jadi jawaban tersingkat di setiap bahasa menang.

DJMcMayhem
sumber
Terkait
DJMcMayhem

Jawaban:

12

Haskell , 104 64 63 byte

(-26 terima kasih kepada H.PWiz, tambahan -14 terima kasih kepada Sriotchilism O'Zaic, tambahan -1 berkat cole)

Ini sebuah fungsi.

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

Cobalah online!


Penjelasan:

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

Urutan fungsi gabungan yang mengembalikan y + jumlah digital y. Konversi menjadi string pertama, lalu lakukan beberapa senam monad untuk mendapatkan jumlah karakter dan nomor asli (terima kasih kepada Cole).

The <*>operator dalam konteks ini memiliki tipe dan definisi

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

jadi kita bisa menulis seperti di atas

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

Ini read . puremengubah a Charmenjadi angka, jadi (+) . read . pure :: Char -> Int -> Intmenambahkan digit ke nilai akumulasi. Nilai ini diinisialisasi ke nomor yang diberikan dalam flip.

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

untilberulang kali menerapkan fungsi ke hasilnya (dalam hal ini, y + jumlah digital y) hingga memenuhi persyaratan yang ditentukan oleh fungsi dalam argumen pertama. Ini memberikan elemen y-DSS terkecil yang lebih besar atau sama dengan x.

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

Daftar malas y yang tak terbatas sehingga elemen y-DSS terkecil> = x sebenarnya x. Menggunakan notasi pemahaman daftar Haskell (yang juga telah saya lupakan, terima kasih).

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

Elemen pertama dari daftar itu, yang merupakan y terkecil yang memenuhi persyaratan tantangan.

Transformasi Fourier Rin
sumber
1
Inilah cara saya bermain golf.
H.PWiz
1
@ H. Wiz Ini harus sama, kan? Saya akan berpikir begitu tetapi penggunaan Anda fmapdi tempat pertama membingungkan saya sedikit.
Wheat Wizard
1
OK butuh banyak fenangling tapi saya menyalahgunakan pembaca monad untuk memotong satu byte. Woohoo pointfree code! TIO
cole
@ SriotchilismO'Zaic Keren. Saya baru saja memasukkan kode secara mekanis, tanpa memikirkannya
H.PWiz
1
Tidak yakin bagaimana cara mengedit permintaan di ponsel jadi saya baru saja mengedit penjelasan kode saya - jangan ragu untuk mengubah atau memutar kembali.
cole
4

Perl 6 , 44 byte

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

Cobalah online!

Solusi naif yang memeriksa setiap urutan hingga menemukan yang berisi input

Penjelasan:

->\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
Jo King
sumber
3

Ruby , 51 byte

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

Cobalah online!

Nilai Tinta
sumber
3

MATL , 18 byte

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

Cobalah online! Atau verifikasi 20 nilai pertama .

Penjelasan

Untuk input i, ini terus meningkat nsampai isyarat pertama dari nurutan ke-4 termasuk i. Cukup untuk menguji ipersyaratan untuk setiap urutan karena urutan meningkat.

`         % 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)
Luis Mendo
sumber
3

Keempat (gforth) , 106 byte

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

Cobalah online!

Penjelasan Kode

: 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    
reffu
sumber
3

Pyth , 13 byte

fqQ.W<HQ+ssM`

Coba di sini atau lihat test suite .


Bagaimana itu bekerja

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. 

Dalam kebanyakan bahasa, akan lebih mudah untuk mengulang pada himpunan bilangan alami, menemukan istilah pertama dari -DSS (karena jumlah digit selalu setidaknya sehingga penambahan berulang dari jenis kuantitas ini tidak dapat menghasilkan nilai lebih kecil dari ) dan periksa apakah termasuk dalam pertama istilah -DSS. Dalam Pyth, bagaimanapun, struktur aliran kontrol yang tersedia sebenarnya membuatnya lebih mudah untuk menghasilkan istilah sampai kondisi tertentu terpenuhi, daripada jumlah istilah yang tetap.nk1nnnk

Tuan Xcoder
sumber
1
Bagus, saya punya fqQ.W<HQ+sjZ10untuk 14. Saya selalu lupa tentang `dan s sebagai cara untuk mendapatkan angka dari integer!
Sok
3

Jelly , 9 byte

DS+)i$ƬṖṪ

Tautan monadik yang menerima bilangan bulat positif nyang menghasilkan bilangan bulat positif,, a(n)Kolombia Terbalik dari n.

Cobalah online! Atau lihat test-suite .

Bagaimana

Secara efektif kami bekerja mundur, berulang kali mencari nilai yang kami tambahkan sampai kami tidak dapat menemukannya:

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

Menggunakan 13sebagai contoh ...

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
Jonathan Allan
sumber
2

Python 2 , 85 byte

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

Cobalah online!

Ini tentu saja berfungsi untuk semua kasus uji, ditambah semua 1,88 entri yang diberikan di OEIS; tapi saya masih tidak yakin itu terbukti benar. (Ini adalah salah satu keluhan saya mengenai Church Of Unit Testing :)).

Chas Brown
sumber
d(x)xCi(s)isCi(0)=i;Ci(s)=Ci(s1)+Σd(Ci(s1))x>1ed(x)(e1)ed(x)(e0)Σd(x)1
S(i)Ci(S(i))=nΣd(Ci(s1))1i<inS(i),S(i)S(i)S(i)iiinia.index(n)
@ Nilai Tinta: Roger! Itu benar-benar berfungsi. Terima kasih!
Chas Brown
2

MathGolf , 13 byte

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

Cobalah online!

Tantangan besar! Itu menyebabkan saya menemukan beberapa bug dalam perilaku pop implisit MathGolf, yang menambahkan 1-2 byte ke solusinya.

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)

Untuk membuktikan bahwa ini akan selalu berhasil, mudah untuk melihatnya n <= input, karena inputmerupakan elemen pertama dari inputurutan ke - th. Saya secara teknis tidak membuktikan bahwa solusi ini selalu valid, tetapi tidak lulus setiap test case yang saya uji.

maks
sumber
1

Bersih , 86 byte

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

Cobalah online!

Diperluas:

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

Itu menggangguku yang digitToInt dlebih lama daritoInt d-48

Suram
sumber
1

C (gcc) , 102 byte

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

Cobalah online!

Suram
sumber
1

JavaScript, 65 byte

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

Cobalah online!


Ini juga berfungsi sebagai C, tetapi biaya satu byte lagi

C (gcc) , 66 byte

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

Cobalah online!

tsh
sumber
1

Japt , 15 14 byte

The ternary untuk menangani kasus-kasus di mana input=outputmengganggu saya!

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

Cobalah

@Ç?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
Shaggy
sumber
1

cQuents , 18 byte

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

Cobalah online!

Penjelasan

=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
Stephen
sumber
1

Keempat (gforth) , 99 byte

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

Cobalah online!

Sangat mirip dengan pengajuan reffu (106 byte) . Bagian golf adalah:

  • Perhitungan jumlah digit (-6)
  • Pembersihan akhir (-1) dengan mencetak beberapa sampah ke stdout. (Tidak ada masalah karena hasilnya dikembalikan di atas tumpukan.)

Bagaimana itu bekerja

: 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`
Bubbler
sumber
0

Arang , 26 byte

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Menggunakan algoritma @ ChasBrown. Jika ternyata tidak valid, maka untuk 29 byte:

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

Cobalah online! Tautan adalah untuk mengucapkan versi kode. Bekerja dengan menghitung anggota pertama dari setiap urutan penjumlahan digit tidak kurang dari n. Penjelasan:

Nθ

Masukan n.

W¬№υθ«

Ulangi sampai kami menemukan urutan penjumlahan digit n.

≔⊕Lυη

Urutan berikutnya dimulai dengan satu lebih dari jumlah urutan sejauh ini.

W‹ηθ

Ulangi sementara anggota urutan kurang dari n.

≧⁺Σηη

Tambahkan jumlah digit untuk mendapatkan anggota urutan berikutnya.

⊞υη

Dorong anggota terakhir ke daftar.

»ILυ

Cetak jumlah daftar yang dihitung sampai kami menemukan satu yang berisi n.

Neil
sumber
0

Merah , 103 byte

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

Cobalah online!

Galen Ivanov
sumber
0

Gaia , 16 byte

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

Cobalah online!

Mengembalikan daftar yang berisi bilangan bulat terkecil.

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 byte

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

Cobalah online!

Menggunakan pengamatan yang dilakukan oleh Mr. Xcoder . Ini tidak lebih pendek dari yang lain, tetapi ini merupakan pendekatan yang menarik.

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 byte

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

Cobalah online!

Pendekatan ketiga tidak menggunakan N-find,, #tetapi masih mengandalkan observasi yang sama dengan pendekatan menengah. Mengembalikan integer daripada daftar.

Giuseppe
sumber
0

Clojure , 106 byte

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

Cobalah online!

Ini adalah 99 byte tetapi menghasilkan Stack Overflow pada input yang lebih besar (mungkin mengutak-atik JVM akan membantu):

#((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)
NikoNyrh
sumber
0

Sekam , 14 10 byte

-4 terima kasih kepada @ H.PWiz

V£⁰m¡SF+dN

Cobalah online!

Buah Esolanging
sumber
Berikut ini 10 byte: €mΩ≥¹SF+dN(Saya masih merasa ada yang lebih pendek)
H.PWiz
AtauV£⁰m¡SF+dN
H.PWiz
0

tinta , 130 127 byte

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

Cobalah online!

  • -3 bytes dengan mengkonversi ke program lengkap yang mengambil input unary.

Ini terasa terlalu lama untuk tidak bisa golf.

Tidak disatukan

// 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)
Sara J
sumber
0

C (gcc) , 80 79 78 byte

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

Cobalah online!

-2 dari ceilingcat

attinat
sumber