Ravenity of Cube Distance Numbers

15

Inspirado por esta entrada Numberphile

fundo

Os números de distância do cubo de um número inteiro n são definidos aqui como o conjunto de números inteiros que estão a distância de para um dado x . Para um exemplo simples, com n=100e x=2, os números da distância do cubo são {92,108}.

Isso pode ser estendido para um conjunto maior simplesmente variando x . Com x ∈ {1,2,3,4}o mesmo n=100, temos o conjunto resultante {36,73,92,99,101,108,127,164}.

Vamos definir CD (n, x) como o conjunto de todos os números inteiros n ± z³com z ∈ {1,2,3,...,x}.

Agora, podemos nos concentrar em algumas das propriedades especiais desses números de distância do cubo . Das muitas propriedades especiais que os números podem ter, as duas propriedades nas quais estamos interessados ​​aqui são primalidade e divisores primos .

Para o exemplo acima CD (100,4) , observe que 73, 101, 127todos são primos. Se removermos aqueles do conjunto, ficaremos com {36,92,99,108,164}. Todos os divisores primos desses números são (em ordem) {2,2,3,3,2,2,23,3,3,11,2,2,3,3,3,2,2,41}, o que significa que temos 5 divisores primos distintos {2,3,23,11,41}. Podemos, portanto, definir que o CD (100,4) possui voracidade 1 de 5.

O desafio aqui é escrever uma função ou programa, no menor número de bytes, que produza a voracidade de uma determinada entrada.

Entrada

  • Dois números inteiros positivos ne x, em qualquer formato conveniente.

Resultado

  • Um único número inteiro que descreve a intensidade dos dois números de entrada, quando calculado com CD (n, x) .

Regras

  • A entrada / saída pode ser feita através de qualquer método adequado .
  • Aplicam-se restrições de brecha padrão .
  • Para facilitar o cálculo, você pode assumir que os dados de entrada serão tais que o CD (n, x) terá apenas números positivos no conjunto (ou seja, nenhum CD (n, x) terá números negativos ou zero).
  • A função ou o programa deve poder manipular números de entrada para que n + x³se encaixem no tipo de dados inteiro nativo do seu idioma. Por exemplo, para um tipo inteiro assinado de 32 bits, todos os números de entrada com n + x³ < 2147483648são possíveis.

Exemplos

n,x   - output
2,1   - 0   (since CD(2,1)={1,3}, distinct prime divisors={}, ravenity=0)
5,1   - 2
100,4 - 5
720,6 - 11

Notas de rodapé

1 - Assim nomeado porque não estamos interessados ​​na cardinalidade do conjunto, mas em um tipo diferente de pássaro. Como estamos lidando com divisores "comuns", escolhi usar o corvo comum .

AdmBorkBork
fonte
Como é que 100,4rende 5? Os números da distância do cubo desse conjunto são 36,164e os principais fatores desse conjunto são 2,3,41(já que os fatores desse conjunto são {2, 3, 4, 6, 9, 12, 18, 36}e {2, 4, 41, 82, 164}, respectivamente). Portanto, a saída deve ser de 3, não 5.
R. Kap
2
@ R.Kap 100,4é o exemplo que o OP explica na seção Background. Seu erro parece ser que você deveria considerar tudo 1..x, então, [1,2,3,4]neste caso.
FryAmTheEggman #
@FryAmTheEggman Oh. OK. Agora eu entendi.
R. Kap
Seria pronunciado [ruh-VEE-nuh-tee] (ou / rəˈviːnəti / para aqueles que lêem IPA)?
gotejante Nun
1
@KennyLau Na minha cabeça, eu o pronunciei como "rah-VIN-eh-ty"
AdmBorkBork 04/04

Respostas:

4

Gelatina, 16 bytes

ŒRḟ0*3+µÆfFœ-µQL

Aceita x e n como argumentos de linha de comando, nessa ordem. Experimente online!

Como funciona

ŒRḟ0*3+µÆfFœ-µQL  Main link. Arguments, x, n

ŒR                Range; yield [-x, ..., x].
  ḟ0              Filter out 0.
    *3            Cube each remaining integer.
      +           Add n to all cubes.
       µ          Begin a new, monadic link. Argument: A (list of sums)
        Æf        Factorize each k in A.
          F       Flatten the resulting, nested list.
           œ-     Perform multiset difference with A.
                  If k in A is prime, Æf returns [k], adding on k too many to the
                  flat list. Multiset difference with A removes exactly one k from
                  the results, thus getting rid of primes.
                  If k is composite (or 1), it cannot appear in the primes in the
                  flat list, so subtracting it does nothing.
             µ    Begin a new, monadic link. Argument: D (list of prime divisors)
              Q   Unique; deduplicate D.
               L  Compute the length of the result.
Dennis
fonte
4

Pitão - 21 19 18 bytes

Gostaria de saber se há um truque.

l{st#mP+Q^d3s_BMSE

Conjunto de Teste .

l                   Length
 {                  Uniquify
  s                 Combine divisor lists
   t#               Filter by if more than one element
     PM             Take prime factorization of each number
       +RQ          Add each num in list to input
          s_BM      Each num in list and its negative (with bifurcate)
              ^R3   Cube each num in list
                 SE Inclusive unary range - [1, 2, 3,... n] to input
Maltysen
fonte
3

Julia, 107 bytes

f(n,x)=endof(∪(foldl(vcat,map(k->[keys(factor(k))...],filter(i->!isprime(i),[n+z^3for z=[-x:-1;1:x]])))))

Esta é uma função que aceita dois números inteiros e retorna um número inteiro.

Ungolfed:

function f(n, x)
    # Get all cube distance numbers
    cubedist = [n + z^3 for z = [-x:-1; 1:x]]

    # Filter out the primes and zeros
    noprimes = filter(i -> !isprime(i) && i > 0, cubedist)

    # Factor each remaining number
    factors = map(k -> [keys(factor(k))...], noprimes)

    # Flatten the list of factors
    flat = foldl(vcat, factors)

    # Return the number of unique elements
    return endof(∪(flat))
end
Alex A.
fonte
A especificação foi atualizada; você não precisa mais se preocupar com o zero .
Dennis
@ Dennis Nice, obrigado pela atenção.
Alex A.
2

05AB1E , 20 19 bytes

Código:

L3mD(«-Dp_Ïvyf`})Úg

Entrada na forma x, n. Usa CP-1252 codificação .

Experimente online!

Adnan
fonte
2

MATL , 21 bytes

:3^t_h+tZp~)"@Yf!]vun

De entrada é x, nseparados por uma nova linha.

Experimente online!

Explicação

:       % take n implicitly. Generate [1,2,...,n]
3^      % raise to 3, element-wise
t_h     % duplicate, negate, concatenate horizontally: [1,2,...,n,-1,2,...-n]
+       % take x implicitly. Add to that array
t       % duplicate
Zp      % array that contains true for primes
~       % logical negate
)       % apply index to keep only non-primes
"       % for each number in that array
  @     %   push that number
  Yf!   %   prime factors, as a column array
]       % end for each
v       % concatenate vertically all factors
u       % remove repeated factors
n       % number of elements of that array. Implicitly display
Luis Mendo
fonte
2

J, 30 bytes

#@~.@(,@:q:-.0&,)@:+(|#^&3)@i:

Este é um verbo diádico, usado da seguinte maneira:

   f =: #@~.@(,@:q:-.0&,)@:+(|#^&3)@i:
   100 f 4
5

Experimente aqui.

Explicação

#@~.@(,@:q:-.0&,)@:+(|#^&3)@i:
                            i:  Range from -x to x
                    (     )@    Apply this verb to the range:
                       ^&3        a) every item cubed
                     |            b) absolute value of every item
                      #           c) every item in a) repeated b) times; this removes 0
                                     and produces some harmless duplication
                   +            Add n to every element of the resulting list
     (          )@:             Apply this verb to the resulting vector:
             0&,                  a) the vector with 0 appended
      ,@:q:                       b) flat list of prime divisors in the vector
                                     (and some extra 0s since we flatten an un-even matrix)
           -.                     c) list b) with elements of a) removed; this gets rid of
                                     the extra 0s and all primes that were in the list
#@~.@                           Remove duplicates and take length
Zgarb
fonte
2
@:+(por que tão triste, cara de cabelo incrível?
AdmBorkBork
Link para o TIO em resposta, por favor?
Rɪᴋᴇʀ
@EasterlyIrk O TIO não tem J. Vou adicionar um link para tryj.tk.
Zgarb 01/04
@Zgarb okai .___
Aug
2

Python 3.5, 218 198 bytes:

( Obrigado ao @Blue por me salvar 20 bytes.)

lambda r,n:len({z for z in{v for f in{t for u in[[r-q**3,r+q**3]for q in range(1,n+1)]for t in u if any(t%g<1 for g in range(2,t))}for v in range(2,f)if f%v<1}if all(z%g>0 for g in range(2,z))})

Uma boa função lambda de uma linha, embora possa ser um pouco longa. Desde que eu estava usando Python, tive que criar minha própria maneira de encontrar os compostos para o primeiro passo e, em seguida, os divisores principais para o último passo, por isso não foi muito fácil, e esse foi o mais curto por mim . poderia fazê-lo. No entanto, ele faz o que precisa e tenho orgulho disso. :) No entanto, todas as dicas para jogar um pouco mais são bem-vindas.

R. Kap
fonte
Algumas coisas: não use == 0, use <1 e para! = 0,> 0. Além disso, por que z% 1 e z% z no final? Parece que eles sempre serão verdadeiros.
Azul
@ Blue Sim, você está certo. Eles sempre serão verdadeiros, de modo que essa parte nem é necessária. Então, eu vou remover isso. E também, obrigado por essas outras dicas! :)
R. Kap
1

PARI / GP , 79 bytes

(n,x)->omega(factorback(select(k->!isprime(k),vector(2*x,i,n+(i-(i<=x)-x)^3))))

Aqui está minha implementação direta original. A versão otimizada acima combina os dois vetores em um único vetor um pouco mais complicado.

(n,x)->omega(factorback(select(k->!isprime(k),concat(vector(x,i,n-i^3),vector(x,i,n+i^3)))))
Charles
fonte
Isso é realmente interessante. Vejo que há um link no navegador para experimentar o código, mas não sei como enviar a entrada. Você pode fornecer uma explicação?
AdmBorkBork
@ TimmyD: Se você atribuir um dos itens acima a f(like f=(n,x)->...), poderá testá-lo com f(100,4). Como alternativa, você pode invocá-lo em uma linha com ((n,x)->...)(100,4).
Charles
1

Ruby, 138 bytes

->(n,x){require'prime'
v=((-x..x).to_a-[0]).map{|i|n+i**3}.reject{|e|Prime.prime?(e)}
Prime.each(v[-1]).select{|i|v.any?{|e|e%i==0}}.size}

Foi um trocadilho y desafio. :-)

jose_castro_arnaud
fonte
Eles realmente construíram uma maneira de encontrar primos em Ruby? Uau ... Não acredito que o Python não tem isso.
R. Kap
Sim. Consulte ruby-doc.org/stdlib-2.3.0/libdoc/prime/rdoc/Prime.html - Deve funcionar mesmo na versão 1.9.3.
Jose_castro_arnaud
1

Ruby, 132 120 114 bytes

Estou ciente de que esta solução ainda precisa de muito golfe. Quaisquer dicas de golfe são bem-vindas.

require'prime'
->n,x{(-x..x).map{|i|j=n+i**3;j.prime?||(j==n)?[]:j.prime_division.map{|z|z[0]}}.flatten.uniq.size}

Ungolfing:

require 'prime'

def ravenity(n, x)
  z = []
  (-x..x).each do |i|
    j = n + i**3
    m = j.prime_division
    if j.prime? || j == n
      z << []
    else
      z << m.map{|q| q[0]}
    end
  return z.flatten.uniq.size
end
Sherlock9
fonte
1

Python 3.5 - 177 175 159 bytes

Qualquer dica de golfe bem-vindo :)

a=range
p=lambda n:any(n%x<1for x in a(2,n))
r=lambda n,x:len(set(sum([[x for x in a(2,z+1)if z%x<1&1>p(x)]for z in filter(p,[n+z**3for z in a(-x,x+1)])],[])))

Ungolfed:

def is_composite(n):
    return any(n % x == 0 for x in range(2, n))

def prime_factors(n):
    return {x for x in range(2, n+1) if n % x == 0 and not is_composite(x)}

def ravenity(n, x):
    nums = [n + z**3 for z in range(-x, x+1)]
    nums = filter(is_composite, nums)
    factors = map(prime_factors, nums)
    factors = sum(factors, [])
    #remove duplicates
    factors = set(factors)
    return len(factors)
Tuomas Laakkonen
fonte
0

Wolfram Language (Mathematica) , 90 bytes

Tr[1^Union[First/@Join@@FactorInteger/@Select[z=Range@#2^3;Join@@{#-z,#+z},Not@*PrimeQ]]]&

Experimente online!

sem golfe: o código é lido principalmente da direita para a esquerda,

F[n_, x_] := 
  Length[Union[                                        (* number of unique elements   *)
    First /@                                           (* drop multiplicities         *)
      Join @@                                          (* join all prime factor lists *)
        FactorInteger /@                               (* compute prime factors       *)
          Select[                                      (* select those...             *)
            Join @@ {n - Range[x]^3, n + Range[x]^3},  (* ...candidates...            *)
            Not@*PrimeQ]]]                             (* ...that are not prime       *)
romano
fonte