Inteiros com perda única: sequências concatenadas sem um único elemento

18

Defino o método de combinar uma sequência para significar que todos os números na sequência são concatenados como uma sequência, e esse resultado é transformado em um número inteiro.

[1, 2, 3] -> 123

Para cada sequência finita de pelo menos 3 números inteiros consecutivos, faltando exatamente um elemento na sequência, e esse elemento ausente pode não ser o primeiro ou o último elemento na sequência, produza o número inteiro resultante da sequência combinada. Estou me referindo a isso como um "número inteiro com perda única".

[1, 2, 3] -> {1, 3} (missing an element) -> 13

Essa sequência de números inteiros com perda única é a união das seguintes subsequências (partições?):

A primeira subsequência {n, n+2}é A032607 .

{n, n+2}            -> 13, 24, 35, 46, 57, 68, 79, 810, 911, 1012, ...
{n, n+1, n+3}       -> 124, 235, 346, ...
{n, n+2, n+3}       -> 134, 245, 356, ...
{n, n+1, n+2, n+4}  -> 1235, 2346, 3457, ...
{n, n+1, n+3, n+4}  -> 1245, 2356, 3467, ...
{n, n+2, n+3, n+4}  -> 1345, 2456, 3567, ...
... 
for n ∈ ℕ (integers >= 1)

Esses números inteiros devem ser impressos em ordem crescente. Os primeiros 25 números inteiros com perda única estão abaixo :

13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, ...

Primeiros 7597 inteiros com perda única

Implementações de referência não destruídas. Eu fiz isso para ser mais rápido, ao invés de menor.

  • Ideone
  • TIO (limites mais rápidos e mais altos)

Regras:

  • O código mais curto vence
  • Você pode (diga qual):
    • Imprimir os números inteiros com perda única para sempre
    • Dado um número inteiro positivo n , imprima ou retorne os primeiros n elementos como uma lista ou como uma string delimitada por vírgula ou espaço em branco.
  • Você deve suportar números inteiros arbitrariamente grandes se o seu idioma permitir, especialmente se você estiver imprimindo para sempre.

Inspirado por / Relacionado

Nota: Ainda não há uma entrada no OEIS para esta sequência.

Outra observação: eu os nomeei "Inteiros com perdas simples", para que, por sua vez, possam ser "Inteiros com perdas duplas", "Inteiros com perdas n-ly", "Inteiros com perdas n-ly", "(N + 1) inteiros com perdas" e "Inteiros com perdas" "(união de todos estes).

mbomb007
fonte
Adicionei uma lista dos primeiros ~ 7600 elementos, bem como uma implementação de referência que acabei de concluir em Python.
mbomb007
2
Este seria um fastest-codedesafio divertido .
Michael Klein
Isso seria. É aceitável relançar um desafio, mas com um critério de vitória diferente? Se assim for, eu esperaria uma semana ou mais primeiro de qualquer maneira.
mbomb007
Até onde eu sei, tudo bem. Pode querer entrar no chat para pedir um mod, apenas no caso / para obter dicas.
Michael Klein

Respostas:

3

Mathematica, 101 bytes

Sort@Flatten@Table[FromDigits[""<>ToString/@(z~Range~x~Delete~y)],{x,3,#},{z,1,x-1},{y,2,x-z}][[1;;#]]&

Yay! Pela primeira vez eu tenho a resposta mais curta!Party[Hard]

CalculatorFeline
fonte
1
Isso é realmente um Mathematica embutido? Eu não ficaria surpreso. : D
mbomb007 23/02
4
Não, mas isso pode ser corrigido com Party[_]:=While[True,Print["PARTY!!!"]]. O argumento é ignorado porque todas as partes estão participando.
CalculatorFeline
1
@CatsAreFluffy Eu discordo. Party[Where]deve imprimir Here!e Party[When]deve imprimir Now!etc. Não pense levemente em festas.
Sanchises
Party[x_]:=Switch[x,Where,"Here!",When,"Now!",How,Pause[1];"...Really?",_,While [True,Print["PARTY!!!"]]]
CalculatorFeline
3

Haskell, 131 , 114 , 106 bytes

iterate(\n->minimum[x|x<-[read(show=<<filter(/=k)[i..j])::Int|i<-[1..n],j<-[i+2..n],k<-[i+1..j-1]],x>n])13

Isso é limitado pelo tamanho de Int, mas pode ser facilmente estendido substituindo-o Intpor Integer.

Menos golfe:

concatInt x = read (concatMap show x) ::Int
allUpToN n = [concatInt $ filter (/=k) [i..j] | i <- [1..n], j <- [i+2..n], k <- [i+1..j-1]]
f n = minimum[x | x <- allUpToN, x > n ]
iterate f 13

8 bytes jogados por @nimi.

Michael Klein
fonte
Isso é infinito, ou é preciso n?
mbomb007
@ mbomb007 Com Integer, continuará até você ficar sem memória (ou paciência). Ele continuará com Int, mas começará a dar respostas erradas assim que for excedido ( > 2^29-1).
Michael Klein
Você pode criar um link para um intérprete onde eu possa executar isso? Eu colei no TryHaskell.org e não funcionou.
mbomb007
@ mbomb007 O melhor que eu encontrei até agora é este , apesar de precisar main=print$que o GHCi não. O GHC.io fica sem memória e o conjunto de recursos do TryHaskell.org é muito limitado.
Michael Klein
Uau, não chega muito longe antes do tempo limite. : D
mbomb007
2

Python 3, 136 127 126 122 bytes

solução de força bruta, eu nem tento n = 7000 (já são necessários 10s para n = 100)

r=range
f=lambda n:sorted(int(''.join(str(i+k)for i in r(1,j)if l-i))for k in r(n)for j in r(4,n)for l in r(2,j-1))[:n]

Explicação

# f=lambda n:sorted( int(''.join(str(i+k) for i in r(1,j)   if l-i)) for k in r(n) for j in r(4,n) for l in r(2,j-1))[:n]
#            ──┬──                        ───────┬───────    ───┬──  ──────┬──────  ──────┬──────  ────────┬──────── ─┬─
#              │                                 │              │          │              │                │          └── selection of the n first numbers
#              │                                 │              │          │              │                └── loop to remove missing element
#              │                                 │              │          │              └── loop for the dimension of the list n to be sure we miss nothing xD
#              │                                 │              │          └── loop on the n in op description 
#              │                                 │              └── Test to remove missing element
#              │                                 └── loop on {n, n+1 ...} in the op description
#              └──── sort the list

Resultados

>>> f(25)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235]

>>> f(100)
[13, 24, 35, 46, 57, 68, 79, 124, 134, 235, 245, 346, 356, 457, 467, 568, 578, 679, 689, 810, 911, 1012, 1113, 1214, 1235, 1245, 1315, 1345, 1416, 1517, 1618, 1719, 1820, 1921, 2022, 2123, 2224, 2325, 2346, 2356, 2426, 2456, 2527, 2628, 2729, 2830, 2931, 3032, 3133, 3234, 3335, 3436, 3457, 3467, 3537, 3567, 3638, 3739, 3840, 3941, 4042, 4143, 4244, 4345, 4446, 4547, 4568, 4578, 4648, 4678, 4749, 4850, 4951, 5052, 5153, 5254, 5355, 5456, 5557, 5658, 5679, 5689, 5759, 5789, 5860, 5961, 6062, 6163, 6264, 6365, 6466, 6567, 6668, 6769, 6870, 6971, 7072, 7173, 7274, 7375]

Obrigado a @ mbomb007 e @FricativeMelon por sua ajuda

Erwan
fonte
Você não precisa de um espaço entre um )e o caractere a seguir, e pode adicionar t=rangeao início do programa e substituir todas rangeas chamadas de função por tchamadas. Isso deve reduzir muito a contagem de bytes.
Fricative Melon
@FricativeMelon bem, vou removido espaço inútil
Erwan
i!=l+ktambém pode ser substituído por l+k-i, o que salva um byte.
Fricative Melon
@FricativeMelon i adicionou-se uma pequena descrição :)
Erwan
str(i)for i in r(1+k,j+k)if l+k-ipode ser substituído por str(i+k)for i in r(1,j)if l-i, economizando 4 bytes.
mbomb007
1

Python 3, 319 , 270 , 251 bytes

t,h,n,k,q*=range,input(),1,2,
while h>len(q)or n*k<=len(str(q[h])):
 q+=[int("".join([str(c+s)for c in t(k+1)if c-y]))for s in t(10**~-n,10**n)for y in t(1,k)]
 if~-n:n*=k;k+=1
 else:n,k=k+1,2
 while n//k*k-n:k+=1
 n//=k;q.sort()
print(q[:h])

Toma uma hentrada como de STDIN e imprime uma matriz dos primeiros hnúmeros inteiros com perda única. Também é muito rápido, levando apenas alguns segundos h=7000.

Explicação: Observe que, se tivéssemos tempo infinito, poderíamos simplesmente iterar sobre todos n,ke, para cada par, soltar cada uma das n+1,n+2,...,n+k-1( k-1possibilidades) e obter todos os valores (infinitamente muitos) desses, basta classificar a sequência em ordem crescente e truncar para helementos. Obviamente, não podemos realmente fazer isso, mas se pudermos chegar a um ponto em que os primeiros helementos classificados não possam mais mudar adicionando os valores de quaisquer n,kpares futuros , podemos apenas truncar e terminar em tempo finito. Para qualquer n,kpar, ele tem pelo menos floor(log10(n)+1)*kdígitos, possivelmente mais. Então, vamos agrupar esses pares pelo valor c(n,k)=floor(log10(n)+1)*k, onde garantimos que c(a,b)<c(n,k), se processarmos a,bantes n,k. Se tivermos a lista classificada e seu último elemento tiverddígitos e, d<c(n,k)para o próximo n,kprocesso, podemos parar, já que não podemos mais obter um número com tantos ou menos dígitos, pois, como garantia, já deveríamos processá-lo e, portanto, independentemente dos números que acabaria computando, os primeiros helementos não podem mudar, para que possamos devolvê-los.

Então agora precisamos da função que garante a ordem declarada c(n,k). Para cada um yobtido c(n,k), precisamos processar tudo (n,k)isso y=c(n,k). Vamos dizer L=floor(log10(n)+1)para alguns n. Portanto, y=L*kdeve aguentar. Comece com k=2,L=y/2, k=3,L=y/3;k=4,L=y/4...k=y,L=1ignorando valores não inteiros de L. Para gerar toda a c(n,k)função, comece com (1,2)com y=2, e aumentar ypor 1 e começar de novo sempre que você receber L==1. Agora, temos uma enumeração de pares (L,k)e ela satisfaz nossa condição. No entanto, precisamos recuperar todos os possíveis na partir L, o que fazemos, enumerando todos os inteiros com Ldígitos. Então, para cada um desses (n,k)pares, para cada um dosk-1possíveis elementos eliminados, devemos gerar o número de perdas que obtemos como resultado e adicioná-lo à nossa lista, que começa vazia. Depois, ordenamos a lista e repetimos no próximo (L,k)par, parando quando temos o que d<c(n,k)foi dito anteriormente.

Repartição de código (um pouco desatualizada):

t=range                     #shortens code
def f(r,n,k):               #helper function
 for s in t(10**~-n,10**n): #for the (L,k) pair, add value of (s,k,y)
  for y in t(1,k):r+=[(int("".join(map(str,[c+s for c in t(k+1)if c!=y]))))]
 if n>1:                    #case where L!=1
  n*=k;k+=1                 #multiply n (which is n'/k from prev iter), inc k
 else:n,k=k+1,2             #reset n and k
 while n//k*k-n:k+=1        #find next proper divisor of n
 return(r,n//k,k)           #divide by that divisor and return
def g(h):                   #main function
 q,a,b=[],1,2               #initial values
 while h>=len(q)or a*b<=len(str(q[h])):(q,a,b)=f(q,a,b);q.sort()
 return q[:h]               #continues until at least h numbers and surpassed current max
Melão Fricativo
fonte
Eu acho que len(`q[h]`)deveria len(str(q[h]))apoiar números inteiros arbitrários? Ou apenas diga se funciona apenas até um determinado limite, pois você está usando um parâmetro e não imprimindo para sempre.
mbomb007
Eu pensei que `x` == repr (x) == str (x) para números inteiros não negativos, e não consigo encontrar nenhuma referência a isso não ser verdade. Por que você acha que isso não é verdade?
Fricative Melon
Eu sei que isso não é verdade, porque freqüentemente jogo golfe em Python. Exemplo . Qualquer coisa maior que o valor máximo inteiro ( 2**63-1) terá um Lno final, se estiver usando repr. Observe que essa entrada provavelmente está muito adiantada na sequência.
Mbomb007