OEIS tem uma variação (A111439) na sequência de Golomb . Como na sequência de Golomb, A(n)descreve com que frequência naparece na sequência. Além disso, dois números consecutivos não podem ser idênticos. Durante a construção da sequência, A(n)sempre é escolhido como o menor número inteiro positivo que não viola essas duas propriedades. Devido a números idênticos consecutivos não permitidos, a série oscila levemente para cima e para baixo à medida que cresce. Aqui estão os 100 primeiros termos:

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, 7, 8, 9, 8, 9, 8, 9, 
10, 9, 10, 9, 10, 11, 10, 11, 10, 11, 10, 11, 12, 11, 12, 13, 12, 13, 12, 
13, 12, 13, 12, 13, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 14, 15, 16, 15, 
16, 17, 16, 17, 16, 17, 16, 17, 16, 17, 18, 17, 18, 17, 18, 19, 18, 19, 18, 
19, 18, 19, 18, 19, 18, 19, 20, 19, 20, 21, 20, 21, 20, 21, 20, 21, 20

A lista completa dos primeiros 10.000 números pode ser encontrada no OEIS .

O desafio é escrever um programa ou função que calcule A(n), dado n. né 1baseado em para garantir que a propriedade autoexplicativa funcione.

Regras

Você pode escrever um programa ou uma função e usar qualquer um dos nossos métodos padrão de recebimento de entrada e saída.

Você pode usar qualquer linguagem de programação , mas observe que essas brechas são proibidas por padrão.

Isso é código-golfe , então a resposta mais curta e válida - medida em bytes - vence.

Casos de teste

n     A(n)
1     1
4     2
10    6
26    10
100   20
1000  86
1257  100
10000 358

Haskell , 67 bytes

f k|k<4=k|p<-k-1=[n|n<-[1..],n/=f p,sum[1|a<-[1..p],f a==n]<f n]!!0

Define uma função f. Experimente online! É muito lento, o f 15tempo limite de computação no TIO.

Explicação

Seguindo a definição: em cada estágio, escolha o número mínimo positivo nque satisfaça as restrições (não é igual à entrada anterior e ainda não ocorreu f nvezes).

f k             -- Define f k:
 |k<4=k         -- If k < 4, it's k.
 |p<-k-1=       -- Otherwise, bind k-1 to p,
  [n|           -- compute the list of numbers n where
   n<-[1..],    -- n is drawn from [1,2,3,...],
   n/=f p,      -- n is not equal to f p, and
   sum[1|       -- the number of
    a<-[1..p],  -- those elements of [1,2,3,...,p]
    f a==n]     -- whose f-image equals n
   <f n]        -- is less than f n,
  !!0           -- and take the first element of that list.

Mathematica, 69 68 bytes

Obrigado a Martin Ender por ter encontrado um byte extra de 1 byte para mim!

Last@Nest[{##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&,{},#]&

Função sem nome, recebendo um número inteiro positivo ncomo entrada e retornando um número inteiro positivo. Construímos a lista inteira dos primeiros nelementos dessa sequência e pegamos o Lastelemento. A lista é construída começando com a lista vazia {}e operando nela com ntempos de função seguidos (via Nest).

A função em questão é {##&@@#,1//.x_/;x==Last@#||#~Count~x==#[[x]]->x+1}&, que pega uma lista parcial de valores de sequência (essencialmente ##&@@#) e acrescenta o próximo valor a ela. O próximo valor é calculado começando com x=1, então repetidamente substituindo xpor x+1enquanto a condição x==Last@#||#~Count~x==#[[x]]for cumprida, em outras palavras, se quer xé o elemento anterior, ou então xjá está na lista o número correto de vezes. Esta função cospe alguns erros, pois (por exemplo) não devemos chamar o xth-elemento da lista inicial {}; no entanto, todos os valores estão corretos.

Python 2, 99 86 bytes

Obrigado a @Dennis por várias melhorias, totalizando 13 bytes!

s=0,1,2,3
exec't=1\nwhile t==s[-1]or s.count(t)/s[t]:t+=1\ns+=t,;'*input()
print s[-4]

O programa prossegue de maneira bastante ingênua: mantém o controle da lista de valores determinados até o momento e procura anexar o próximo valor. Ele tenta anexar 1a ao final da lista, se puder; caso contrário, ele tenta um 2e assim por diante até que algo seja permitido.

Agora, começamos semeando os resultados para 1,2,3ser 1,2,3. Isso é feito para evitar problemas com a lista de valores já calculados muito curta: conjecturo que se né pelo menos, 4então a(n)é estritamente menor que n. (Neste programa, s[n]é igual a a(n). Nossa lista, na verdade, é inicializada [0,1,2,3]porque as listas são 0indexadas em Python. Assim, por exemplo a(1)=s[1]=1, e a(2)=s[2]=2.)

Então, digamos que estamos tentando determinar s[m], o que significa que nossa lista já inclui s[0], s[1], ..., s[m-1]. Vamos começar t=1e tentar definir s[m]=1. Quando isso não funciona, vamos t=2e tentamos definir s[m]=2. Cada vez que incrementamos t, verificamos se s.count(t)==s[t]... mas o lado direito não produz um erro, desde que nunca tenhamos que ir tão alto quanto t=m. A conjectura diz que nunca precisamos, pois o primeiro valor que calculamos é realmente s[4].

Esta implementação calcula mais 3 valores da sequência do que precisa. Por exemplo, se nfor 8, ele será calculado s[11]antes de retornar o valor de s[8].

Eu ficaria feliz em ver uma prova da conjectura. Eu acredito que isso pode ser provado por indução (forte?).

Edit: Aqui está uma prova da conjectura . Na verdade, provamos uma forma um pouco mais forte da declaração, já que ela não envolve trabalho extra.

Teorema: Para todos nmaiores ou iguais a 4, o termo a(n)é menor ou igual a (n-2).

Prova (por forte indução): (Base n=4): A afirmação é verdadeira para n=4, desde a(4) = 2 = 4-2.

Agora vamos supor a(k)é inferior ou igual a k-2para todos ka partir de 4meio n, inclusive (e assumir n, pelo menos 4). Em particular, isso significa que todos os termos anteriores da sequência foram no máximo (n-2). Precisamos mostrar que a(n+1)será no máximo (n-1). Agora, por definição, a(n)é o menor número inteiro positivo que não viola nenhuma das condições, portanto, apenas precisamos mostrar que o valor (n-1)não violará nenhuma das condições.

O valor (n-1)não violará a condição "sem repetições consecutivas", porque pela hipótese de indução a entrada anterior era no máximo (n-2). E não violará a condição " a(m)é o número de vezes que maparece", a menos (n-1)que já tenha sido atingido a(n-1). Mas, pela forte suposição de indução, (n-1)já haviam sido alcançados 0tempos e a(n-1)não é igual a, 0pois a(m)é positivo para todos m.

Portanto, a(n+1)é menor ou igual a n-1 = (n+1)-2, conforme desejado. QED.

Geléia , 17 bytes

Ṭ€S<;1Tḟ®Ḣ©ṭ
⁸Ç¡Ṫ

Os últimos três casos de teste são demais para o TIO. Eu verifiquei 1000 e 1257 localmente.

Experimente online! ou verifique os 100 primeiros termos .

Como funciona

⁸Ç¡Ṫ          Main link. No arguments.

⁸             Yield [].
 Ç¡           Execute the helper link n times (where n is an integer read from
              STDIN), initially with argument [], then with the previous return
              value as argument. Yield the last return value.
              Tail; yield the last element of the result.


Ṭ€S<;1Tḟ®Ḣ©ṭ  Helper link. Argument: A (array)

Ṭ€            Untruth each convert each k into an array of k-1 zeroes and one 1.
  S           Sum; column-wise reduce by +, counting the occurrences of all
              between 1 and max(A).
   <          Compare the count of k with A[k] (1-indexed), yielding 1 for all
              integers that still have to appear once or more times.
    ;1        Append a 1 (needed in case the previous result is all zeroes).
      T       Truth; find all indices of ones.
       ḟ®     Filter-false register; remove the value of the register (initially 0)
              from the previous result.
         Ḣ©   Head copy; yield the first (smallest) value of the result and save
              it in the register.
           ṭ  Tack; append the result to A.

Python 2 , 77 74 bytes

f=lambda n,k=1:n*(n<4)or map(f,range(n)+k*[n-1]).count(k)<f(k)or-~f(n,k+1)

Esta é uma implementação recursiva do algoritmo do @ mathmandan .

A implementação é O (insana) : a entrada 9 leva 2 segundos localmente, a entrada 10 52 segundos e a entrada 11 17 minutos e 28 segundos. No entanto, se declarada como uma função regular e não como uma lambda, a memorização pode ser usada para verificar os casos de teste.

Experimente online!

Observe que, mesmo com memorização, o TIO não pode calcular f (1257) ou f (10000) (ambos verificados localmente).

05AB1E , 32 31 bytes

XˆXˆG[N¯2(è<›¯¤NÊsN¢¯Nè‹&&#]N.ˆ

Experimente online!

Explicação

XˆXˆ                             # initialize global list as [1,1]
    G                            # input-1 times do:
     [                    #]     # loop until expression is true     
      N¯2(è<›                    # n > list[-2]-1
             ¯¤NÊ                # list[-1] != N
                 sN¢¯Nè‹         # count(list, N) < list[N]
                        &&       # logical AND of the 3 expressions
                            N.ˆ  # add N to global list 
                                   and output last value in list and end of program

Tecnicamente, estamos em loop Gquando adicionamos N à lista global, mas todos os loops em 05AB1E usam a mesma variável N que o índice; portanto, o loop interno [...]substituiu o N de Gsignificado, podemos adicioná-lo fora do loop.

Problemas com loops e condicionais aninhados nos impedem de fazer isso dentro do loop.

Befunge, 141 136 bytes

<v9\0:p8\2:*2:-1<9
v>p1+:3\8p0\9p:#^_&
>1-:#v_1.@>$8g.@
*+2%\>1-:!|>$!:::9g!\!9g!*\:8g\!8g`
9\+1g9::< \|`g9\g8+2::p
g2+\8p2+^:<>:0\9p::8

Experimente online!

Devido às limitações de memória do Befunge, não é realmente prático acompanhar todas as entradas de entradas anteriores na sequência, portanto, esta solução usa um algoritmo com menor espaço de memória que calcula os valores mais diretamente.

Dito isto, ainda estamos limitados pelo tamanho da célula, que no intérprete de referência Befunge-93 é um valor assinado de 8 bits, portanto, o maior número par suportado na sequência é A(1876) = 126e o maior número ímpar suportado A(1915) = 127.

Se você quiser testar valores maiores, precisará usar um intérprete com um tamanho de célula maior. Isso deve incluir a maioria das implementações do Befunge-98 ( Experimente online! ).

Python 2, 117 bytes

Meh. Não é tão curto. A solução iterativa simples.

L=[1,2,3]
n=input()
while len(L)<n:
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:L+=[i];break
print L[n-1]

Experimente online

Aqui está uma tentativa muito ruim de uma solução recursiva (129 bytes):

def f(n,L=[1,2,3]):
 if len(L)>=n:print L[n-1];exit(0)
 for i in range(2,n):
    if L.count(i)<L[i-1]and L[-1]!=i:f(n,L+[i])
 f(n,L)