_{(via chat )}

A entrada OEIS A123321 lista a sequência de números que são o produto de sete primos distintos. Por uma questão de brevidade, chamaremos esse número de 7DP . Os primeiros números e seus divisores correspondentes estão abaixo:

510510 = 2 * 3 * 5 * 7 * 11 * 13 * 17
570570 = 2 * 3 * 5 * 7 * 11 * 13 * 19
690690 = 2 * 3 * 5 * 7 * 11 * 13 * 23
746130 = 2 * 3 * 5 * 7 * 11 * 17 * 19

O desafio aqui será encontrar o número 7DP mais próximo, em termos de distância absoluta, de uma determinada entrada.

Entrada

Um único número inteiro positivo n em qualquer formato conveniente .

Resultado

O número 7DP mais próximo de n , novamente em qualquer formato conveniente. Se dois números 7DP estiverem vinculados ao mais próximo, você poderá gerar um ou ambos.

Regras

• Pode-se presumir que os números se encaixam no [int]tipo de dados padrão do seu idioma (ou equivalente).
• Um programa completo ou uma função são aceitáveis.
• As brechas padrão são proibidas.
• Isso é código-golfe , portanto todas as regras usuais de golfe se aplicam e o código mais curto vence.

Exemplos

5 -> 510510
860782 -> 870870
1425060 -> 1438710 (or 1411410, or both)

Python, 89 86 85 bytes

f=lambda n,k=0:126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))and f(n+k,k%2*2+~k)or n

O algoritmo é O (assustador) e a recursão não ajuda muito, mas funciona bem desde que n seja suficientemente próximo de um número 7DP.

Graças a @xnor por jogar fora 3 bytes!

Testá-lo em repl.it .

Como funciona

O Python não possui embutidos de primalidade ou fatoração, mas podemos identificar os números 7DP pela quantidade e natureza de seus divisores.

Pelo princípio da multiplicação, o número de divisores de um número inteiro pode ser calculado como o produto dos expoentes incrementados de sua fatoração primária. Assim, σ ₀ (n) ( função divisora ) é 2 ^m sempre que n é um número mDP.

σ ₀ (n) = 128 é, portanto, uma condição necessária, mas não é suficiente; por exemplo, σ ₀ (2 ¹²⁷ ) = 128 , mas 2 ¹²⁷ claramente não é um número 7DP. No entanto, se ambos σ ₀ (n) = 128 e nenhum quadrado perfeito divide n uniformemente, então n é um número 7DP.

Para a entrada n , o algoritmo consiste em inspecionar os números inteiros n , n - 1 , n + 1 , n - 2 , n + 2 , etc. e retornar o primeiro número 7DP.

Quando f é chamado com o argumento n , acontece o seguinte:

• O código

  126^sum(1>>n%i<<7*(n/i%i<1)for i in range(2,n))

  testa se n não é um número 7DP da seguinte maneira.

  Para todos os números inteiros i, de modo que 1 <i <n , 1>>n%i<<7*(n/i%i<1)é avaliado.

  • Se n é divisível por i, mas não por i ² , 1>>n%iproduz 1 e (n/i%i<1)produz 0 , resultando em
    1 · 2 ^{7 · 0} = 1 .

  • Se n é divisível por i ² , 1>>n%ie (n/i%i<1)ambos produzem 1 , resultando em 1 · 2 ^{7 · 1} = 128 .

  • Se n não for divisível por i , 1>>n%iproduz 0 , resultando em 0 · 2 ^{7 · x} = 0 .

  
  A soma dos números inteiros resultantes serão 2 ^m - 2 se n é um número (MDP seus dois ^m divisores, excluindo 1 e N ) e um número maior do que 127 se n tem um factor quadrado perfeito. Assim, a soma será 126 se e somente se n for um número 7DP.

• Para números 7DP, a soma é 126 , portanto, XOR com 126 produz 0 , o que é falso. Assim, o ou parte do lambda é executado ef retorna o valor atual de n .

• Se n não for um número 7DP, o XOR retornará um valor verdadeiro diferente de zero. Assim, a parte e do lambda é executada.

  f(n+k,k%2*2+~k)

  chama recursivamente f com valores atualizados de n (o próximo número 7DP em potencial) ek (a diferença entre o novo candidato e o seguinte).

  Se k é um número inteiro par, não negativo, k%2*2produz 0 e ~kproduz - (k + 1) . A soma dos dois resultados é - (k + 1) , que é um número inteiro ímpar negativo que é 1 maior em valor absoluto que k .

  Se k é um número inteiro ímpar, negativo, k%2*2produz 2 e ~kproduz - (k + 1) . A soma dos dois resultados é 2 - (k + 1) = - (k - 1) , que é um número inteiro par não negativo que é 1 unidade maior em valor absoluto que k .

  Isso significa que k assume os valores 0, -1, 2, -3, 4, ⋯ .

  Quando adicionados cumulativamente a n ₀ (o valor inicial de n ), os números inteiros resultantes são

  • n ₀ + 0
  • ( n ₀ + 0) - 1 = n ₀ - 1
  • ( n _0-1 ) + 2 = n ₀ + 1
  • ( N ₀ + 1) - 3 = N ₀ - 2
  • ( n _0-2 ) + 4 = n ₀ + 2
  • etc.

  
  certificando-se o primeiro número 7DP que encontramos é tão perto de n ₀ possível.

Braquilog , 44 40 16 bytes

_{O riscado 44 ainda é regular 44;}

:I=+.>0,.$pPdPl7

Exemplo:

?- run_from_atom(':I=+.>0,.$pPdPl7',1425060,Z).
Z = 1438710 .

Será que esse idioma nem sempre é ruim? Eu venci Jelly e MATL!

O caso de teste com 5é o mais longo e leva cerca de 10 segundos na minha máquina.

Isso seria de 12 bytes se $pnão fosse corrigido (não precisaríamos da >0,.parte)

Explicação

O Brachylog usa programação lógica de restrição por padrão para toda aritmética de número inteiro. Além disso, a etiquetagem interna =funciona em domínios possivelmente infinitos.

É sucessivamente unifica uma variável sem restrições (isto é, em (-inf, inf)) tal como: 0, 1, -1, 2, -2, 3, ….

Portanto, podemos obter o número 7DP mais próximo, procurando o primeiro número Iunificado (-inf, inf)(usando o Input + Iretorno automático), para o qual é um número 7DP.

:I=                Label variables in [Input, I]. I has no constraints and Input is known
   +.              Unify Output with Input + I
     >0,           Output > 0 (wouldn't be needed if $p failed for numbers less than 1)
        .$pP       Unify P with the list of prime factors of Output
            dP     Check that P with duplicates removed is still P
              l7   Check that the length of P is 7

Gelatina, 17 bytes

Pµạ³,
×⁹ÆRœc7Ç€ṂṪ

Trabalha em teoria, mas leva muitos anos para ser concluído.

Aqui está uma versão que realmente funciona para as entradas fornecidas, mas teoricamente falha para entradas grandes:

Pµạ³,
50ÆRœc7Ç€ṂṪ

Experimente aqui. Isso gera todos os números primos até 50, depois encontra todas as 7 combinações de números primos nessa lista e todos os seus produtos. Finalmente, ele simplesmente encontra o elemento mais próximo dessa lista para o argumento fornecido.

Obviamente, uma vez que nossos 7DPs contenham números primos maiores que 50, isso irá falhar. A versão teórica gera todos os números primos até 256n para uma entrada n , mas funciona da mesma maneira.

Prova

Vamos p(x)denotar o próximo primo depois x. Um limite superior (extremamente flexível) para o produto 7DP mais próximo de x é:

p(x) * p(p(x)) * p(p(p(x))) * ... * p(p(p(p(p(p(p(x)))))))

Portanto, só precisamos verificar os números primos em [2… p (p (p (p (p (p (p (p (x)))))))] . O postulado de Bertrand diz que p (x) ≤ 2x , portanto basta verificar todos os números primos de até 128x .

MATL , 21 17 16 14 13 bytes

Agradecemos a Dennis por uma sugestão que removeu 4 bytes e outra que salvou mais 1 byte!

t17*Zq7XN!pYk

Isso funciona na teoria, mas fica sem memória para as entradas acima 6(compilador online).

Uma versão mais eficiente usa 21 bytes e calcula todos os casos de teste em cerca de um segundo:

t3e4/k16+_YqZq7XN!pYk

Experimente online!

• Versão ineficiente em memória
• Versão com memória eficiente
• Versão com eficiência de memória, todos os casos de teste

Explicação

Versão com memória eficiente

Tome a entrada N = 860782como exemplo. Basta considerar primos até H = 29, que é o primeiro nobre que multiplicado por 2*3*5*7*11*13excede N . Neste exemplo 2*3*5*7*11*13*29 = 870870,. O próximo primo é 31. Qualquer produto que envolva que prime ou maior será, pelo menos 2*3*5*7*11*13*31 = 930930, e assim é garantido não ser a solução, porque excede 870870o que excede N .

M é calculado como o primeiro primo maior que max(N/(2*3*5*7*11*13), 16). A maxfunção é usada para garantir que pelo menos 17seja selecionado. Para salvar alguns bytes, o código substitui 2*3*5*7*11*13 = 30030por 30000e funciona maxpor adição. Essas alterações são válidas porque fornecem um valor maior.

t      % Take input implicitly. Duplicate
3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime
Zq     % Prime numbers up to that value
7XN    % Combinations of those primes taken 7 at a time. Gives a 2D array
       % with each combination on a different row
!p     % Product of each row
Yk     % Output product that is closest to the input. Implicitly display

Versão ineficiente em memória

Para reduzir ainda mais o número de bytes, a divisão pode ser removida; de fato, basta multiplicar por 17(obrigado, @Dennis). Isso garante que o próximo primo seja incluído (pelo postulado de Bertrand ) e que o resultado seja pelo menos 17. Isso funciona na teoria, mas fica sem memória para entradas maiores que cerca de 6.

No código, a seção

3e4/k  % Divide input by 30000 and round down (rounding here is only needed
       % due to a bug in the "next prime" function)
16+    % Add 16
_Yq    % Next prime

é substituído por

17*    % Multiply by 17

Pyke, 32 bytes

#PDl 7q.ID}lRlqi*(#)DF-X,)R],She

Experimente aqui!

Observe que isso não funciona on-line - é o tempo limite. Esta versão verifica apenas 2 números primos distintos e deve funcionar mais rapidamente. Quando existem 2 números da mesma distância do alvo, ele escolhe o menor.

Isso percorre todos os números até encontrar um que seja maior que a entrada e seja um 7DP. Para cada número, ele se livra se não for um 7DP. Em seguida, ele tem uma lista de 7DPs até a entrada com uma que é maior. Em seguida, escolhe o que está mais próximo da entrada.

Julia, 59 bytes

!n=sort(map(prod,combinations(17n|>primes,7))-n,by=abs)[]+n

Isso é muito ineficiente, mas funciona para o primeiro caso de teste na prática e para os outros na teoria.

Ao custo de mais 5 bytes - para um total de 64 bytes - a eficiência pode ser melhorada drasticamente.

!n=sort(map(prod,combinations(n>>14+17|>primes,7))-n,by=abs)[]+n

Experimente online!

fundo

Como mencionado na resposta de @ LuisMendo , o conjunto de números primos que devemos considerar para o número 7DP mais próximo é bastante pequeno. Basta que o conjunto contenha um número 7DP maior que a entrada n , que será verdadeira se e somente se contiver um valor inicial p ≥ 17 , de modo que 30300p = 2 · 3 · 5 · 7 · 11 · 13 · p ≥ n .

Em No intervalo que contém pelo menos um número primo, prova que o intervalo [x, 1,5x) contém pelo menos um número primo sempre que x ≥ 8 . Desde 30030/16384 ± 1,83 , isso significa que deve haver um p in prim (n / 30030, n / 16384) sempre que n> 8 · 30300 = 242400 .

Finalmente, quando n <510510 , p = 17 é claramente suficiente, portanto, precisamos considerar apenas primos até n / 16384 + 17 .

Ao custo da eficiência, podemos considerar primos de até 17n . Isso funciona quando n = 1 e é muito maior que n / 16384 + 17 para valores maiores de n .

Como funciona

17n|>primese n>>14+17|>primes(o deslocamento de bits é equivalente a dividir por 2 ¹⁴ = 16384 ) calcula os intervalos primos mencionados no parágrafo anterior. Em seguida, combinations(...,7)calcula todas as matrizes de sete números primos diferentes nesse intervalo e o mapeamento prodsobre esses calcula seus produtos, ou seja, os números 7DP dos quais escolheremos a resposta.

Em seguida, -nsubtrai n prom cada número 7DP e sort(...,by=abs)classifica essas diferenças por seus valores absolutos. Por fim, selecionamos a primeira diferença com []e calculamos o número 7DP correspondente adicionando n com +n.

Pitão, 30 bytes

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

Experimente online!

Suíte de teste.

(5 leva muito tempo para ser executado)

Explicação

L&{IPbq7lPby#.W!syMH,hhZa0teZ,

L&{IPbq7lPb     Defines a function y, whose argument is b:
 &                  Return if both the following are true:
  {IPb                  the prime factorization contains no duplicate; and:
      q7lPb             the number of prime factors is 7

           y#.W!syMH,hhZa0teZ,   The main programme. Input as Q.
                             ,QQ Implicit arguments, yield [Q,Q].
             .W                  While
               !syMH                   both numbers do not satisfy y:
                    ,hhZ             increment the first number
                          teZ        and decrement the second number
                        a0           while making it non-negative.

Mathematica 136 80 75 bytes

Esta é uma abordagem simples, trabalhando a partir de fora n.

né um produto com 7 primos distintos se o número de fatores primos for 7 ( PrimeNu@#==7) e nenhum desses fatores aparecer mais de uma vez ( SquareFreeQ@#&).

g@n_:=(k=1;While[!(PrimeNu@#==7&&SquareFreeQ@#&)⌊z=n-⌊k/2](-1)^k⌋,k++];z)

Meu envio anterior (136 bytes) encontrou o primeiro produto com 7 pontos distintos acima ne, se existir, o primeiro produto com 7 pontos distintos abaixo n. Então, simplesmente determinava qual estava mais próximo n. Se os produtos fossem equidistantes, retornariam ambos.

A versão atual verifica n-1, n + 1, n-2, n + 2 ... até atingir o primeiro produto 7-prime-prime. Esta versão mais eficiente adota a abordagem adotada por Dennis.

O avanço da chave estava em uso ⌊k/2](-1)^k⌋para retornar as séries, 0, 1, -1, 2, -2 ... O zero é usado para verificar se né um produto primo com 7 distintas. Por esse motivo, Floor(ou seja, ⌊...⌋) é usado em vez de Ceiling.

g[5]
g[860782]
g[1425060]

510510

870870

1438710

05AB1E , 10 bytes

°Åp7.ÆPs.x

Experimente online!

Tenta todas as combinações de 7 dos primeiros 10 ** primos de entrada. Fica sem memória para entradas maiores que 1.

Versão 14 bytes consideravelmente mais eficiente:

5°/7+Åp7.ÆPs.x

Experimente online!

Usa os primeiros (input / 100000 + 7) primos.