Primes em diferentes bases

17

Desafio:

Você recebe um número base 10. Para cada base, de 10 a contagem decrescente até a base 2:

  1. Pegue o número de entrada original como uma string de base 10 e remova quaisquer dígitos do número inválidos para a base.
  2. Interprete a sequência numérica resultante nessa base. Se isso der 1 ou 0, encerre todo o processo.
  3. Saída ou imprima seu maior fator primo, como número decimal.

A saída pode ser uma matriz dos maiores fatores primos.

Casos de amostra:

Entrada:

987654321

Resultado:

379721
10593529
1091
179
1493
293
19
7

Alternativamente:

[379721,10593529,1091,179,1493,293,19,7]

Isso imprime os maiores fatores primos de 987654321, 87654321 9 = 42374116 10 , 7654321 8 = 2054353 10 e assim sucessivamente até atingir 1 2 , onde para.

poi830
fonte
2
Não estou claro sobre o processo. Provavelmente eu poderia descobrir isso a partir do exemplo, mas você deve ter instruções claras para que isso não seja necessário. Então, convertemos para uma base inferior, removemos dígitos inválidos e imprimimos o maior fator primo? Em que base imprimimos esse fator? Em seguida, fazemos o mesmo processo com o maior fator primo e um fator base mais baixo? Ou fazemos isso com o número que fatoramos? Começamos com 10 ou 9?
Xnor
Bem vindo ao site!
DJMcMayhem
2
Tentei reescrever o desafio para torná-lo mais claro. Espero que seja isso que você pretendeu. Caso contrário, fique à vontade para alterá-lo.
Xnor
4
Acho que o passo de maior fator primordial adotado na operação principal é a conversão de base. Muitos idiomas fazem isso diretamente com um fator de fator interno incorporado, e o restante basicamente precisa fazer um segundo desafio separado. A conversão de base também é incorporada ou eliminada. Quando as operações são incorporadas, você espera que elas sejam um terreno bem trilhado para os golfistas, e de fato a fatoração e a conversão de base são. Ainda assim, é bom para um primeiro desafio, mas é preciso ter em mente a próxima vez.
Xnor
3
Alguma chance de isso ter sido inspirado no Google Code Jam?
Mego

Respostas:

6

Pitão, 25 bytes

sfTm>1PiFdC,.u-N`tYKrT1zK
                       z   get input as a string
            .u      rT1    cumulative reduce over [10,9,...,2]
              -N`tY        remove one minus the number (10,9,...) from the input
          C,       K    K  pair each step along the chain with corresponding base
   m                       map over [["987654321", 10],...]:
       iFd                   apply the base-conversion (splat over i)
      P                      prime factorization, smallest to largest
    >1                       take [the last element], or [] if empty (1 or 0)
 fT                        remove the []s from 0s or 1s
s                          join the one-element arrays together

Experimente aqui.

Maçaneta da porta
fonte
4

Pitão - 16 bytes

V_S9#ePi~-z`NhNB

Experimente online aqui .

Às vezes, existem algumas linhas em branco nas entradas sem todos os dígitos, deixe-me saber se isso é um problema.

Maltysen
fonte
4

MATL , 17 15 bytes

9:PQ"G@ZAYfXzX>

Isso leva o número como uma string com aspas, o que é permitido por padrão.

Experimente online!

Explicação

9:PQ     % Push array [10, 9, ..., 2]
"        % For each number in that array. These are the bases to be considered
  G      %   Push input. Forces for input to be taken implicitly first time
  @      %   Push current base
  ZA     %   Convert from that base to base 10, discarding non-valid digits
  Yf     %   Prime factors. Gives empty for input 1, and 0 for input 0
  Xz     %   Non-zero values. Gives empty if previous result was 0, or else
         %   leaves it as it was
  X>     %   Maximum of array. For empty input gives empty
         % Implicitly end for each
         % Implicitly display. Empty arrays are not displayed
Luis Mendo
fonte
Este gera um 0 no final de insumos não terminam em 1.
poi830
Para as entradas '98765432' e '98765' (exemplos aleatórios), ele gera os números corretos e depois 0 antes de terminar.
achou
11
@ poi830 Resolvido agora
Luis Mendo
1

Julia, 101 bytes

f(s,x=[],b=10)=(t=filter(c->c<=47+b,s))>"1"&&b>1?f(s,[x;maximum(keys(factor(parse(Int,t,b))))],b-1):x

Esta é uma função recursiva que aceita a entrada como uma sequência e retorna uma matriz.

Ungolfed:

function f(s, x=[], b=10)
    # Filter the string down to only the digits valid for base b
    t = filter(c -> c <= 47 + b, s)

    # If the filtered string isn't "1" or "0" and b is a valid base
    if t > "1" && b > 1
        # Call the function again, appending the maximum prime factor
        # of t in base b to the argument x and decrementing the base
        f(s, [x; maximum(keys(factor(parse(Int, t, b))))], b-1)
    else
        # Otherwise return the array
        x
    end
end
Alex A.
fonte
1

Mathematica, 83 bytes

FactorInteger[Select[IntegerDigits@#,#<a&]~FromDigits~a][[-1,1]]~Table~{a,10,2,-1}&

Função anônima, retorna uma lista. Não é tão complicado, para ser honesto.

LegionMammal978
fonte
0

Ruby, 120 bytes

Função recursiva, recebe a entrada como uma string.

f=->n,b=2{require'prime';i=n.tr([*b.to_s..?9].join,"").to_i(b)
b>10?[]:f[n,b+1]+[*i>1?Prime.prime_division(i).max[0]:p]}
Value Ink
fonte
11
Você pode salvar alguns bytes usando o -rprimesinalizador de linha de comando em vez de require.
Maçaneta
-rprimenão funciona para mim por alguma razão ...
Valor Ink
0

Pyke, 19 bytes, não-competitivo

(adicione a função splat_node)
DTAbPe
;1TtD=T`"":r

Experimente aqui!

Pega entrada entre aspas, sai com um erro.

Explicação (nova linha substituída por \ n):

D                    - Duplicate the first item on the stack (And get it from input first time)
 TAb                 - Convert input to base (whatever's in T, 10 default)
    Pe               - get the highest prime factor of the number
      \n;1           - print it out and get rid of it
          TtD=T      - T -= 1
               `"":  - input = input.replace(str(t), "")
                   r - GOTO start
Azul
fonte