Vertraute Zahlen

Sei xeine ganze Zahl einer beliebigen Basis, also Dein Array ihrer Ziffern. xist eine vertrauliche Zahl, wenn für alle nzwischen 1und die Länge von D:

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

Nehmen 349wir zum Beispiel die Zahl in der Basis 10. Wenn wir die Indizes für diese Zahl beschriften, haben wir Folgendes.

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

Ausgehend von der ersten Ziffer 1 + 3 = 4ergibt sich die nächste Ziffer. Dann haben wir mit der zweiten Ziffer 3 + 4 + 2 = 9die nächste Ziffer. Somit ist diese Nummer eine Vertrauensperson.

Berechnen Sie bei einer Ganzzahl mit einer Basis zwischen 1 und 62 alle Vertrauenspersonen für diese Basis und geben Sie eine durch Zeilenumbrüche getrennte Liste aus. Sie können davon ausgehen, dass es für eine bestimmte Basis eine begrenzte Anzahl von vertraulichen Zahlen gibt.

Verwenden Sie für Ziffern größer als 9 die Buchstaben A-Zund für Ziffern größer als Zdie Buchstaben a-z. Sie müssen sich keine Gedanken mehr über Ziffern machen z.

Sie müssen nicht in einer bestimmten Reihenfolge ausgegeben werden.

Beispiel Input:

16

Beispielausgabe:

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

Dies ist Codegolf, also gewinnt der kürzeste Code. Viel Glück!

(Vielen Dank an Zach, der bei der Formatierung geholfen und auf einige Probleme hingewiesen hat.)

Pyth, 38 Bytes

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

Probieren Sie es online aus: Demonstration

Erläuterung:

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 Bytes

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

Hierbei wird die folgende Beobachtung verwendet: In einer vertrauten Zahl ifolgt die Ziffer 2*i+1, außer i+1für die zweite Ziffer. Indem wir alle möglichen ersten Ziffern ausprobieren und weitere Ziffern hinzufügen, bis sie zu groß werden, können wir alle vertrauten Zahlen generieren.

Wir berechnen das der Zahl entsprechende Zeichen ials chr(48+i+(i>9)*7+i/36*6), wodurch es für die Intervalle in die Zahl, den Großbuchstaben oder den Großbuchstabenbereich verschoben wird 0-9, 10-35, 36-61.

Dann erhöhen wir idurch i+=i+1mit zwei Anpassungen. Um dies stattdessen i+=1nach der ersten Ziffer zu machen, fügen wir die iBedingung hinzu , sdass mehr als 1Zeichen vorhanden sind. Außerdem müssen wir vermeiden, dass Zahlen, die mit 0 beginnen, gedruckt werden, und dies gleichzeitig zulassen 0. Dazu machen wir einen Hack, der bewirkt i=0, dass die Bedingung i<nin der nächsten Schleife fehlschlägt, indem er hinzugefügt nwird. Dies geschieht durch Ersetzen 1durch n**0**i, welches Recht mit n**(0**i)welchem ​​gleich n**(i==0)oder gleichgesetzt wird n if i==0 else 1.

Python 3, 201 200 Bytes

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

Erläuterung

Die wichtigste Erkenntnis hier ist, dass Sie bei einer gegebenen Sequenz x(wie zum Beispiel [1,2,5]) den nächsten Term in der Sequenz mit erhalten können sum(x)+len(x), der 11in diesem Fall ( B) ergibt . Überprüfen Sie, ob dies kleiner ist als nund fügen Sie die erweiterte Sequenz zur Liste aller solcher Sequenzen hinzu (durch alle einzelnen Ziffern gesät).

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

So ordne ich Sequenzelemente Zeichen zu. Diese werden ''.joinzusammengefügt und dann durch Zeilenumbrüche getrennt gedruckt.

GS2, 44 Bytes

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

Es erzeugt die Zahlen in einer anderen Reihenfolge, aber die Problembeschreibung gibt nichts an, also mache ich es! Hier ist der Ausgang für den Eingang von 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

Hier sind die mnemonischen Entsprechungen für die Bytes:

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 Bytes

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

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

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#

Am Ende sind noch 0 und ein paar leere Arrays auf dem Stapel, sodass der Interpreter druckt 0.

Gawk, 111 Bytes

{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"

Für jede Startziffer von 1bis base-1werden die nächsten Ziffern berechnet, und obwohl diese niedriger als die Basis sind, haben wir immer noch eine vertraute Zahl. Berechnung der nächsten Ziffer beim Drucken. Endlich druckt 0.