Cyfrowy pierwiastek (również powtarzana suma cyfrowa) dodatniej liczby całkowitej jest wartością (pojedynczej cyfry) uzyskaną w wyniku iteracyjnego procesu sumowania cyfr, na każdej iteracji z wykorzystaniem wyniku z poprzedniej iteracji do obliczenia sumy cyfrowej. Proces ten trwa do momentu uzyskania liczby jednocyfrowej.

Na przykład cyfrowy pierwiastek z 65536 wynosi 7 , ponieważ 6 + 5 + 5 + 3 + 6 = 25 i 2 + 5 = 7 .

Sortowanie wszystkich cyfrowych pierwiastków nie ma większego sensu, ponieważ zaczynałoby się od nieskończenie wielu 1 s.

Zamiast tego utworzymy listy wszystkich jednocyfrowych liczb całkowitych wraz z cyfrowymi pierwiastkami, następnie wszystkie dwucyfrowe liczby wraz z cyfrowymi pierwiastkami, a następnie potrójne, poczwórne i tak dalej.

Teraz dla każdej z tych list posortujemy ją tak, aby najpierw pojawiły się wszystkie liczby całkowite z cyfrowymi pierwiastkami 1 , a następnie wszystkie liczby całkowite z cyfrowymi pierwiastkami 2 i tak dalej. Sortowanie będzie stabilne, więc lista liczb całkowitych z pewnymi cyfrowymi pierwiastkami powinna być posortowana rosnąco po sortowaniu.

Na koniec połączymy te listy w jedną sekwencję. Ta sekwencja rozpocznie się od wszystkich liczb jednocyfrowych, następnie wszystkich liczb dwucyfrowych (posortowanych według cyfrowego pierwiastka), a następnie wszystkich liczb potrójnych i tak dalej.

Wyzwanie:

Weź jako liczbę całkowitą dodatnią n i wyślij n -tą liczbę w sekwencji opisanej powyżej. Możesz wybrać, czy lista ma wartość 0 - indeks 1 - indeks.

Sekwencja wygląda następująco:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 19, 28, 37, 46, 55, 64, 73, 82, 91, 11, 20, 29 ... 
72, 81, 90, 99, 100, 109, 118, ... 
981, 990, 999, 1000, 1009, 1018, 1027, ...

Przypadki testowe:

Przypadki testowe są indeksowane 1.

   n   f(n)  
   9      9
  10     10
  11     19
  40     13
  41     22
  42     31
  43     40
  44     49
  45     58
 600    105
 601    114
 602    123
 603    132
 604    141
 605    150
4050   1453
4051   1462
4052   1471
4053   1480
4054   1489
4055   1498

Łatwiej kopiować:

n =    9, 10, 11, 40, 41, 42, 43, 44, 45, 600, 601, 602, 603, 604, 605, 4050, 4051, 4052, 4053, 4054, 4055, 
f(n) = 9, 10, 19, 13, 22, 31, 40, 49, 58, 105, 114, 123, 132, 141, 150, 1453, 1462, 1471, 1480, 1489, 1498

Wyjaśnienia:

• Nie możesz wyprowadzać wszystkich n pierwszych elementów. Wyprowadzisz tylko n -ty.
• Kod musi teoretycznie działać dla wszystkich liczb całkowitych do 10 ^ 9 , ale jest OK, jeśli przekroczy limit czasu dla TIO (lub innych interpreterów z ograniczeniami czasowymi) dla danych wejściowych większych niż 999 .
• Wyjaśnienia są zachęcane.

To gra w golfa , więc wygrywa najkrótszy kod w każdym języku! Nie zniechęcaj się innymi rozwiązaniami w języku, w którym chcesz grać w golfa, nawet jeśli są one krótsze niż możesz sobie poradzić!

Python 2 , _{78 60 52 46} 45 bajtów

-6 bajtów dzięki GB .
-1 bajt dzięki Jakob .

n=input()
b=10**~-len(`n`)
print~-b+n/b+n%b*9

Wypróbuj online!

W końcu osiągnął formę zamkniętą, indeksowaną 1.

Python 2 , 78 bajtów

0-indeksowane.

d=10;k=1
exec'\nk+=9\nif k>d+7:k=d;d*=10\nif k>=d:k-=d/10*9-1'*input()
print k

Wypróbuj online!

Python 3 , 80 bajtów

f=lambda i,k=1:k>i and sorted(range(k//10,k),key=lambda n:n%-9)[i-k]or f(i,k*10)

Wypróbuj online!

1-indeksowany. To jest najlepsze, co mogłem zarządzać w Pythonie 3 (no oprócz 78-byter , który jest portem mojego rozwiązania Python 2 poniżej; myślę, że ten jest jednak znacznie fajniejszy). Pełne programy w języku Python 2 są korzystne dla tego konkretnego wyzwania, ponieważ input()wymagają konwersji na intjęzyk Python 3 (+5 bajtów), execjest funkcją, a nie instrukcją (+2 bajty) i /domyślnie wykonuje dzielenie liczb całkowitych, jeśli jej argumentami są liczby całkowite w Py 2 (+1 bajt), więc jest to zdecydowanie krótszy czas niż przeniesienie odpowiedzi ovs .

Jak to działa

Ustawiać

f=lambda i,k=1:k>i and ... or f(i,k*10)

Definiuje funkcji rekurencyjnej F , które zajmuje jedną liczbę argumentów ı i drugiego, k , domyślnie jest to 1 . Podczas gdy k ≤ i , funkcja f zwraca f (i, 10k) , mnożąc k przez 10 za każdym razem, aż stanie się większe niż i .

Zakres docelowy i poprawne indeksowanie

...range(k//10,k)...[i-k]

Po tym zestawie operacji pozostaje nam i , początkowe dane wejściowe i zmienna k, która reprezentuje najmniejszą moc 10 większą od i . W ten sposób jesteśmy w stanie wygenerować zakres (liczba całkowita) [floor (k / 10), k) , który zasadniczo obejmuje wszystkie liczby całkowite, które są:

• większa lub równa najwyższej mocy 10 mniejszej lub równej i
• mniej niż k , najmniejsza moc 10 większa od i

Ponieważ pomijamy liczby całkowite mniejsze niż x = floor (k / 10) , musimy przesunąć indeksowanie, aby uwzględnić brakujące liczby. Oczywistym sposobem jest odjęcie ich liczby x od i , abyśmy indeksowali się do listy (po sortowaniu, co opisano poniżej), a zatem ix . Jednakże, ponieważ lista zawiera 9K / 10 , pozycji i indeksowanie na liście w indeksie -y jakiegoś pozytywnego y daje pręd ^th element z końca w Pythonie, to jest po prostu odpowiednikiem indeksowania z ik , stąd oszczędność 4 bajty.

Sortowanie każdej porcji według cyfrowego katalogu głównego

sorted(...,key=lambda n:n%-9)

Wzór na funkcję cyfrowego pierwiastka to 1 + ((n-1) mod 9) (zobacz sekcję Wzór zgodności w tym artykule w Wikipedii ). Jako 1 będzie w ten sposób być dodawane do każdego z nich, to jest zbędne przy sortowaniu, więc jesteśmy w lewo z (n-1) mod 9 . Sposób działania %operatora Pythona, gdy podane są liczby ujemne na RHS, jest bardzo wygodny, ponieważ zamiast tego możemy użyć n pymod -9, aby zapisać jeszcze inny bajt.

Python 2 , 72 bajty

Zainspirowany poddaniem się Chasa Browna .

lambda i:sorted(range(1,10**len(`i`)),key=lambda n:(len(`n`),n%-9))[i-1]

Wypróbuj online!

Python 2 , 73 71 70 bajtów

lambda n:sorted(range(10**len(`n`)),key=lambda i:(len(`~i`),i%9))[n]+1

Wypróbuj online!

2 bajty dzięki panu XCoder ; i 1 bajt dzięki za H.PWiz .

To jest indeksowane na 0.

Galaretka ,  15 14 10  9 bajtów

D,Ḣ$‘Ḍḅ9’

Wypróbuj online!

W jaki sposób?

Korzysta z golfowej wersji rozwiązania w zamkniętej formie stworzonego przez ovs w odpowiedzi na Pythona ...

Wzór naświetlany przez ovs to: 9 * (n% b) + (n / b) + b - 1 gdzie b = 10 ^{piętro (log (n, 10))}

Teraz jeśli c jest liczbą cyfr dziesiętnych n, to b-1 jest c-1 dziewiątkami dziesiętnymi.
Jest to to samo, co dziewięciokrotność wartości c-1 w systemie dziesiętnym (np 111*9=999.).

Ponadto n / b jest cyfrą wiodącą n, a n% b jest resztą cyfr jako liczba dziesiętna.

Formuła taka jak b * x + y może być zaimplementowana jako konwersja [x,y]z podstawy b
(tj. B ^ 1 * x + b ^ 0 * y = b * x + y )

Jako taki możemy wziąć liczbę, n (na przykład7045 ), podzielić ją na cyfry wiodącą i końcową, umieszczając cyfrę wiodącą na końcu ( [[0,4,5],7]), dodać jedną do wszystkich cyfr pierwszego elementu, aby uwzględnić dodanie b-1 ( [[1,5,6],7]) konwertuje je z list dziesiętnych na liczby całkowite ( [156,7]) i konwertuje je z podstawy dziewięciu ( 1411).

W poniższej implementacji dodajemy jedną do wszystkich cyfr obu pozycji, uwzględniając catering b-1 ( [[0,4,5],8]), konwertujemy z list dziesiętnych na liczby całkowite ([156,8] ), konwertujemy z podstawy dziewiątej ( 1412), a następnie odejmujemy tę dodaną przez ten proces ( 1411).

D,Ḣ$‘Ḍḅ9’ - Link: positive integer, n    e.g. 4091
D         - to base ten                       [4, 0, 9, 1]
   $      - last two links as a monad:
  Ḣ       -   head (modifies the list too)    4
 ,        -   pair (the modified list) with   [[0, 9, 1], 4]
    ‘     - increment (vectorises)            [[1, 10, 2], 5]
     Ḍ    - from base ten (vectorises)        [202, 5] (since 1*10^2+10*10^1+2*10^0 = 100+100+2 = 202)  
      ḅ9  - convert from base 9               1823 (since 202*9^1 + 5*9^0 = 202*9 + 6*9 = 1818 + 5 = 1823)
        ’ - decrement                         1822

Poprzedni, 14 bajtów:

æċ⁵DL,’%9ƊƲÞị@

Wypróbuj online!

Ta buduje listę do następnej potęgi 10 powyżej wejścia, sortując te liczby naturalne, [digitalRoot, digitCount]a następnie znajduje wartość na wprowadzonym indeksie.

Haskell , 94 88 bajtów

([n|x<-[0..],i<-[1..9],n<-[10^x..10^(x+1)-1],until(<10)(sum.map(read.pure).show)n==i]!!)

Wypróbuj online! 0-indeksowane.

Wyjaśnienie:

Zrozumienie listy generuje sekwencję jako nieskończoną listę, w której indeksujemy !!:

• x jest o jeden mniej niż bieżąca liczba cyfr i pochodzi z nieskończonej listy [0,1,2,3, ...]
• iiteruje w zakresie od 1do 9i służy do sortowania według cyfrowych pierwiastków
• niteruje wszystkie x+1cyfry
• until(<10)(sum.map(read.pure).show)oblicza cyfrowy root ( zobacz wyjaśnienie tutaj )
• njest dodawany do listy, jeśli jego cyfrowy katalog główny jest równy i.

Siatkówka , 65 bajtów

.
9
.+
*
L$`
$`
O$`_(_{9})*(_*)
$2
_+
$.&
N$`
$.&
"$+L`^|\d+"^~G`

Wypróbuj online! 1-indeksowany. Wyjaśnienie:

.
9
.+
*
L$`
$`

Zbuduj listę linii _od 0 do następnej potęgi 10 (wyłącznie).

O$`_(_{9})*(_*)
$2

Posortuj je wszystkie w kolejności cyfrowej root.

_+
$.&

Konwertuj z unarnego na dziesiętny.

N$`
$.&

Sortuj je według długości.

"$+L`^|\d+"^~G`

Wyodrębnij nelement th.

Pyth ,  36 31 25 24 23  22 bajtów

1-indeksowany.

@o%tN9rFK^LThBlt`Q-QhK

Zestaw testowy!

Jak to działa (nieaktualne)

@smo%tN9dcU^TKhs.lQT^LTSK – Full program. Q = input.
             Khs.lQT      – Take floor(log10(Q))+1 and store it in K.
          U^T             – Generate [0 ... T^K).
         c                – Cut at locations...
                    ^LTSK – Of the powers of 10 less than K.
  m     d                 – Map over those.
   o  N                   – Sort them by...
    %t 9                  – Themselves decremented, modulo 9.
@s                        – Flatten the result and retrieve the Q'th entry.

05AB1E , 19 11 bajtów

Port mojej odpowiedzi w języku Python .

-6 bajtów (!) Dzięki Kevin Cruijssen .

g<°©‰`9*®O<

Wypróbuj online!

Code           Explanation            Stack
               implicit input         [n]
g              length                 [len(n)]
 <             decrement              [len(n)-1]
  °            10 ** a                [10**(len(n) - 1)]
   ©           store value            [10**(len(n) - 1)]
    ‰          divmod                 [[n // 10**(len(n) - 1), n % 10**(len(n) - 1)]]
     `         push items to stack    [n // 10**(len(n) - 1), n % 10**(len(n) - 1)]
      9*       multiply by 9          [n // 10**(len(n) - 1), n % 10**(len(n) - 1) * 9]
        ®      retrieve value         [n // 10**(len(n) - 1), n % 10**(len(n) - 1) * 9, 10**(len(n) - 1)]
         O     sum the stack          [n // 10**(len(n) - 1) + n % 10**(len(n) - 1) * 9 + 10**(len(n) - 1)]
          <    decrement              [n // 10**(len(n) - 1) + n % 10**(len(n) - 1) * 9 + 10**(len(n) - 1) - 1]
               implicit output

Pyth , 23 bajty

@o%tN9rF_mJ^TsdtBl`Q-QJ

Wypróbuj tutaj.

-3 dzięki Mr. Xcoder

1-indeksowany.

Perl 6 ,  68  58 bajtów

{({|(10**$++..^10**++$).sort({({.comb.sum}…*==*).tail})}…*)[$_]}

Przetestuj to w oparciu o 0

{sort({.chars,({.comb.sum}…*==*).tail},^10**.chars)[$_]}

Przetestuj to 1

Rozszerzony:

{  # bare block lambda with implicit parameter $_

  sort(
    {
      .chars,         # sort by the length first

      (  # generate sequence to find digital sum

        { .comb.sum } # one round of digital sum
        … * == *      # stop when the digital sum matches itself (1..9)

      ).tail          # get the last value
    },

    ^                 # Range up to (and excluding)
      10 ** .chars    # the next power of 10

  )[ $_ ] # index into the sequence
}

Rubinowy , 43 38 bajtów

->x{9*(x%b=10**~-x.to_s.size)+x/b+b-1}

Wypróbuj online!

Pierwotnie port doskonałej odpowiedzi Pythona przez ovs, a następnie nieco uprościł.

Java 8, 68 bajtów

n->{int b=(int)Math.pow(10,(n+"").length()-1);return~-b+n/b+n%b*9;}

Nudny port odpowiedzi @ovs na Python 2 , więc pamiętaj, aby go zagłosować!
-1 bajt dzięki @Jakob

Wypróbuj online.

K4 , 38 bajtów

Rozwiązanie:

-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:

Przykłady:

q)k)-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:40
13
q)k)-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:601
114
q)k)-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\:4051
1462

Wyjaśnienie:

Rozwiązanie rozwiązania Jonathana Allana, gdy zabrakło mi pamięci, budując cyfrowe korzenie od 1 do 1e9.

-1+9/:10/:'(0;c-1)_1_(1+c:#x)#x:1+10\: / the solution
                                  10\: / convert to base 10
                                1+     / add 1
                              x:       / save as x
                             #         / take from x
                     (      )          / do together
                          #x           / count x
                        c:             / save as c
                      1+               / add 1
                   1_                  / drop the first
                  _                    / cut at these indices
           ( ;   )                     / 2-item list
              c-1                      / length - 1
            0                          / .. zero
      10/:'                            / convert each from base 10
   9/:                                 / convert from base 9
-1+                                    / subtract 1

Premia:

Tłumaczenie rozwiązania ovs jest prostsze, ale dłuższe:

-1+b+/1 9*(_%;.q.mod).\:x,b:10 xexp#1_$x:

Galaretka , 19 bajtów

æḟ©ræċɗ⁵Ṗ%Þ-9⁸‘_®¤ị

Wypróbuj online!

-1 dzięki Mr. Xcoder .

1-indeksowany.

J, 24 bajty

(]/:([:+/[:".&>":)^:_"0)

To milczenie wyrażenie jest zawinięte w pareny, co oznacza, że ​​powinno być traktowane samo, a nie jako część dowolnego następnego wyrażenia (jak argumenty).

Wyrażenie „] /:” porządkuje (rosnąco ”/:”) oryginalną tablicę „]” sumą „+ /” cyfr Wyrażenie

". &> ":

konwertuje liczbę na wektor znaków za pomocą „”: ”, a następnie stosuje odwrotność„ ”. - znak na cyfrę - stosowany do każdego elementu „&>”. Zatem 65536 -> „65536” -> 6 5 5 3 6.

Koniunkcja potęgi „^:” pod koniec wyrażenia stosuje kod, który właśnie wyjaśniliśmy (po lewej) określoną liczbę razy. W tym przypadku podana liczba razy to nieskończoność „_”, co oznacza kontynuowanie stosowania, aż wynik przestanie się zmieniać.

Ostatnie „0” oznacza zastosowanie całego wyrażenia po lewej stronie do każdego skalarnego (0-wymiarowego) elementu po prawej stronie, który byłby tablicą liczb, do której chcemy to zastosować.

Eliksir , 239 bajtów

q=:math
e=Enum
r=fn x,f->cond do
x<10->x
1->f.(e.sum(Integer.digits x),f)end end
fn p->e.at(e.at(Stream.unfold({0,[0]},fn {a,c}->{c,{a+1,c++e.sort(trunc(q.pow 10,a)..trunc(q.pow 10,a+1)-1,&r.(&1,r)<=r.(&2,r))}}end),1+trunc q.log10 p),p)end

Wypróbuj online!

Wyjaśnienie przychodzące (powoli)! Nie sądzę, że może być znacznie krótszy, ale zawsze jestem otwarty na sugestie

Perl 5 -pF , 27 bajtów

$_=9x$#F+$_%10**$#F*9+$F[0]

Wypróbuj online!

Wykorzystuje formułę @ ovs i wyjaśnienia @ JonathanAllen, aby wymyślić ładny kompaktowy fragment kodu.