Imagine um "fio" que tenha nespaços. Imagine ainda que existem "elétrons" nesse fio. Esses elétrons vivem apenas uma unidade de tempo. Quaisquer espaços no fio adjacentes a exatamente um elétron se tornam um elétron. Na terminologia de Game of Life, é isso B1/S.

Por exemplo, este é um fio de comprimento 10, com período 62.

Regras

• Input,, né um número inteiro único positivo.
• A saída deve ser um número inteiro único que denota o período de um fio de comprimento n.
• O estado inicial é um único elétron em uma extremidade do fio.
• O período não inclui necessariamente o estado inicial. Alguns comprimentos nunca retornam ao estado inicial, mas todos são periódicos.
• Um fio estático (ou seja, um sem elétrons) tem o período 1.
• As condições de contorno não são periódicas. Ou seja, o fio não é toroidal de forma alguma.

Casos de teste

Agradecimentos especiais ao orlp por produzir esta lista. (Eu verifiquei até n = 27).

1 1
2 2
3 1
4 6
5 4
6 14
7 1
8 14
9 12
10 62
11 8
12 126
13 28
14 30
15 1
16 30
17 28
18 1022
19 24
20 126
21 124
22 4094
23 16
24 2046
25 252
26 1022
27 56
28 32766
29 60
30 62
31 1
32 62
33 60
34 8190
35 56
36 174762
37 2044
38 8190
39 48
40 2046
41 252
42 254
43 248
44 8190
45 8188

Você pode ver casos de teste de n = 2 a 21 aqui com meu simulador de jogo da vida: Variações da vida .

EDIT: a sequência aqui foi publicada como A268754 !

Python 2, 148 142 87 bytes

n=input()
p=l=1
t=1
h=2
while t!=h:
 if p==l:t,l,p=h,0,p*2
 h=h/2^h*2%2**n;l+=1
print l

Usa o algoritmo de detecção de ciclo do Brent e, portanto, é executado rapidamente.

Também escrevi uma animação em Python (ambos os trabalhos 2 e 3). Ele precisa pygletcorrer. Você pode ver a animação executando:

python -m pip install --user pyglet
curl -s https://gist.githubusercontent.com/orlp/f32d158130259cbae0b0/raw/ | python

(Sinta-se à vontade para fazer o download da essência e inspecionar o código antes de executar.) Você pode pressionar as teclas + e - para aumentar / diminuir o n sendo visualizado.

E, finalmente, para os interessados ​​em explorar ainda mais essa sequência numérica, aqui está uma versão legível (usada para gerar os casos de teste acima):

# Brent's cycle detection, modified from wikipedia.
def electron_period(n):
    wire_mask = (1 << n) - 1
    power = lam = 1
    tortoise, hare = 1, 2
    while tortoise != hare:
        if power == lam:
            tortoise = hare
            power *= 2
            lam = 0
        hare = ((hare << 1) ^ (hare >> 1)) & wire_mask
        lam += 1
    return lam

Mathematica, 127 bytes

p@n_:=Tr[#2-#]&@@Position[#,Last@#]&@NestWhileList[1~Table~n~ArrayPad~1*18~CellularAutomaton~#&,{1}~ArrayPad~{1,n},Unequal,All]

Explicação

Artigo 18 :

{0,0,0} -> 0
{0,0,1} -> 1
{0,1,0} -> 0
{0,1,1} -> 0
{1,0,0} -> 1
{1,0,1} -> 0
{1,1,0} -> 0
{1,1,1} -> 0

Casos de teste

p/@Range[10]
(* {1,2,1,6,4,14,1,14,12,62} *)

Python 2, 68 bytes

f=lambda n,k=1,l=[]:k in l and-~l.index(k)or f(n,k/2^k*2%2**n,[k]+l)

A detecção do ciclo poderia ser melhor, mas a etapa iterativa é agradável.

k -> k/2^k*2%2**n

Ao representar a matriz como um número binário k, a atualização pode ser feita retirando o XOR de kum para a esquerda /2e outro para a direita e *2, em seguida, truncando para nbytes como %2**n.

Python 3 2, 134 121 118 bytes

Q=input()
h=[]
n=[0,1]+Q*[0]
while n not in h:h+=[n];n=[0]+[n[d]^n[d+2] for d in range(Q)]+[0]
print len(h)-h.index(n)

Basicamente, o mesmo que a minha resposta Pyth , mas a adaptou um pouco por causa da falta de certas funções internas no Python.

Versão não destruída:

length = input()
history = []
new = [0] + [1] + length*[0]
while new not in history:
    history += [new]
    new = [0] + [new[cell]^new[cell+2] for cell in range(length)] + [0]
print len(history) - history.index(new)

Pitão, 39 36 bytes

L++Zmx@[email protected].[,Z1ZQ)xJyeJ

Usa a função "ponto fixo cumulativo" para iterar até pouco antes de a configuração se repetir e retorna todas as configurações intermediárias como uma lista de listas. Isso funciona porque as regras são determinísticas e a configuração da próxima geração é uma função da configuração atual. Isso significa que quando a mesma configuração aparecer novamente, os autômatos concluíram um ciclo.

Depois de atingir isso (a última iteração do ciclo), ele chama a função de próxima geração uma última vez no último elemento da lista "history", para obter a próxima configuração (que é a configuração inicial de um ciclo) e encontre seu índice na história. Agora, o período é simplesmente a duração (1 + índice de final do ciclo) menos o índice de início do ciclo.

No pseudocódigo pitônico:

                  Z = 0
                  Q = eval(input())
L                 def y(b):                # generates next-gen from current(param)
  ++Zm                return [Z] + map(    # adds head zero padding
    x@bd@bhhd             lambda d: b[d] ^ b[1+ 1+ d],  # xor the states of adjacent cells
    Q                     range(Q))        # implicit range in map
    Z                     + [Z]            # adds end zero padding
-lJ.uyN.[,Z1ZQ)   J = repeatTilRecur(lambda N,Y:y(N), padRight([Z,1],Z,Q)); print( len(J) -
                  # N:value; Y:iteration count
  JxJyeJ              J.index( y( J[-1] ) ) )

O conjunto de testes leva muito tempo para que o servidor o mate, portanto, você precisará usar o programa regular e testá-lo um por um, ou instalar o Pyth (se não tiver) e usar um script para testá-lo.

Geléia, 19 18 17 bytes

H^Ḥ%®
2*©Ç‘СUµiḢ

Esse código calcula os primeiros 2 ⁿ estados, portanto, não é particularmente rápido ou eficiente em termos de memória ...

Experimente online! ou verifique os 16 primeiros casos de teste .

Versão alternativa, 13 bytes (não concorrente)

As versões do Jelly que pós-datam esse desafio têm detecção de loop integrada, permitindo uma solução mais curta e mais eficiente.

H^Ḥ%®
2*©ÇÐḶL

Isso lida com o último caso de teste com facilidade. Experimente online!

Como funciona

2*©Ç‘СUµiḢ    Main link. Input: n (integer)

2*             Compute 2 ** n.
  ©            Store the result in the register.
     С        Do the following:
   Ç             Apply the helper link, which updates the state, ...
    ‘            2 ** n + 1 times.
               Collect all 2 ** n + 2 intermediate results in a list.
       U       Upend; reverse the list of results.

        µ      Begin a new, monadic chain. Argument: R (list of results)
          Ḣ    Yield and remove the first element of R (final state).
         i     Find its first index in the remainder or R.
               This is the length of the loop.

H^Ḥ%®        Helper link. Argument: s (state, integer)

H            Halve s. This yields a float, but ^ will cast to integer.
  Ḥ          Double s.
 ^           Compute (s ÷ 2) ^ (s × 2).
    ®        Retrieve the value stored in the register (2 ** n).
   %         Compute ((s ÷ 2) ^ (s × 2)) % (2 ** n).

Observe que o link auxiliar é aplicado a 2 ⁿ na primeira iteração, que não codifica um estado válido. No entanto, ((2 ⁿ ÷ 2) ^ (2 ⁿ × 2))% 2 ⁿ = (2 ^{n - 1} + 2 ^{n + 1} )% 2 ⁿ = 2 ^{n - 1} , que é um dos possíveis estados iniciais.

Como fazemos um loop 2 ⁿ + 1 vezes, temos a garantia de encontrar um estado duas vezes, tornando a detecção do loop bem-sucedida.

CJam, 41 34 31 27 25 bytes

Agradecimentos a Dennis por salvar 3 bytes. Tomar emprestada uma idéia de sua resposta Jelly salvou outras 4.

2ri#_){__4*^2/W$%}*]W%(#)

Teste aqui.

Explicação

Estou representando o fio simplesmente como um número inteiro (cujos bits indicam as posições dos elétrons) em vez de usar uma lista real de bits. O estado é atualizado por meio de cálculos bit a bit bastante simples.

Para encontrar o período em que coletamos todos os resultados intermediários na pilha, execute a simulação para 2 etapas ^n-1 +1 e determine o período como o número de elementos desde a última ocorrência do estado final (mais 1).

Aqui está um detalhamento do código:

2ri#   e# Compute 2^n. This has a 1 in the n+1-th bit and zeroes below it. This is
       e# itself not a valid state but will be turned into 2^(n-1) by the first
       e# update.
_)     e# Duplicate and increment to get number of steps to simulate.
{      e# Repeat that many times...
  __   e#   Duplicate the last state twice.
  4*   e#   Multiply by 4, shifting all bits to the left by two positions.
  ^    e#   XOR - we only keep keep those cells where we have exactly one 1-bit
       e#   between both copies, i.e. those that neighboured a single electron
       e#   but shifted up by one position. We don't need handle the survival rule
       e#   explicitly, since electrons can never be adjacent in the first place.
  2/   e#   Divide by 2 shifting all bits back to the right again.
  W$   e#   Copy the initial number 2^n.
  %    e#   Modulo - this simply sets the first bit to 0.
}*
]      e# Wrap all states in an array.
W%     e# Reverse it.
(      e# Pull off the latest state.
#      e# Find its position in the remainder of the array.
)      e# Increment.

JavaScript (ES6) 99 104

n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

Teste

f = n=>eval("a=[...Array(n)];k={};for(a[0]=i=1;!k[a=a.map((v,i)=>v?0:a[i-1]^a[i+1])];k[a]=i++);i-k[a]")

console.log = x => O.textContent += x + '\n';

;[...Array(45)].map((_, i) => console.log(++i + ' ' + f(i)))

<pre id=O></pre>

Haskell, 170 bytes

x!pfornece o elemento no índice p se estiver dentro dos limites, caso contrário, 0. ncalcula o próximo passo. g idá o ipasso th. c xfornece o período, se começar com x. fenvolve tudo junto.

n x|l<-length x-1=[mod(x!(p-1)+x!(p+1))2|p<-[0..l],let y!q|q<0=0|q>=l=0|1<2=y!!p]
c x=[i-j|i<-[1..],j<-[0..i-1],let g k=iterate n x!!k,g i==g j]!!0
f n=c$1:map(*0)[2..n]

(Nota: postado no telefone que possui o intérprete de abraços, que não possui todos os recursos, pode haver erros de digitação.)

MATL , 38 37 36 35 bytes

1Oi(`t0Y)5BX+8L)1=vt6#Xut0)=fdt?w}A

Isso usa um loop que continua computando novos estados até que o novo estado seja igual a qualquer um dos anteriores. Cada estado é um vetor de zeros e uns. Esses vetores são armazenados como linhas de uma matriz 2D crescente.

A computação de cada novo estado é feita através da convolução do estado atual com a sequência [1,0,1], mantendo apenas a parte central e definindo 0qualquer entrada que não seja 1.

EDIT (13 de maio de 2016) O código no link a seguir foi ligeiramente modificado de acordo com as alterações introduzidas no idioma após a redação desta resposta

Experimente online!

1Oi(            % create initial vector [1,0,0,...,0], with size equal to input
`               % do...while loop
  t0Y)          %   duplicate. Get last row of array: most recent vector
  5BX+8L)       %   compute new vector by convolving the most recent one
                %   with [1,0,1] and keeping only the central part
  1=            %   set ones to 1, rest to 0
  v             %   append to 2D array
  t6#Xu         %   compute vector of unique numeric labels, so that equal rows
  t0)=f         %   indices of entries whose value equals that of the last entry.
                %   This will contain the index of the last entry and possibly
                %   another index, in which case we've found a repetition
  d             %   this will either be empty (which is falsy) or contain the
                %   period, which is a nonzero number (and thus truthy)
  t?            %   duplicate. If non-empty (and nonzero)
    w           %     swap to put the 2D-array at the top of the stack. This is
                %     falsy, because it contains at least one zero, even in the
                %     n=1 case (the array is initiallized to 0 in that case)
                %     So the loop will terminate, with the period left on the stack
  }             %   else
    A           %     this transforms the empty array at the top of the stack
                %     into a true value, so that the loop will continue
                %   implicitly end if
                % implicitly end loop
                % implicitly display stack contents (period)

Perl 6, 81 bytes

{my@h=my$w=2;@h.push($w=$w/2+^$w*2%2**$_)while 2>@h.grep($w);[R-] @h.grep($w,:k)}

Expandido e não destruído um pouco

-> $n {
    my @history = my $wire = 2;
    while 2 > @history.grep($wire) {
        @history.push($wire = $wire/2 +^ $wire*2 % 2**$n)
    }
    [R-] @history.grep($wire,:k)
}

Um pouco de explicação:

• [op]reduz a lista usando op. Por exemplo [+] @list, somará@list
• Ré uma meta-op que reverte os argumentos dados a uma op. Por exemplo 1 R- 3, resultará em 2.

C ++, 211 bytes

Golfe

#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);int main() {int p,l;for(scanf("%d",&p);p--;m.set(p));
for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;return !printf("%d",l);}

Com espaço em branco adicional para facilitar a leitura

#include <bitset>
#include <cstdio>
#define B std::bitset<1<<10>
B m,t(1),h(2);
int main() {    
    int p,l;
    for(scanf("%d",&p);p--;m.set(p));
    for(p=l=1;t!=h;h=(h>>1^h<<1)&m,l++)p==l?t=h,p*=2,l=0:0;    
    return !printf("%d",l);
}

Boas práticas para o conjunto de bits do C ++; e um ótimo aprendizado educacional sobre o algoritmo de detecção de ciclo de Brent (usado pelo @orlp)

Pitão, 95 bytes

J.[ZQ[1)K_1=bYW<K0=NY aN?hJZ?htJ1ZFTr1tlJ aN?@JTZ?x@JhT@JtT1Z) aN?eJZ?@J_2 1Z=JN=KxbJ abJ;-tlbK

Você pode experimentá-lo aqui .

Pitão, 29 bytes

J^2QL%x/b2*b2JK.uyN1;-lKxKyeK

• Experimente online!
• Suíte de teste

Usa o algoritmo a(n+1) = ((a(n) << 1)^(a(n) >> 1)) % (2 ** N).

Ruby, 72 bytes

Função anônima.

->n{s=[w=1];c=p
(j=s.index w=w*2%2**n^w/2
j ?c=s.size-j:s<<w)while !c
c}