Toda a sua base palindrômica nos pertence

20

Gere o número den sequência de bases em que é um palíndromo ( OEIS A126071 ).

Especificamente, a sequência é definida da seguinte forma: dado um número n, expresse-o na base ade a = 1,2, ..., ne conte quantas dessas expressões são palindrômicas. "Palindrômico" é entendido em termos de reversão dos adígitos básicos da expressão como unidades atômicas (obrigado, @Martin Büttner ). Como exemplo, considere n= 5:

  • a=1: a expressão é 11111: palindrômico
  • a=2: a expressão é 101: palindrômico
  • a=3: a expressão é 12: não palindrômica
  • a=4: a expressão é 11: palindrômico
  • a=5: a expressão é 10: não palindrômica

Portanto, o resultado para n=5é 3. Observe que o OEIS usa bases em 2, ..., n+1vez de 1, ..., n(obrigado, @beaker ). É equivalente, porque as expressões na base 1e n+1são sempre palindrômicas.

Os primeiros valores da sequência são

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

A entrada é um número inteiro positivo n. Saída são os primeiros ntermos da sequência.

Teoricamente, o programa deve funcionar (com tempo e memória suficientes) para quaisquer nlimitações causadas pelo seu tipo de dados padrão em qualquer cálculo interno.

Todas as funções são permitidas. O menor número de bytes vence.

Luis Mendo
fonte
Relacionado
Luis Mendo
1
Se é útil para alguém, vale a pena notar que um número n também é sempre palindrômico na base n-1.
Computronium
Este é A126071
Titus

Respostas:

9

Pitão, 13 bytes

mlf_ITjLdSdSQ

A brevidade disso se deve principalmente ao comando Iinestimável " Invariant".

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

Se Trueé uma saída aceitável para 1, msm_IjdkSdSQ(12 bytes) funciona.

Experimente aqui .

lirtosiast
fonte
2
Veja a sugestão de FryAmTheEggman para usar em _I#vez de f_IT(não tenho 100% de certeza de que estava disponível, mas parece ter sido ).
Jonathan Allan
7

Gelatina, 14 bytes

bR‘$µ=UP€S
RÇ€

Experimente online!

Versão não concorrente

O intérprete Jelly tinha um bug que tornava impossível a conversão para unário. Como foi corrigido agora, o código a seguir ( 12 bytes ) também realiza a tarefa em questão.

bRµ=UP€S
RÇ€

Experimente online!

Como funciona

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
fonte
4

MATL , 19 20 bytes

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

Usa a versão atual (10.1.0) , anterior a esse desafio.

Experimente online !

Explicação

:            % 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
fonte
2

CJam, 20 bytes

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

Teste aqui.

Martin Ender
fonte
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
fonte
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]))

Também funciona para bases> 36.

Neil
fonte
1

JavaScript (ES6), 105 95 bytes

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

Explicação

Pega um número de 1 a 36 (a limitação da conversão de base em JavaScript) e retorna uma matriz da sequência.

Função recursiva que verifica se há palíndromos quando uma base é passada, senão retorna a sequência se apenas nfor passada.

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

Teste

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
fonte
Existe uma maneira de transformar isso em uma função recursiva? Eu sinto que isso poderia economizar alguns bytes.
Mama Fun Roll
@ ՊՓԼՃՐՊՃՈԲՍԼ Você está certo. Obrigado pela dica.
user81655
1

PHP, 73 + 1 bytes

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

trabalha para bases 1para 36. Execute como pipe -nRou experimente online .

Titus
fonte
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;

funciona para todas as bases. Execute como pipe -nRou experimente online .

Titus
fonte
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

Meu primeiro post em Python, na verdade, meu primeiro código em Python
provavelmente tem algum potencial de golfe.

Experimente online!

Titus
fonte
1

> <>, 197 + 2 bytes

+2 para sinalizador -v

: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 parece não retornar nenhuma saída para n> 1, mas você pode verificá-la em https://fishlanguage.com . A entrada entra na caixa "Pilha inicial".

Sasha
fonte
1

Japonês , 10 bytes

õ_õ!ìZ èêS

Tente


Explicação

õ              :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
Shaggy
fonte
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

Experimente online!

Espera um número inteiro como argumento.

Explicação:

# 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
Triggernometria
fonte