Numery powiernicze

Niech xbędzie liczbą całkowitą dowolnej podstawy, taką Djak tablica jego cyfr. xjest liczbą powierniczą, jeżeli dla wszystkich nmiędzy 1i na długości D:

D[n+1] = D[n] + D[n-1] + ... + D[1] + n

Weźmy na przykład liczbę 349z podstawy 10. Jeśli oznaczymy wskaźniki dla tego numeru, mamy następujące.

Index    Digit
-----    -----
1        3
2        4
3        9

Począwszy od pierwszej cyfry, mamy 1 + 3 = 4, co daje następną cyfrę. Następnie z drugą cyfrą mamy 3 + 4 + 2 = 9, co znowu daje następną cyfrę. Tak więc liczba ta jest liczbą zaufaną.

Biorąc pod uwagę liczbę całkowitą o podstawie między 1 a 62, oblicz wszystkie liczby ufające dla tej podstawy i wyślij ich listę, oddzieloną znakami nowej linii. Możesz założyć, że dla danej bazy istnieje skończona liczba liczb powierniczych.

Dla cyfr większych niż 9 użyj znaków alfanumerycznych A-Z, a dla cyfr większych niż Zużyj znaków alfanumerycznych a-z. Nie musisz się martwić o cyfry poza nimi z.

Nie muszą być wyprowadzane w określonej kolejności.

Przykładowe dane wejściowe:

16

Przykładowe dane wyjściowe:

0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
12
23
34
45
56
67
78
89
9A
AB
BC
CD
DE
EF
125
237
349
45B
56D
67F
125B
237F

To jest kod golfowy, więc wygrywa najkrótszy kod. Powodzenia!

(Dzięki Zach za pomoc w formatowaniu i wskazanie kilku problemów.)

Pyth, 38 bajtów

0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ

Wypróbuj online: demonstracja

Wyjaśnienie:

0jms@L+s`MT+rG1Gdf<eTQsm.u+N+lNsNQ]dSQ  implicit: Q = input base
0                                       print 0
                       m            SQ  map each d of [1, 2, ..., Q] to:
                        .u       Q]d      start with N=[d], apply v Q times
                          +N+lNsN           add (len(N) + sum(N)) to N
                                          gives all intermediate results
                      s                 join to one list of candidates
                 f<eTQ                  filter those, where every digit < Q
  ms@L+s`MT+rG1Gd                       convert numbers to letters 0-9A-Za-z
 j                                      print each on separate line

Python 2, 104 bajty

n=input()
for i in range(n):
 s=''
 while i<n:s+=chr(48+i+(i>9)*7+i/36*6);print s;i+=n**0**i+i*(s>s[:1])

Wykorzystuje następujące spostrzeżenie: w wielu powiernikiem, cyfra inastępuje 2*i+1, z wyjątkiem, że to i+1zamiast do drugiej cyfry. Próbując wszystkich możliwych pierwszych cyfr i dodając więcej cyfr, aż staną się zbyt duże, możemy wygenerować wszystkie liczby ufające.

Obliczamy znak odpowiadający liczbie ijako chr(48+i+(i>9)*7+i/36*6), która przesuwa go do liczby, wielkiej lub wielkiej litery dla przedziałów 0-9, 10-35, 36-61.

Następnie zwiększamy iza i+=i+1pomocą dwóch korekt. Aby uczynić to zamiast i+=1po pierwszej cyfrze, dodajemy iwarunek sposiadania więcej niż 1znaków. Musimy również unikać drukowania liczb rozpoczynających się od 0, jednocześnie pozwalając 0. Aby to zrobić, wykonujemy hack, który powoduje i=0błąd warunku i<nw następnej pętli poprzez dodanie ndo niego. Odbywa się to poprzez zastąpienie 1z n**0**i, co prawym Associates n**(0**i), która jest równa n**(i==0)lub n if i==0 else 1.

Python 3, 201 200 bajtów

n=int(input())
X=[[i]for i in range(1,n)]
for x in X:
 y=sum(x)+len(x)
 if y<n:X.append(x+[y])
X=[[0]]+X
print('\n'.join(''.join(map(lambda x:[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)],x))for x in X))

Wyjaśnienie

Kluczowym wglądem tutaj jest to, że biorąc pod uwagę sekwencję x(np. Powiedzmy [1,2,5]), możesz uzyskać następny termin w sekwencji z sum(x)+len(x), co daje 11w tym przypadku ( B). Sprawdź, czy jest to mniej niż n, a jeśli tak, dodaj rozszerzoną sekwencję do listy wszystkich takich sekwencji (zaszczepionych wszystkimi pojedynczymi cyframi).

[str(x),chr(x+55),chr(x+61)][(x>9)+(x>35)]

W ten sposób mapuję elementy sekwencji na postacie. Są one ''.joinedytowane razem, a następnie drukowane, oddzielane znakami nowej linii.

GS2, 44 bajty

26 c8 2f 08 4d 08 40 64 45 2e 30 42 67 40 24 d0
75 d3 20 e1 35 09 cb 20 23 78 22 09 34 30 e0 32
08 86 84 30 85 30 92 58 09 34 10

Tworzy liczby w innej kolejności, ale opis problemu nie określa, więc idę po to! Oto wynik dla wejścia 16.

1
12
125
125B
2
23
237
237F
3
34
349
4
45
45B
5
56
56D
6
67
67F
7
78
8
89
9
9A
A
AB
B
BC
C
CD
D
DE
E
EF
F
0

Oto mnemoniczne odpowiedniki bajtów:

read-num dec save-a
range1
{
    itemize
    {
        dup 
        sum
        over length
        add

        swap right-cons

        dup last push-a le

            push-d eval
        block2 when
    }
    save-d eval
    init inits tail
} map

+ ' fold 

{
    ascii-digits
    uppercase-alphabet catenate
    lowercase-alphabet catenate
    select 
    show-line
} map

0

CJam, 46 42 40 bajtów

ri:R,{Q{+_A,s'[,_el^+f=oNo__,+:+_R<}g&}*

Wypróbuj online w interpretatorze CJam .

Jak to działa

ri:R            e# Read an integer from STDIN and save it in R.
,               e# Push [0 ... R-1].
{               e# Fold; For each element but the first:
                e#   Push the element.
  Q             e#   Push an empty array (accumulator for base-R digits).
  {             e#   Do:
    +           e#     Concatenate the integer and the array on the stack.
    _           e#     Push a copy of the result.
    A,s'[,_el^+ e#     Push "0...0A...Za...z".
                e#     See: http://codegolf.stackexchange.com/a/54348
    f=          e#     Replace each base-R digit with the corresponding character.
    oNo         e#     Print the resulting string and a linefeed.
    _           e#     Push another copy of the accumulator.
    _,+         e#     Append its length to it.
    :+          e#     Add all digits (including the length).
    _R<         e#     Push a copy of the result and compare it with R.
  }g            e#   If the sum is less than R, it is a valid base-R digit,
                e#   the comparison pushes 1, and the loop is repeated.
  &             e#   Intersect the accumulator with an integer that is greater
                e#   or equal to R. This pushes an empty array.
}*              e#

Na końcu 0 i kilka pustych tablic pozostaje na stosie, więc interpreter drukuje 0.

gawk, 111 bajtów

{for(n=$0;n>c=++i;)for(j=0;n>$++j=c+=j;print"")for(c=k=0;k++<j;c+=$k)printf"%c",$k+($k>9?$k>35?61:55:48)}$0="0"

Dla każdej cyfry początkowej od 1do base-1niej obliczane są kolejne cyfry, a chociaż są one niższe niż podstawa, nadal mamy liczbę powierniczą. Obliczanie następnej cyfry podczas drukowania. Wreszcie drukuje 0.