Alle deine Basispalindrome gehören uns

20

Generieren Sie die Sequenznummer der Basen, in denen nsich ein Palindrom befindet ( OEIS A126071 ).

Im Einzelnen ist die Sequenz wie folgt definiert: Geben Sie eine Zahl ein n, drücken Sie sie in der Basis aaus a = 1,2, ..., n, und zählen Sie, wie viele dieser Ausdrücke palindrom sind. Unter "Palindrom" versteht man das Umkehren der Basisziffern ades Ausdrucks als atomare Einheiten (danke, @Martin Büttner ). Betrachten Sie als Beispiel n= 5:

  • a=1: der Ausdruck ist 11111: palindromisch
  • a=2: der Ausdruck ist 101: palindromisch
  • a=3: der Ausdruck ist 12: nicht palindromisch
  • a=4: der Ausdruck ist 11: palindromisch
  • a=5: der Ausdruck ist 10: nicht palindromisch

Daher ergibt sich für n=5ist 3. Beachten Sie, dass OEIS Basen 2, ..., n+1anstelle von 1, ..., n(danke, @beaker ) verwendet. Es ist äquivalent, weil die Ausdrücke in base 1und n+1immer palindrom sind.

Die ersten Werte der Sequenz sind

 1, 1, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 4, 4, 4, 2, 4, 5, ...

Die Eingabe ist eine positive Ganzzahl n . Die Ausgabe ist der erste nTerm der Sequenz.

Das Programm sollte theoretisch funktionieren (wenn genügend Zeit und Speicher vorhanden sind) n Einschränkungen , die durch Ihren Standarddatentyp in internen Berechnungen verursacht werden.

Alle Funktionen erlaubt. Die niedrigste Anzahl von Bytes gewinnt.

Luis Mendo
quelle
Related
Luis Mendo
1
Wenn es für jemanden hilfreich ist, ist es erwähnenswert, dass eine Zahl n auch in der Basis n-1 immer palindrom ist.
Computronium
Dies ist A126071
Titus

Antworten:

9

Pyth, 13 Bytes

mlf_ITjLdSdSQ

Die Kürze dieses IBefehls ist hauptsächlich auf den Befehl nvaluable " Invariant" zurückzuführen.

msf_ITjLdSdSQ       implicit: Q=input
m         d         map lambda d over
           SQ       Inclusive range 1 to Q
      jLdSd         Convert d to all the bases between 1 and d
  f                  filter lambda T:
   _IT                 is invariant under reverse
 l                  number that are invariant under reverse

Wenn Trueeine akzeptable Ausgabe für ist 1, msm_IjdkSdSQfunktioniert (12 Byte).

Probieren Sie es hier aus .

Lirtosiast
quelle
2
Siehe FryAmTheEggman Vorschlag zu verwenden , _I#anstatt f_IT(Ich bin nicht 100% sicher , es war vorhanden, aber es scheint gewesen zu sein ).
Jonathan Allan
7

Jelly, 14 Bytes

bR‘$µ=UP€S
RÇ€

Probieren Sie es online!

Nicht konkurrierende Version

Der Jelly-Interpreter hatte einen Fehler, der die Konvertierung in Unary unmöglich machte. Dies wurde nun behoben, sodass der folgende Code ( 12 Byte ) auch die vorliegende Aufgabe erfüllt.

bRµ=UP€S
RÇ€

Probieren Sie es online!

Wie es funktioniert

bR‘$µ=UP€S  Helper link. Argument: z

 R‘$        Apply range and increment, i.e., map z to [2, ..., z + 1].
            In the non-competing version R simply maps z to [1, ... z].
b           Convert z to each of the bases to the right.
    µ       Begin a new, monadic chain. Argument: base conversions
     =U     Compare the digits of each base with the reversed digits.
            = has depth 0, so [1,2,3]=[1,3,3] yields [1,0,1].
       P€   Take the product of the innermost arrays.
         S  Sum all resulting Booleans.


RÇ€         Main link. Argument: n

R           Yield [1, ..., n].
 ǀ         Apply the helper link to each.
Dennis
quelle
4

MATL , 19 20 Bytes

:"0@XK:Q"K@:YAtP=A+

Verwendet die aktuelle Version (10.1.0) , die älter als diese Herausforderung ist.

Probieren Sie es online aus !

Erläuterung

:            % vector [1,2,...,N], where "N" is implicit input
"            % for each number in that vector
  0          % push 0
  @          % push number 1,2,...N corresponding to current iteration, say "n" 
  XK         % copy n to clipboard
  :Q         % vector [2,3,...,n+1]
  "          % for each number "m" in that vector
    K        % push n
    @:       % vector [1,2,...,m]
    YA       % express n in base m with symbols 1,2,...,m
    tP       % duplicate and permute
    =A       % 1 if all entries are equal (palindrome), 0 otherwise
    +        % add that number
             % implicitly close the two loops and display stack contents
Luis Mendo
quelle
2

CJam, 20 Bytes

ri{)_,f{)b_W%=}1bp}/

Teste es hier.

Martin Ender
quelle
1

Haskell, 88 Bytes

a!b|a<b=[a]|1>0=mod a b:(div a b)!b
f n=[1+sum[1|x<-[2..y],y!x==reverse(y!x)]|y<-[1..n]]
Damien
quelle
1

ES6, 149 Bytes

n=>[...Array(n)].map((_,i)=>[...Array(i)].reduce((c,_,j)=>c+(''+(a=q(i+1,j+2,[]))==''+a.reverse()),1),q=(n,b,d)=>n<b?[n,...d]:q(n/b|0,b,[n%b,...d]))

Funktioniert auch für Basen> 36.

Neil
quelle
1

JavaScript (ES6), 105 bis 95 Byte

f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]

Erläuterung

Nimmt eine Zahl von 1 bis 36 (die Beschränkung der Basiskonvertierung in JavaScript) und gibt ein Array der Sequenz zurück.

Rekursive Funktion, die nach Palindromen sucht, wenn eine Basis übergeben wird, andernfalls wird die Sequenz zurückgegeben, wenn nur übergeben nwird.

f=(n,b)=>

  // Base palindrome checking
  b?
    b<3?1:                 // return 1 for base-1, since toString(2)
    f(n,b-1)+(             // return the sum of all lower bases and check  this
      [...s=n.toString(b)] // s = n in base b
      .reverse().join``==s // add 1 if it is a palindrome
    )

  // Sequence generation
  :
    n<2?[1]:               // return 1 for the first value of the sequence
    [...f(n-1),f(n,n)]     // return the value for n after the previous values

Prüfung

var solution = f=(n,b)=>b?b<2?1:f(n,b-1)+([...s=n.toString(b)].reverse().join``==s):n<2?[1]:[...f(n-1),f(n,n)]
<input type="number" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>

user81655
quelle
Gibt es eine Möglichkeit, dies in eine rekursive Funktion umzuwandeln? Ich glaube, das könnte ein paar Bytes sparen.
Mama Fun Roll
@ ՊՓԼՃՐՊՃՈԲՍԼ Du hast recht. Danke für den Tipp.
user81655
1

PHP, 73 + 1 Bytes

while(++$i<$argn)$c+=strrev($n=base_convert($argn,10,$i+1))==$n;echo$c+1;

arbeitet für Basen 1zu 36. Laufen Sie als Pipe mit -nRoder versuchen Sie es online .

Titus
quelle
1

PHP, 92 + 1 Bytes:

for($b=$c=1;$b++<$n=$argn;$c+=$a==array_reverse($a))for($a=[];~~$n;$n/=$b)$a[]=$n%$b;echo$c;

funktioniert für alle Basen. Laufen Sie als Pipe mit -nRoder versuchen Sie es online .

Titus
quelle
1

Python 2, 97 Bytes

c=1;n=int(input())
for b in range(2,n):
	a=[];z=n
	while z:a+=[z%b];z//=b
	c+=a[::-1]==a
print c

Mein erster Python-Beitrag, eigentlich mein erster Python-Code überhaupt
hat wahrscheinlich etwas Golfpotential.

Probieren Sie es online!

Titus
quelle
1

> <> 197 + 2 Bytes

+2 für -v Flag

:1+0v    ;n\
1\  \$:@2(?/
:<~$/?)}:{:*}}@:{{
\   \~0${:}
>$:@1(?\::4[:&r&r]:$&@@&%:&@&$@-$,5[1+{]$~{{:@}}$@,$
~~1 \  \
?\~0>$:@2(?\$1-:@3+[}]4[}1-]=
 \  /@@r/!?/
r@+1/)0:<
  /?/$-1$~<
~$/       \-1

tio.run scheint keine Ausgabe für n> 1 zurückzugeben, Sie können dies jedoch unter https://fishlanguage.com überprüfen . Die Eingabe erfolgt im Feld "Initial Stack".

Sasha
quelle
1

Japt , 10 Bytes

õ_õ!ìZ èêS

Versuch es


Erläuterung

õ              :Range [1,input]
 _             :Map each Z
  õ            :  Range [1,Z] (let's call each X)
   !ìZ         :   Convert Z to a base X digit array
       è       :  Count
        êS     :   Palindromes
Zottelig
quelle
1
õ_õ hahaha nice emoji
Luis Felipe De Jesus Munoz
1

Python 2 , 85 Bytes

def f(a):b,c=2,0;exec'd,m=[],a\nwhile m:d+=[m%b];m/=b\nc+=d[::-1]==d;b+=1;'*a;print c

Probieren Sie es online!

Erwartet eine Ganzzahl als Argument.

Erläuterung:

# named function
def f(a):
    # initialize variable to track base (b) and to track palindromes (c)
    b,c=2,0
        # construct code
        '
        # initialize variable to store remainders (m) and to track divisor (d)
        m,d=[],a
        # while d is not zero,
        # add the current remainder to the array
        # and divide d by the base and assign the result back to d
        while d:m+=[m%b];d/=b
        # False == 0 and True == 1, so add 1 to total if m == reversed(m)
        c+=m[::-1]==m;
        # increment base
        # terminate with ; so that next statement can be executed separately
        b+=1;
        '
    # execute constructed statement (a) times
    exec'....................................................'*a
    # print result
    print c
Triggernometrie
quelle