Desde Euclides, sabemos que existem infinitos primos. O argumento é por contradição: se há apenas um número finito muitos, digamos $p_1,p_2,...,p_n$ , então certamente $m:=p_1\cdot p_2\cdot...\cdot p_n+1$ não é divisível por qualquer desses números primos, então o seu primeiro-factorização deve produzir um novo primeiro que não estava na lista. Portanto, a suposição de que apenas primos finitos existem é falsa.

Agora vamos supor que $2$ é o único primo. O método acima fornece $2+1=3$ como um novo (possível) primo. A aplicação do método novamente produz $2\cdot 3+1=7$ e, em seguida, $2\cdot 3\cdot 7+1=43$ , depois $2\cdot 3\cdot 7\cdot 43+1=13\cdot 139$ , então $13$ e $139$ são novos números primos, etc. No caso em que obtemos um número composto, apenas obtemos o número primo menos novo. Isso resulta em A000945 .

Desafio

Dado um primo $p_1$ e um número inteiro $n$ calculam o $n$ ésimo termo $p_n$ da sequência definida da seguinte forma:

p_{n} := min (primefactors (p_{1} \cdot p_{2} \cdot . . . \cdot p_{n - 1} + 1))

$p_n := \min(\operatorname{primefactors}(p_1\cdot p_2\cdot ... \cdot p_{n-1} + 1))$

Essas sequências são conhecidas como sequências de Euclides-Mullin .

Exemplos

Para $p_1 = 2$ :

1 2
2 3
3 7
4 43
5 13
6 53
7 5
8 6221671
9 38709183810571

Para $p_1 = 5$ ( A051308 ):

1 5
2 2
3 11
4 3
5 331
6 19
7 199
8 53
9 21888927391

Para $p_1 = 97$ ( A051330 )

code-golf sequence integer primes factoring flawr
fonte

10

JavaScript (ES6), 45 44 bytes

Recebe a entrada como (n)(p1), onde $n$ é indexado em 0.

n=>g=(p,d=2)=>n?~p%d?g(p,d+1):--n?g(p*d):d:p

Experimente online!

Comentado

n =>                // n = 0-based index of the requested term
  g = (             // g is a recursive function taking:
    p,              //   p = current prime product
    d = 2           //   d = current divisor
  ) =>              //
    n ?             // if n is not equal to 0:
      ~p % d ?      //   if d is not a divisor of ~p (i.e. not a divisor of p + 1):
        g(p, d + 1) //     increment d until it is
      :             //   else:
        --n ?       //     decrement n; if it's still not equal to 0:
          g(p * d)  //       do a recursive call with the updated prime product
        :           //     else:
          d         //       stop recursion and return d
    :               // else:
      p             //   don't do any recursion and return p right away

Arnauld
fonte

9

05AB1E , 6 bytes

Isso produz um fluxo de saída infinito.

λλP>fW

Experimente online! (o link inclui uma versão ligeiramente modificada λ£λP>fW, que gera os primeiros $n$ termos)

Explicação

Muito simples. Dados $p_1$ e $n$ , o programa faz o seguinte:

Inicia com $p_1$ como um parâmetro inicial para o fluxo infinito (que é gerado usando o primeiro λ) e inicia um ambiente recursivo que gera um novo termo após cada interação e o anexa ao fluxo.
O segundo λ, agora sendo usado dentro do ambiente recursivo, altera sua funcionalidade: Agora, ele recupera todos os elementos gerados anteriormente (ou seja, a lista $[\lambda_0, \lambda_1, \lambda_2, \ldots, \lambda_{n-1}]$ ), onde $n$ representa o número de iteração atual.
O resto é trivial: Ppega o produto ( $\lambda_0\lambda_1\lambda_2 \cdots \lambda_{n-1}$ ), >adiciona um a este produto e fWrecupera o fator primário mínimo.

Mr. Xcoder
fonte

6

J , 15 bytes

-10 bytes graças a milhas!

Retornando a sequência até n (indexado a zero) - graças a @miles

(,0({q:)1+*/)^:

Experimente online!

J , 25 bytes

Retorna o n item th

_2{((],0{[:q:1+*/@])^:[])

Experimente online!

Galen Ivanov
fonte

1

(,0({q:)1+*/)^:por 15 bytes, retornando a sequência até n(indexada a zero)

milhas

@miles Obrigado!

Galen Ivanov

Muito agradável. @ milhas o que exatamente está acontecendo lá gramaticalmente? juntamos um verbo e uma conjunção e obtemos um verbo diádico de volta. Eu pensei que verb conj produziu um advérbio .

Jonah

1

@ Jonah, é um truque que aprendi no golfe. Eu acho que é uma das regras de análise mais velhos que ainda é válido

milhas

@miles Acabei de perceber que é um advérbio (ou adnoun). Ele modifica o substantivo à sua esquerda, que "atribui" à direita do ^:, e, em seguida, que se torna um verbo que se aplica ao arg direita. Eu acho que é isso que está acontecendo gramaticalmente.

Jonah

5

Python 2 , 56 bytes

i=input();k=1
while 1:
 k*=i;print i;i=2
 while~k%i:i+=1

Experimente online!

Comentado

i=input() # the initial prime
k=1       # the product of all previous primes
while 1:  # infinite loop
 k*=i     # update the product of primes
 print i  # output the last prime
 i=2      # starting at two ...
 while~k%i: # find the lowest number that divides k+1
  i+=1
            # this our new prime

Experimente online!

ovs
fonte

Eu apenas comecei com Python, mas você precisa de int(input())outra forma ié um str?

Anthony

2

No Python 3 isso seria verdade, como input()sempre retorna strings. No Python 2, input()tenta avaliar a entrada. Estou usando o Python 2 neste caso, porque o código resultante é um pouco menor. Para código real , você deve tentar usar o Python 3, pois é a versão mais recente e mais suportada do Python.

ovs 5/09

Como isso termina após n etapas?

sintax 6/09

@sintax gera a sequência para um dado p1 indefinidamente, conforme permitido pelas regras de sequência padrão .

ovs 6/09

4

Geléia , 8 bytes

P‘ÆfṂṭµ¡

Um programa completo (usando indexação zero) aceitando $P_0$ e $n$ que imprime uma representação Jelly da lista de $P_0$ para $P_n$ inclusive. (Como um link diádico, n=0retornaremos um número inteiro, não uma lista.)

Experimente online!

Quão?

P‘ÆfṂṭµ¡ - Link: integer, p0; integer n
      µ¡ - repeat the monadic chain to the left n times, starting with x=p0:
P        -   product of x (p0->p0 or [p0,...,pm]->pm*...*p0)
 ‘       -   increment
  Æf     -   prime factors
    Ṃ    -   minimum
     ṭ   -   tack
         - implicit print

Jonathan Allan
fonte

3

05AB1E , 8 bytes

GDˆ¯P>fß

A primeira entrada é $n$ , segundo é primo $p$ .

Experimente online ou muito mais casos de teste (o conjunto de testes não possui os casos de teste para $n\geq9$ , por causa de $p=2$ e $p=5$ o built-in fleva muito tempo).

Explicação:

G         # Loop (implicit input) n-1 amount of times:
 Dˆ       #  Add a copy of the number at the top of the stack to the global array
          #  (which will take the second input p implicitly the first iteration)
   ¯      #  Push the entire global array
    P     #  Take the product of this list
     >    #  Increase it by 1
      f   #  Get the prime factors of this number (without counting duplicates)
       ß  #  Pop and only leave the smallest prime factor
          # (after the loop: implicitly output the top of the stack as result)

Kevin Cruijssen
fonte

Eu tinha λλP>fW(6 bytes) com saída como uma lista infinita e λ£λP>fW(7 bytes) pela primeira vez

n

$n$ termos. No entanto, obter o

n^{th}

$n^{\text{th}}$ deve ter 9 bytes ... Se ao menos tivéssemos uma flag como, £mas o último elemento!

Sr. Xcoder

@ Mr.Xcoder " Se ao menos tivéssemos uma bandeira como £mas para o último elemento! ", Como .£? ;) EDIT: Na verdade, ele não funciona exatamente como £para listas .. usando uma lista como [1,2]com .£resultados em dois itens soltos com os últimos 1 e 2 itens (ou seja, 12345torna-se em [5,45]vez de [45,3]ou [3,45]com 12S.£) ..

Kevin Cruijssen

Hum, não, não vejo como λ.£deve funcionar. Eu usei flag como em uma função adicional associada a λ(consulte esta conversa com Adnan ). Eu basicamente quero um sinalizador èque, ao executá- λè...}lo, gere o n-ésimo elemento em vez do fluxo infinito (assim como λ£funcionaria para gerar os primeiros n elementos).

Sr. Xcoder

@ Mr.Xcoder Ah, desculpe, você usou o £ambiente recursivo. Sim, então λ.£realmente não vai funcionar, meu mal. Nice 6-byter independentemente. Agora você só precisa aguardar a resposta do @flawr , seja ela permitida ou não (provavelmente é).

Kevin Cruijssen 5/09

3

Japonês , 12 11 bytes

Esforçou-se para acertar este, por isso pode ter perdido algo que pode ser jogado no golfe.

Toma ncomo a primeira entrada e p1, como uma matriz singleton, como a segunda. Retorna os primeiros ntermos. Mude hpara gpara retornar o ntermo indexado em 0.

@Z×Ä k Î}hV

Tente

@Z×Ä k Î}hV     :Implicit input of integer U=n & array V=[p1]
@               :Function taking an array as an argument via parameter Z
 Z×             :  Reduce Z by multiplication
   Ä            :  Add 1
     k          :  Prime factors
       Î        :  First element
        }       :End function
         hV     :Run that function, passing V as Z, and
                : push the result to V.
                : Repeat until V is of length U

Shaggy
fonte

3

Retina , 56 bytes

,|$
$*
"$&"{~`.+¶
$$¶_
)`\b(__+?)\1*$
$.1$*
1A`
.$

\*
,

Experimente online! Recebe entrada como o número de novos termos a serem adicionados na primeira linha e o (s) termo (s) inicial (is) na segunda linha. Nota: Fica muito lento, pois usa fatoração unária, portanto, é necessário criar uma sequência do comprimento relevante. Explicação:

,|$
$*

Substitua as vírgulas nos termos de propagação por se *acrescente a *. Isso cria uma expressão Retina para uma sequência de comprimento do produto dos valores.

"$&"{
)`

Repita o loop o número de vezes indicado pela primeira entrada.

~`.+¶
$$¶_

Substitua temporariamente o número na primeira linha por $ae anteceda _a à segunda linha e avalie o resultado como um programa Retina, acrescentando, assim, uma sequência de _s de comprimento 1 mais que o produto dos valores.

\b(__+?)\1*$
$.1$*

Encontre o menor fator não trivial do número em decimal e adicione um *pronto para o próximo loop.

1A`

Exclua a entrada da iteração.

.$

Exclua o último *.

\*
,

Substitua os restantes *s por ,s.

Neil
fonte

2

JavaScript (Node.js) , 54 bytes

f=(p,n,P=p,F=n=>-~P%n?F(n+1):n)=>--n?f(p=F(2),n,P*p):p

Experimente online!

Ungolfed

F=(p,n=2)=>            // Helper function F for finding the smallest prime factor
  p%n                  //   If n (starting at 2) doesn't divide p:
    ?F(n+1)            //     Test n+1 instead
    :n                 //   Otherwise, return n
f=(p,n,P=p)=>          // Main function f:
  --n                  //   Repeat n - 1 times:
    ?f(p=F(P+1),n,P*p) //     Find the next prime factor and update the product
    :p                 //   Return the last prime

Herman L
fonte

2

bash + núcleo GNU, 89 bytes

IFS=\*;n=$1;shift;for((;++i<n;));{ set $@ `factor $["$*+1"]|cut -d\  -f2`;};echo ${@: -1}

TIO

Nahuel Fouilleul
fonte

2

Ruby 2.6, 51 bytes

f=->s,n{[s,l=(2..).find{|d|~s%d<1}][n]||f[l*s,n-1]}

(2..), o intervalo infinito a partir de 2, ainda não é suportado no TIO.

Essa é uma função recursiva que pega um valor inicial s(pode ser primo ou composto), retorna quando n = 0 (edite: observe que isso significa que é indexado a zero), retorna o menor número lmaior que 1 e divide -(s+1)quando n = 1 e, de outro modo, se repete com s=l*se n=n-1.

histocrata
fonte

1

Você provavelmente deve mencionar que está fazendo indexação zero; Troquei (2..)por 2.step(apenas 1 byte a mais) para permitir que ele funcionasse no TIO e tudo foi interrompido por um. Experimente online!

Value Ink

2

APL (Dyalog Extended) , 15 bytes

Esta é uma implementação bastante simples do algoritmo que usa os fatores primários muito úteis do Extended ⍭,. Experimente online!

{⍵,⊃⍭1+×/⍵}⍣⎕⊢⎕

Explicação

{⍵,⊃⍭1+×/⍵}⍣⎕⊢⎕

             ⊢⎕  First get the first prime of the sequence S from input.
{         }⍣⎕    Then we repeat the code another input number of times.
     1+×/⍵       We take the product of S and add 1.
    ⍭            Get the prime factors of product(S)+1.
   ⊃             Get the first element, the smallest prime factor of prod(S)+1.
 ⍵,              And append it to S.

Sherlock9
fonte

1

Pari / GP , 47 bytes

(p,n)->s=1;for(i=2,n,s*=p;p=divisors(s+1)[2]);p

Experimente online!

alefalpha
fonte

1

Stax , 9 bytes

é|G╝╓c£¼_

Execute e depure

Toma e (indexado a zero) para entrada. Produz .p₀np_n

recursivo
fonte

1

C (gcc) , 54 53 bytes

p;f(x,n){for(p=x;--n;p*=x)for(x=1;~p%++x;);return x;}

Experimente online!

-1 byte graças ao ceilingcat

wastl
fonte

1

Perl 6 , 33 32 bytes

-1 byte graças a nwellnhof

{$_,{1+(2...-+^[*](@_)%%*)}...*}

Experimente online!

Bloco de código anônimo que pega um número e retorna uma lista lenta.

Explicação:

{                              }  # Anonymous codeblock
                           ...*   # That returns an infinite list
 $_,                              # Starting with the input
    {                     }       # Where each element is
     1+(2...             )          # The first number above 2
                      %%*           # That cleanly divides
               [*](@_)                # The product of all numbers so far
            -+^                       # Plus one

Brincadeira
fonte

1

-+^[*](@_)salva um byte.

nwellnhof 13/09

0

Haskell , 49 bytes

g 1
g a b=b:g(a*b)([c|c<-[2..],1>mod(a*b+1)c]!!0)

Experimente online!

Retorna a sequência infinita como uma lista lenta.

Explicação:

g 1                                            -- Initialise the product as 1
g a b=                                         -- Given the product and the current number
       b:                                      -- Return the current number, followed by
         g                                     -- Recursively calliong the function with
          (a*b)                                -- The new product
               (                             ) -- And get the next number as
                [c|c<-[2..],             ]!!0  -- The first number above 2
                            1>mod       c      -- That cleanly divides
                                 (a*b+1)       -- The product plus one

Brincadeira
fonte

Infinitamente muitos números primos

Desafio

Exemplos

Respostas:

JavaScript (ES6), 45 44 bytes

Comentado

05AB1E , 6 bytes

Explicação

J , 15 bytes

J , 25 bytes

Python 2 , 56 bytes

Comentado

Geléia , 8 bytes

Quão?

05AB1E , 8 bytes

Japonês , 12 11 bytes

Retina , 56 bytes

JavaScript (Node.js) , 54 bytes

bash + núcleo GNU, 89 bytes

Ruby 2.6, 51 bytes

APL (Dyalog Extended) , 15 bytes

Pari / GP , 47 bytes

Stax , 9 bytes

C (gcc) , 54 53 bytes

Perl 6 , 33 32 bytes

Explicação:

Haskell , 49 bytes

Explicação: