Esta é a sequência A054261
O th número de contenção principal é o número mais baixo que contém os primeiros primos números como subsequências. Por exemplo, o número é o número mais baixo que contém os 3 primeiros números primos como substrings, tornando-o o terceiro número de contenção principal.
É trivial descobrir que os quatro primeiros números de contenção primos são , , e , mas depois fica mais interessante. Como o próximo primo é 11, o próximo número de contenção do primo não é , mas é pois é definido como o menor número com a propriedade.
No entanto, o verdadeiro desafio surge quando você ultrapassa 11. O próximo número de contenção principal é . Observe que, neste número, as substrings e estão sobrepostas. O número também se sobrepõe ao número .11
13
3
13
É fácil provar que essa sequência está aumentando, pois o próximo número precisa atender a todos os critérios do número anterior e ter mais uma substring. No entanto, a sequência não está aumentando estritamente, como é mostrado pelos resultados para n=10
e n=11
.
Desafio
Seu objetivo é encontrar o maior número possível de contenção primária. Seu programa deve produzi-los de maneira ordenada, começando com 2 e subindo.
Regras
- Você tem permissão para codificar números primos.
- Você não tem permissão para codificar números de contenção primária (
2
é a única exceção) ou qualquer número mágico que torne o desafio trivial. Por favor seja gentil. - Você pode usar qualquer idioma que desejar. Inclua uma lista de comandos para preparar o ambiente para a execução do código.
- Você é livre para usar CPU e GPU e pode usar multithreading.
Pontuação
A pontuação oficial será no meu laptop (dell XPS 9560). Seu objetivo é gerar o maior número possível de contenção possível dentro de 5 minutos.
Especificações
- Intel Core i7-7700HQ de 2,8 GHz (aumento de 3,8 GHz) 4 núcleos, 8 threads.
- 16GB 2400MHz DDR4 RAM
- NVIDIA GTX 1050
- Linux Mint 18.3 de 64 bits
Os números encontrados até o momento, juntamente com o último primo adicionado ao número:
1 => 2 ( 2)
2 => 23 ( 3)
3 => 235 ( 5)
4 => 2357 ( 7)
5 => 112357 ( 11)
6 => 113257 ( 13)
7 => 1131725 ( 17)
8 => 113171925 ( 19)
9 => 1131719235 ( 23)
10 => 113171923295 ( 29)
11 => 113171923295 ( 31)
12 => 1131719237295 ( 37)
13 => 11317237294195 ( 41)
14 => 1131723294194375 ( 43)
15 => 113172329419437475 ( 47)
16 => 1131723294194347537 ( 53)
17 => 113172329419434753759 ( 59)
18 => 2311329417434753759619 ( 61)
19 => 231132941743475375961967 ( 67)
20 => 2311294134347175375961967 ( 71)
21 => 23112941343471735375961967 ( 73)
22 => 231129413434717353759619679 ( 79)
23 => 23112941343471735359619678379 ( 83)
24 => 2311294134347173535961967837989 ( 89)
25 => 23112941343471735359619678378979 ( 97)
26 => 2310112941343471735359619678378979 (101)
27 => 231010329411343471735359619678378979 (103)
28 => 101031071132329417343475359619678378979 (107)
29 => 101031071091132329417343475359619678378979 (109)
30 => 101031071091132329417343475359619678378979 (113)
31 => 101031071091131272329417343475359619678378979 (127)
32 => 101031071091131272329417343475359619678378979 (131)
33 => 10103107109113127137232941734347535961967838979 (137)
34 => 10103107109113127137139232941734347535961967838979 (139)
35 => 10103107109113127137139149232941734347535961967838979 (149)
36 => 1010310710911312713713914923294151734347535961967838979 (151)
Agradecemos a Ardnauld, Ourous e japh por estender esta lista.
Observe que n = 10
e n = 11
são o mesmo número, pois é o número mais baixo que contém todos os números , mas também contém .
Para referência, você pode usar o fato de que o script Python original que escrevi para gerar esta lista acima calcula os 12 primeiros termos em cerca de 6 minutos.
Regras adicionais
Após os primeiros resultados, percebi que há uma boa chance de que os melhores resultados possam ter a mesma pontuação. No caso de empate, o vencedor será o que tiver menos tempo para gerar seu resultado. Se duas ou mais respostas produzirem resultados igualmente rápidos, será simplesmente uma vitória empatada.
Nota final
O tempo de execução de 5 minutos é colocado apenas para garantir uma pontuação justa. Eu ficaria muito interessado em ver se podemos avançar ainda mais na sequência OEIS (agora ela contém 17 números). Com o código de Ourous, gerei todos os números até n = 26
, mas pretendo deixar o código funcionar por um longo período de tempo.
Placar
- Python 3 + Ferramentas OR do Google : 169
- Scala : 137 (não oficial)
- Solucionador Concorde TSP : 84 (não oficial)
- Conjunto C ++ (GCC) + x86 : 62
- Limpo : 25
- JavaScript (Node.js) : 24
fonte
n=11
trivial, pois você só precisa verificar sen=10
também satisfaz a nova condição. Eu também argumentaria que a codificação embutida só ajuda atén=17
, pois nenhum número é conhecido além desse ponto, até onde pude descobrir.[1,22,234,2356,112356,113256,1131724,113171924,1131719234,113171923294,113171923294,1131719237294]
e iniciar uma pesquisa de cada umRespostas:
Python 3 + Google OR-Tools , pontuação 169 em 295 segundos (pontuação oficial)
Como funciona
Após descartar números primos redundantes contidos em outros números primos, desenhe um gráfico direcionado com uma aresta de cada primo para cada um de seus sufixos, com distância zero e uma aresta para cada primo de cada um de seus prefixos, com distância definida pelo número de dígitos adicionados . Buscamos o primeiro caminho lexicograficamente mais curto através do gráfico, começando no prefixo vazio, passando por cada primo (mas não necessariamente por cada prefixo ou sufixo) e terminando no sufixo vazio.
Por exemplo, aqui estão as arestas do caminho ideal ε → 11 → 1 → 13 → 3 → 31 → 1 → 17 → ε → 19 → ε → 23 → ε → 29 → ε → 5 → ε para n = 11, correspondente para a sequência de saída 113171923295.
Comparado à redução direta ao problema do vendedor ambulante , observe que, ao conectar os primos indiretamente por esses nós de sufixo / prefixo extras, em vez de diretamente um ao outro, reduzimos drasticamente o número de arestas que precisamos considerar. Mas como os nós extras não precisam ser atravessados exatamente uma vez, isso não é mais uma instância do TSP.
Usamos o solucionador de restrições incremental CP-SAT do Google OR-Tools, primeiro para minimizar o comprimento total do caminho e, em seguida, para minimizar cada grupo de dígitos adicionados em ordem. Inicializamos o modelo apenas com restrições locais: cada primo precede um sufixo e sucede um prefixo, enquanto cada sufixo / prefixo precede e sucede o mesmo número de primos. O modelo resultante pode conter ciclos desconectados; nesse caso, adicionamos restrições de conectividade adicionais dinamicamente e executamos novamente o solucionador.
Código
Resultados
Aqui estão os primeiros 1000 números de contenção primária , calculados em 1 ½ dias em um sistema de 8 núcleos / 16 threads.
fonte
Montagem C ++ (GCC) + x86, pontuação
323662 em 259 segundos (oficial)Resultados calculados até o momento. Meu computador fica sem memória depois
65
.Todos eles concordam com a saída do solucionador baseado em Concorde , portanto, eles têm uma boa chance de estarem corretos.
Changelog:
Cálculo incorreto para o comprimento de contexto necessário. A versão anterior era 1 muito grande e também apresentava um erro. Pontuação:
3234Adicionado otimização de grupo de contexto igual. Pontuação:
3436Revisão do algoritmo para usar seqüências livres de contexto corretamente, além de outras otimizações. Pontuação:
3662Adicionada uma redação adequada.
Adicionada a variante dos números primos.
Como funciona
Aviso: este é um despejo de cérebro. Role até o fim, se você quiser apenas o código.
Abreviações:
Este programa basicamente usa o algoritmo de programação dinâmica do livro didático para o TSP.
São muitos bugs em potencial. Depois de brincar com a entrada de anselm e não conseguir obter resultados errados, devo pelo menos provar que minha abordagem geral está correta.
Embora a solução baseada no Concorde seja (muito, muito) mais rápida, ela se baseia na mesma redução, portanto, essa explicação se aplica a ambos. Além disso, esta solução pode ser adaptada para OEIS A054260 , a sequência de primos contendo primos; Não sei como resolver isso com eficiência na estrutura do TSP. Portanto, ainda é um pouco relevante.
Redução de TSP
Vamos começar provando que a redução ao TSP está correta. Temos um conjunto de strings, digamos
e queremos encontrar a menor supercorda que contém esses itens.
Saber o comprimento é suficiente
Para o PCN, se houver várias seqüências menores, precisamos retornar a menor lexicograficamente. Mas veremos um problema diferente (e mais fácil).
Se conseguirmos resolver o comprimento do SCS, podemos reconstruir a menor solução e obter o PCN. Se sabemos que a menor solução começa com o nosso prefixo, tentamos estendê-lo anexando cada item, em ordem lexicográfica, e resolvendo o tamanho novamente. Quando encontrarmos o item menor para o qual o comprimento da solução é o mesmo, sabemos que esse deve ser o próximo item na menor solução (por quê?); Portanto, adicione-o e recorra aos itens restantes. Esse método de alcançar a solução é chamado de auto-redução .
Percorrer o gráfico de sobreposição máxima
Suponha que começamos a resolver o SCS para o exemplo acima manualmente. Provavelmente:
13
e37
, porque eles já são substrings dos outros itens. Qualquer solução que contenha137
, por exemplo, também deve conter13
e37
.113,137 → 1137
,211,113 → 2113
etc.De fato, é a coisa certa a fazer, mas vamos provar isso por uma questão de perfeição. Pegue qualquer solução SCS; por exemplo, uma supercorda mais curta
A
ée pode ser decomposto em uma concatenação de todos os itens em
A
:(Ignoramos os itens redundantes
13, 37
.) Observe o seguinte:Mostraremos que todas as supercordas menores podem ser decompostas desta maneira:
Para cada par de itens adjacentes
x,y
,y
inicia e termina em posições posteriores ax
. Se isso não for verdade,x
é uma substringy
ou vice-versa. Mas já removemos todos os itens que são substrings, para que isso não possa acontecer.Suponha que itens adjacentes na sequência tenham sobreposição menor que a máxima, por exemplo, em
21113
vez de2113
. Mas isso tornaria o1
redundante extra . Nenhum item posterior precisa da inicial1
(como em 2 1 113), porque ocorre antes113
e todos os itens que aparecem depois113
não podem começar com um dígito antes.113
(consulte o ponto 1). Um argumento semelhante impede que o último extra1
(como em 211 1 3) seja usado por qualquer item anterior211
. Mas nossa supercorda mais curta , por definição, não terá dígitos redundantes; portanto, essas sobreposições não máximas não ocorrerão.Com essas propriedades, podemos converter qualquer problema do SCS em um TSP:
x
,y
, adicionar uma arestax
day
cujo peso é o número de símbolos extra adicionado anexandoy
parax
com sobreposição máxima. Por exemplo, adicionaríamos uma aresta de211
a113
com o peso 1, porque2113
adiciona mais um dígito211
. Repita para a borda dey
atéx
.Qualquer caminho neste gráfico, a partir do prefixo inicial, corresponde a uma concatenação de sobreposição máxima de todos os itens desse caminho, e o peso total do caminho é igual ao comprimento da sequência concatenada. Portanto, todo passeio de menor peso, que visita todos os itens pelo menos uma vez, corresponde a uma supercorda mais curta.
E essa é a redução de SCS (e comprimento SCS) para TSP.
Algoritmo de programação dinâmica
Este é um algoritmo clássico, mas vamos modificá-lo um pouco, então aqui está um lembrete rápido.
(Eu escrevi isso como um algoritmo para o comprimento do SCS em vez do TSP. Eles são essencialmente equivalentes, mas o vocabulário do SCS ajuda quando chegamos às otimizações específicas do SCS.)
Chame o conjunto de itens de entrada
A
e o prefixo fornecidoP
. Para cadak
subconjunto -elementS
emA
e todo elementoe
deS
, calculamos o comprimento da string mais curta que começa comP
, contém todosS
e termina come
. Isso envolve armazenar uma tabela a partir dos valores de(S, e)
para seus comprimentos de SCS.Quando chegamos a cada subconjunto
S
, a tabela já precisa conter os resultadosS - {e}
para todose
emS
. Como a tabela pode ficar muito grande, eu calcular os resultados para todos osk
subconjuntos -element, entãok+1
, etc. Para isso, precisamos apenas para armazenar os resultados parak
ek+1
em qualquer momento um. Isso reduz o uso de memória em um fator de aproximadamentesqrt(|A|)
.Mais um detalhe: em vez de calcular o comprimento mínimo do SCS, na verdade eu calculo a sobreposição total máxima entre os itens. (Para obter o comprimento do SCS, basta subtrair a sobreposição total da soma dos comprimentos dos itens.) O uso de sobreposições ajuda a algumas das otimizações a seguir.
[2.] Contextos de itens
Um contexto é o sufixo mais longo de um item que pode se sobrepor aos itens a seguir. Se nossos itens forem
113,211,311
, então11
é o contexto para211
e311
. (Também é o contexto do prefixo113
, que veremos na parte [4.])No algoritmo DP acima, acompanhamos as soluções de SCS que terminam com cada item, mas na verdade não nos importamos com qual item um SCS termina. Tudo o que precisamos saber é o contexto. Assim, por exemplo, se dois SCSs para o mesmo conjunto terminarem em ,
23
e43
qualquer SCS que continuar de um também funcionará para o outro.Essa é uma otimização significativa, porque os números primos não triviais terminam apenas nos dígitos
1 3 7 9
. Os quatro contextos de um dígito1,3,7,9
(mais o contexto vazio) são de fato suficientes para calcular os PCNs para números primos de até131
.[3.] Itens sem contexto
Outros já apontaram que muitos números primos começam com os dígitos
2,4,5,6,8
, como23,29,41,43...
. Nada disso pode se sobrepor a um primo anterior (além de2
e5
, primos não podem terminar com esses dígitos;2
e5
já foram removidos como redundantes). No código, eles são chamados de seqüências livres de contexto .Se nossa entrada tiver itens livres de contexto, todas as soluções SCS poderão ser divididas em blocos
e as sobreposições em cada bloco são independentes dos outros blocos. Podemos embaralhar os blocos ou trocar itens entre os blocos que têm o mesmo contexto, sem alterar o comprimento do SCS.
Portanto, precisamos apenas acompanhar os possíveis vários conjuntos de contextos, um para cada bloco.
Exemplo completo: para os primos menores que 100, temos 11 itens sem contexto e seus contextos:
Nosso contexto multiset inicial:
O código se refere a eles como contextos combinados ou ccontexts . Então, precisamos considerar apenas subconjuntos dos itens restantes:
[4.] Mesclagem de contexto
Quando chegamos aos números primos com 3 dígitos ou mais, há mais redundâncias:
Esses grupos compartilham os mesmos contextos inicial e final (geralmente - depende de quais outros números primos estão na entrada); portanto, eles são indistinguíveis ao se sobrepor a outros itens. Só nos preocupamos com sobreposições, para que possamos tratar os números primos nesses grupos de contexto igual como indistinguíveis. Agora, nossos subconjuntos DP são condensados em multisubsets
(É também por isso que o solucionador maximiza o comprimento da sobreposição em vez de minimizar o comprimento do SCS: essa otimização preserva o comprimento da sobreposição.)
Resumo: as otimizações de alto nível
A execução com
INFO
saída de depuração imprimirá estatísticas comoEsta linha específica é para o comprimento de SCS dos primeiros 62 primos,
2
para293
.1,3,7,11,13,27
mais a sequência vazia.43,47,53,59,61,89,211,223,227,229,241,251,257,263,269,281,283
. Esses e o prefixo fornecido (nesse caso, cadeia vazia) formam a base do contexto combinado inicial .N_search
), existem 16 grupos de contexto igual não triviais .Ao explorar essas estruturas, o cálculo do comprimento do SCS precisa apenas verificar 8498336
(multiset, ccontext)
combinações. A programação dinâmica direta tomaria43×2^43 > 3×10^14
medidas, e a força bruta das permutações tomaria6×10^52
medidas. O programa ainda precisa executar o SCS-Length várias vezes para reconstruir a solução PCN, mas isso não leva muito mais tempo.[5., 6.] As otimizações de baixo nível
Em vez de executar operações de cadeia, o solucionador de comprimento de SCS trabalha com índices de itens e contextos. Também pré-calculo a quantidade de sobreposição entre cada contexto e par de itens.
O código usava inicialmente os GCCs
unordered_map
, que parecem ser uma tabela de hash com intervalos de lista vinculada e tamanhos de hash principais (ou seja, divisões caras). Então, escrevi minha própria tabela de hash com sondagem linear e potência de dois tamanhos. Isso permite uma aceleração de 3x e redução de 3x na memória.Cada estado da tabela consiste em um conjunto múltiplo de itens, um contexto combinado e uma contagem de sobreposições. Eles são compactados em entradas de 128 bits: 8 para a contagem de sobreposição, 56 para o multiset (como um conjunto de bits com codificação de comprimento de execução) e 64 para o ccontext (RLE delimitado por 1). Codificar e decodificar o ccontext foi a parte mais complicada e acabei usando o novo
PDEP
instrução (é tão nova que o GCC ainda não tem uma intrínseca para ela).Finalmente, o acesso a uma tabela de hash é muito lento quando
N
fica grande, porque a tabela não se encaixa mais no cache. Mas a única razão pela qual escrevemos na tabela de hash é atualizar a contagem de sobreposições mais conhecida para cada estado. O programa divide essa etapa em uma fila de pré-busca e o loop interno pré-busca cada tabela de algumas iterações antes de realmente atualizar esse slot. Outra aceleração 2 × no meu computador.Bônus: novas melhorias
AKA Como o Concorde é tão rápido?
Eu não sei muito sobre algoritmos TSP, então aqui está um palpite.
O Concorde usa o método de ramificação e corte para resolver TSPs.
Idéias óbvias que poderíamos tentar:
No entanto, a combinação de ramificação e corte é muito poderosa, portanto, talvez não consigamos vencer um solucionador de última geração como o Concorde, para grandes valores de
N
.Bônus de bônus: os primos de contenção principais
Diferentemente da solução baseada no Concorde, este programa pode ser modificado para encontrar os menores números primos que contêm ( OEIS A054260 ). Isso envolve três alterações:
Modifique o código do solucionador de comprimento do SCS para categorizar as soluções com base em se as somas de dígitos são divisíveis por 3. Isso envolve adicionar outra entrada, a soma dos dígitos mod 3, a cada estado DP. Isso reduz bastante as chances de o solucionador principal ficar preso com permutações não principais. Esta é a mudança que eu não consegui descobrir como traduzir para o TSP. Ele pode ser codificado com ILP, mas então eu teria que aprender sobre isso chamado “desigualdade de subtore” e como gerá-los.
Pode ser que todos os PCNs mais curtos sejam divisíveis por 3. Nesse caso, o menor prime de contenção primária deve ter pelo menos um dígito a mais que o PCN. Se o nosso solucionador de comprimento de SCS detectar isso, o código de reconstrução da solução terá a opção de adicionar um dígito extra em qualquer ponto do processo. Ele tenta adicionar cada dígito possível
0..9
e cada item restante ao prefixo da solução atual, em ordem lexicográfica como antes.Com essas mudanças, posso obter as soluções até
N=62
. Exceto por47
onde o código de reconstrução fica preso e desiste após 1 milhão de etapas (ainda não sei por que). Os primos de contenção principal são:Código
Ajuntar com
Para a versão do número primo, também vincule ao GMPlib, por exemplo
Este programa usa a instrução PDEP, disponível apenas nos processadores x86 recentes (Haswell +). Tanto o meu computador como o maxb suportam. Caso contrário, o programa será compilado em uma versão lenta do software. Um aviso de compilação será impresso quando isso acontecer.
Experimente online!
E a versão exclusiva no TIO . Desculpe, mas não joguei golfe nesses programas e há um limite de tamanho de postagem.
fonte
debug_dummy
, você pode usar#define DEBUG(x) void(0)
.debug_dummy
porque quero que os argumentos sejam do tipo verificado e avaliado, mesmo quando a depuração estiver desativada.N=32
só precisa de cerca de 500 MB, eu acho.main
, mas eu o encontrei no link TIO.JavaScript (Node.js) , pontuação 24 em 241 segundos
Resultados
Algoritmo
Essa é uma pesquisa recursiva que tenta todas as formas possíveis de mesclar números e, eventualmente, classifica as listas resultantes em ordem lexicográfica quando um nó folha é atingido.
No início de cada iteração, qualquer entrada que possa ser encontrada em outra entrada é removida da lista.
Foi alcançada uma aceleração significativa acompanhando os nós visitados, para que possamos abortar cedo quando operações diferentes levarem à mesma lista.
Uma pequena aceleração foi alcançada atualizando e restaurando a lista quando possível, em vez de gerar uma cópia, conforme sugerido por
um usuário anônimoNeil.Exemplo
Código
Experimente online!
fonte
Solucionador Concorde TSP , pontuação 84 em 299 segundos
Bem ... eu me sinto boba por perceber isso agora.
Tudo isso é essencialmente um problema de vendedor ambulante . Para cada par de números primos
p
eq
, adicione uma aresta cujo peso seja o número de dígitos adicionados porq
(removendo dígitos sobrepostos). Além disso, adicione uma aresta inicial a cada primep
, cujo peso é o comprimento dep
. O caminho mais curto do vendedor itinerante corresponde ao tamanho do menor número de contenção principal.Então, um solucionador TSP de nível industrial, como o Concorde , fará um breve trabalho com esse problema.
Essa entrada provavelmente deve ser considerada não concorrente.
Resultados
O solucionador chega
N=350
em cerca de 20 horas de CPU. Os resultados completos são muito longos para uma postagem do SE, e a OEIS não deseja tantos termos assim mesmo. Aqui estão os primeiros 200:Código
Aqui está um script Python 3 para chamar o solucionador de Concorde várias vezes, até que ele construa as soluções.
O Concorde é gratuito para uso acadêmico. É possível fazer o download de um binário executável do Concorde criado com seu próprio pacote de programação linear QSopt ou, se você tiver uma licença para o IBM CPLEX, de alguma forma, poderá criar o Concorde a partir da origem para usar o CPLEX.
fonte
Limpo , marcar 25 em 231 segundos (pontuação oficial)
Resultados
1 < n <= 23
em4236 segundos no TIOn = 24 (2311294134347173535961967837989)
em3224 segundos localmenten = 25 (23112941343471735359619678378979)
em210160 segundos localmenten = 1
an = 25
foi encontrado em 231 segundos para que a pontuação oficial (editado por maxb)Isso usa uma abordagem semelhante à solução JS da Arnauld, com base na rejeição recursiva da permutação, usando um conjunto de árvores especializado para ganhar muita velocidade.
Para cada primo que precisa caber no número:
Em seguida, para cada par de sub-strings às quais unimos, remova quaisquer sub-strings desse par unido da lista de sub-strings e recorra a ele.
Depois que nenhuma sub-string pode ser unida a outras sub-strings em qualquer parte de nossa recursão, usamos o conjunto de árvores já ordenadas para encontrar rapidamente o número mais baixo que contém as sub-strings.
Coisas a serem melhoradas / adicionadas:
Houve grandes quedas de desempenho entre
19 -> 20
e24 -> 25
devido à manipulação duplicada na etapa de teste de mesclagem e na etapa de rejeição do candidato, mas elas foram corrigidas.Otimizações:
removeOverlap
foi projetado para fornecer sempre um conjunto de sub-strings na ordem idealuInsertMSpec
reduz check-if-is-member e insert-new-member para um conjunto transversalcontainmentNumbersSt
verifica se a solução anterior funciona para um novo númeroExperimente online!
Salvar em
main.icl
e compile com:clm -fusion -b -IL Dynamics -IL StdEnv -IL Platform main
Isso produz um arquivo
a.out
que deve ser executado comoa.out -h <heap_size>M -s <stack_size>M
, onde<heap_size> + <stack_size>
está a memória que será usada pelo programa em megabytes.(Geralmente, defino a pilha como 50 MB, mas raramente os programas usam essa quantidade)
fonte
Scala , pontuação 137Editar:
O código aqui simplifica demais o problema.
Portanto, a solução funciona para muitas entradas, mas não para todas.
Mensagem original:
Ideia básica
Problema mais simples
Primeiro, geramos o conjunto de números primos e removemos todos os que já são substrings de outros. Em seguida, podemos aplicar várias regras, ou seja, se houver apenas uma sequência terminando em uma sequência e apenas uma começando com a mesma sequência, podemos mesclá-las. Outro seria que, se uma string começa e termina com a mesma sequência (como 101), podemos anexá-la / anexá-la a outra string sem alterar as extremidades. (Essas regras são válidas apenas sob certas condições, portanto, tenha cuidado ao aplicá-las)
O verdadeiro problema
Depois, podemos pegar nosso algoritmo do problema simplificado para testar se há uma sequência começando comn k O(n⋅log(n))×the time for the simpler algorithm .
10103
0
, contendo todos10103
1
Portanto, se as regras no algoritmo acima fossem sempre suficientes, o problema teria mostrado não ser NP-difícil.
findSeq
Experimente on-line
Código
Como Anders Kaseorg apontou nos comentários, esse código pode retornar resultados abaixo do ideal (portanto, incorretos).
Resultados
Os resultados paran∈[1,200]
187
188
189
193
fonte
1234
,3423
,2345
, você gera123453423
em vez do ideal12342345
.457, 571, 757
(todos os números primos).findSeq
retornaria7574571
para isso, mas o menor comprimento é457571
. Portanto, sua abordagem está brincando com fogo. Promovido por pura audácia, no entanto.