Dado dois inteiros positivos p e q , sua tarefa é voltar a matriz A criado por aplicar o seguinte algoritmo:

1. Iniciar com A = [P, Q] e d = 2
2. Para cada par (x, y) de números contíguos em A cuja soma é divisível por d , insira (x + y) / d entre x e y .
3. Se pelo menos um par correspondente foi encontrado, aumente d e prossiga com a etapa 2. Caso contrário, parada e retorno A .

Exemplo

Abaixo está o detalhe do processo para p = 1 e q = 21 .

  1  21             | Iteration #1: we start with d = 2 and A = [1, 21]
   \/               |               1 + 21  is divisible by 2 -> we insert 11
 22/2=11            |
                    |
  1  11 21          | Iteration #2: d = 3, A = [1, 11, 21]
   \/               |               1 + 11  is divisible by 3 -> we insert 4
 12/3=4             |
                    |
  1 4 11  21        | Iteration #3: d = 4, A = [1, 4, 11, 21]
        \/          |               11 + 21 is divisible by 4 -> we insert 8
      32/4=8        |
                    |
  1    4    11 8 21 | Iteration #4: d = 5, A = [1, 4, 11, 8, 21]
    \/   \/         |               1 + 4   is divisible by 5 -> we insert 1
  5/5=1 15/5=3      |               4 + 11  is divisible by 5 -> we insert 3
                    |
  1 1 4 3 11 8 21   | Iteration #5: d = 6, A = [1, 1, 4, 3, 11, 8, 21]
                    |               no sum of two contiguous numbers is divisible by 6
                    |               -> we stop here

Daí a saída esperada: [1, 1, 4, 3, 11, 8, 21]

Esclarecimentos e regras

• Entrada e saída podem ser manipuladas em qualquer formato razoável. O inteiros p e q são garantidos para ser maior que 0. Se isso ajuda, você pode assumir q ≥ p .
• A segunda etapa do algoritmo não deve ser aplicada recursivamente aos elementos que foram inseridos na mesma iteração. Por exemplo, A = [1, 1] e d = 2 devem levar a [1, 1, 1] (não uma lista infinita de 1's).
• Isso é código-golfe , então a resposta mais curta em bytes vence!

Casos de teste

  p |   q | Output
----+-----+-------------------------------------------------------------------------------
  1 |   1 | [1,1,1]
  1 |   2 | [1,2]
  1 |   3 | [1,1,2,3]
  2 |   6 | [2,1,2,1,4,1,2,6]
  3 |  13 | [3,1,8,1,3,1,7,1,2,1,5,1,3,2,13]
  9 |   9 | [9,6,9,6,9]
 60 |  68 | [60,13,1,4,31,2,3,5,2,19,64,7,13,1,2,5,2,27,44,3,4,8,2,1,12,1,5,3,28,2,4,16,1,
    |     |  2,12,1,2,1,10,1,6,68]
144 | 336 | [144,68,3,4,8,1,12,1,4,2,28,13,128,44,17,92,240,58,108,5,17,1,2,5,3,28,3,1,11,
    |     |  60,3,6,2,42,2,4,26,192,54,132,7,1,15,1,3,1,18,1,4,2,30,3,1,12,1,9,78,46,336]

Se você deseja testar seu código em um caso de teste um pouco maior, veja a saída esperada para:

• p = 12096 (2 ⁶ * 3 ³ * 7)
• q = 24192 (2 ⁷ * 3 ³ * 7)

05AB1E , 28 19 18 bytes

[Ðü+NÌ/‚ζ˜ʒ.ï}DŠQ#

Experimente online!

eh, definitivamente pode ser melhorado hardcore. ainda trabalhando para refatorar.

Provavelmente tão bom quanto eu estou conseguindo.

-1 Obrigado a quem mais, Emigna! Por apontar a troca funcionou melhor do que os registros.

[                   // Infinite loop.
 Ð                  // Triplicate [p, ..., q]
  U                 // Pop 1 of 3 copies into register X.
   ü+               // Pairwise addition.
     NÌ/            // Divide by current iteration + 2 (which is d).
        ‚           // Group original [p, ..., q] with pairwise additives.
         ζ˜         // Transpose together and flatten.
           ʒ.ï}     // Filter out non-integer entities (includes the space added by zip).
               DXQ  // Dupe result, see if equal to original.
                  # // If new array is original array, nothing happened, quit & return.

Despejo de depuração para [p,q] = [1,3]:

Full program: [ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> [  ||  stack: []
ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: []
current >> U  ||  stack: [[1, 3], [1, 3], [1, 3]]
current >> ü  ||  stack: [[1, 3], [1, 3]]
Full program: +
current >> +  ||  stack: [1, 3]
stack > [4]
current >> N  ||  stack: [[1, 3], [4]]
current >> Ì  ||  stack: [[1, 3], [4], 0]
current >> /  ||  stack: [[1, 3], [4], 2]
current >> ‚  ||  stack: [[1, 3], [2.0]]
current >> ζ  ||  stack: [[[1, 3], [2.0]]]
current >> ˜  ||  stack: [[[1, 2.0], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 2.0, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 2.0, 3]]
current >> X  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
current >> Q  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 3]]
current >> #  ||  stack: [[1, 2.0, 3], 0]
stack > [[1, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 2.0, 3]]
current >> U  ||  stack: [[1, 2.0, 3], [1, 2.0, 3], [1, 2.0, 3]]
current >> ü  ||  stack: [[1, 2.0, 3], [1, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 2.0]
stack > [3.0]
Full program: +
current >> +  ||  stack: [3.0, 2.0, 3]
stack > [3.0, 5.0]
current >> N  ||  stack: [[1, 2.0, 3], [3.0, 5.0]]
current >> Ì  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 1]
current >> /  ||  stack: [[1, 2.0, 3], [3.0, 5.0], 3]
current >> ‚  ||  stack: [[1, 2.0, 3], [1.0, 1.6666666666666667]]
current >> ζ  ||  stack: [[[1, 2.0, 3], [1.0, 1.6666666666666667]]]
current >> ˜  ||  stack: [[[1, 1.0], [2.0, 1.6666666666666667], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 1.0, 2.0, 1.6666666666666667, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.6666666666666667]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 0]
stack > [[1, 1.0, 2.0, 3]]
Full program: ÐUü+NÌ/‚ζ˜ʒ.ï}DXQ#
current >> Ð  ||  stack: [[1, 1.0, 2.0, 3]]
current >> U  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> ü  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
Full program: +
current >> +  ||  stack: [1, 1.0]
stack > [2.0]
Full program: +
current >> +  ||  stack: [2.0, 1.0, 2.0]
stack > [2.0, 3.0]
Full program: +
current >> +  ||  stack: [2.0, 3.0, 2.0, 3]
stack > [2.0, 3.0, 5.0]
current >> N  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0]]
current >> Ì  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 2]
current >> /  ||  stack: [[1, 1.0, 2.0, 3], [2.0, 3.0, 5.0], 4]
current >> ‚  ||  stack: [[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]
current >> ζ  ||  stack: [[[1, 1.0, 2.0, 3], [0.5, 0.75, 1.25]]]
current >> ˜  ||  stack: [[[1, 0.5], [1.0, 0.75], [2.0, 1.25], [3, ' ']]]
current >> ʒ  ||  stack: [[1, 0.5, 1.0, 0.75, 2.0, 1.25, 3, ' ']]
Filter: .ï
Full program: .ï
current >> .  ||  stack: [1]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.5]
stack > [0]
Full program: .ï
current >> .  ||  stack: [1.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [0.75]
stack > [0]
Full program: .ï
current >> .  ||  stack: [2.0]
stack > [1]
Full program: .ï
current >> .  ||  stack: [1.25]
stack > [0]
Full program: .ï
current >> .  ||  stack: [3]
stack > [1]
Full program: .ï
current >> .  ||  stack: [' ']
invalid literal for int() with base 10: ' '
stack > []
current >> D  ||  stack: [[1, 1.0, 2.0, 3]]
current >> X  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> Q  ||  stack: [[1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3], [1, 1.0, 2.0, 3]]
current >> #  ||  stack: [[1, 1.0, 2.0, 3], 1]
[1, 1.0, 2.0, 3]
stack > [[1, 1.0, 2.0, 3]]

Experimente online com depuração!

Mathematica, 72 64 59 58 bytes

(d=2;#//.x_:>Riffle[x,(x+{##2,}&@@x)/d++]~Cases~_Integer)&

Experimente online!

Como funciona

Tomamos a entrada como uma lista {p,q}. A etapa de iteração é reformulada como:

1. Insira (a+b)/dentre cada dois elementos ae b: (x+{##2,}&@@x)calcula a sequência de a+b's, com um a+Nullno final. Dividimos por de Riffleinsere cada um (a+b)/dentre ae b. Incremento d.
2. Escolha os Integerelementos da lista resultante. (Isso também se livra do Nullintroduzido por {##2,}.)

Isso é repetido até que o resultado não seja alterado (o que só pode acontecer porque removemos todos os novos elementos, porque nenhum deles era inteiro).

-8 bytes graças a @MartinEnder de usar em //.vez de FixedPoint(e de receber entrada como uma lista).

-6 a mais porque ListConvolvena verdade não é tão bom

Ruby , 80 bytes

->a,d=2{*b=a[0];a.each_cons 2{|x,y|z=x+y;b+=z%d>0?[y]:[z/d,y]};b==a ?a:f[b,d+1]}

Experimente online!

Função recursiva que recebe fentrada como matriz [p, q].

Haskell, 85 81 bytes

(a:b:c)#d=a:[div(a+b)d|mod(a+b)d<1]++(b:c)#d
l#d=l
l%d|l==l#d=l|e<-d+1=l#d%e
(%2)

Experimente online!

A entrada é tomada como uma lista, por exemplo [1,2].

Edit: -4 bytes graças a @Laikoni.

Python 2 , 112 110 108 105 103 bytes

^{-2 bytes graças a Jonathan Frech
-5 bytes graças a Erik, o Outgolfer}

y=input()
x=d=1
while x!=y:
 d+=1;x=y;y=x[:1]
 for a,b in zip(x,x[1:]):c=a+b;y+=[c/d,b][c%d>0:]
print x

Experimente online!

Python 2 , 98 bytes

f=lambda A,B=0,d=2:A*(A==B)or f(sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1]),A,d+1)

Invocar como f([p,q]). Experimente online!

Jonathan Allan salvou 12 bytes. Obrigado ~!

Explicação

fé uma função recursiva: f(A, B, d)avalia para f(next_A, A, d+1), a menos que A == B, nesse caso, ele retorna A. (Isso é tratado por A*(A==B)or …: se A ≠ B, A*(A==B)é a lista vazia, que é falso-y, a …parte é avaliada; se A = B então A*(A==B)é A, o que não está vazio e, portanto, é verdade, e é retornado.)

next_A é calculado como:

sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])

Isso é melhor explicado pelo exemplo. Quando por exemplo d = 5 e A = [1, 4, 11, 8, 21]:

  sum([[(l+r)/d,r][(l+r)%d>0:]for l,r in zip(A,A[1:])],A[:1])
= sum([[(1+4)/d, 4], [(4+11)/d, 11], [8], [21]], [1])
= [1] + [1, 4] + [3, 11] + [8] + [21]
= [1, 1, 4, 3, 11, 8, 21]

Python 2 , 111 bytes

A=input()
m=d=1
while m:
 m=o=0;d+=1
 while A[o+1:]:
	o+=1;s=A[o-1]+A[o]
	if s%d<1:A[o:o]=s/d,;m=1;o+=1
print A

Experimente online!

-8 graças a Rod .
-2 graças a Lynn .

Casca , 22 bytes

→UG`λf£NΣẊṠeo/⁰+:.)⁰tN

Pega uma lista de 2 elementos, retorna uma lista de números inteiros e flutuantes. Experimente online!

Explicação

→UG`λf£NΣẊṠeo/⁰+:.)⁰tN  Input is a list L.
  G                 tN  Cumulative reduce over the list [2,3,4..
                   ⁰    with initial value L
   `λ             )     using flipped version of this function:
     f£NΣẊṠeo/⁰+:.       Arguments are a list, say K=[1,3,3], and a number, say d=4.
                :.       Prepend 0.5: [0.5,1,2,3]
         Ẋ               For each adjacent pair,
               +         take their sum,
            o/⁰          divide by d,
          Ṡe             and pair it with the right number in the pair: [[0.375,1],[1.0,3],[1.5,3]]
        Σ                Concatenate: [0.375,1,1.0,3,1.5,3]
     f£N                 Remove non-integers: [1,1.0,3,3]
                        Now we have an infinite list of L threaded through 2,3,4.. using the expansion operation.
 U                      Take longest prefix of unique elements,
→                       then last element of that.

Perl 5 , 92 + 1 ( -a) = 93 bytes

do{$c=0;@n=shift@F;$.++;push@n,($t=$_+$n[-1])%$.?$_:($c=$t/$.,$_)for@F;@F=@n}while$c;say"@F"

Experimente online!

Retina , 111 bytes

\d+
$*1;
^
11@
{+`(1+); (1+);
$1; $1$2 $2;
(?<=(?=(1+)).*) (\1)+ 
 a$#2$*1; 
 1+ 
 
.*a
1$&
)`a

1+@

1+
$.&
;

Experimente online!

Toma a entrada como números separados por espaço. Ingenuamente segue o algoritmo dado, com a única técnica notável sendo o uso de um símbolo de marcador a, para observar quando algum dos números foi mantido. Isso é usado para trabalhar com os recursos de loop um tanto limitados do Retina, que permitem apenas fazer loop até que um conjunto de estágios não faça nenhuma alteração geral na entrada desses estágios.

Explicação:

Isso usará o mesmo exemplo da pergunta.

\d+
$*1;

Como alteramos a matriz de entrada de números em uma matriz unírica separada por ponto e vírgula, teríamos:

1; 111111111111111111111;

^
11@

Coloque dnosso código no começo, fornecendo-nos:

11@1; 111111111111111111111;

{+`(1+); (1+);
$1; $1$2 $2;

Isso é um pouco mais complicado. {inicia um grupo de estágios que serão executados até atingirem um ponto fixo. Em seguida, +indica que esse estágio em si deve ser executado até um ponto fixo. Esse estágio adiciona cada par de números adjacentes, mas os insere sem o ponto e vírgula adicional. Agora teríamos:

11@1; 1111111111111111111111 111111111111111111111;

(?<=(?=(1+)).*) (\1)+ 
 a$#2$*1;

O outro estágio complicado, esse acumula nosso divisor no primeiro grupo de capturas e substitui qualquer número em nossa lista sem um ponto e vírgula à direita com esse número dividido por d. Também adicionamos um líder aa esses números, para indicar que algo foi mantido, juntamente com o ;para indicar que ele deve fazer parte permanente da matriz. Agora teríamos:

11@1; a11111111111; 111111111111111111111;

 1+ 

Isso exclui números que não eram divisíveis dnem na matriz antes desta rodada. Isso não altera o nosso exemplo.

.*a
1&$

Isso corresponde com avidez desde o início da string até a última letra ada entrada. Isso significa que pode haver no máximo uma partida. Se fizermos alterações, adicionamos uma a d, caso contrário, deixamos a mesma para que possamos sair do loop.

111@1; a11111111111; 111111111111111111111;

)`a

O )fechamento do loop é iniciado por {(não questione!); Caso contrário, esse estágio apenas remove os marcadores que colocamos anteriormente. Como este é o fim do loop, repetiríamos as etapas acima muitas vezes, no entanto, continuarei como se tivesse esquecido o loop, pois isso torna o exemplo mais contínuo.

111@1; 11111111111; 111111111111111111111;

1+@

Esta etapa remove de nossa saída:

1; 11111111111; 111111111111111111111;

1+
$.&

Esta etapa substitui os números unários por números decimais:

1; 11; 21;

;

A etapa final elimina os pontos e vírgulas:

1 11 21

Obviamente, pular o loop nos faz ter um resultado incorreto aqui, mas espero que não seja muito confuso.

JavaScript (ES6), 89 87 82 bytes

Obrigado @Arnauld por -2 bytes e por ajudar a economizar mais 5 bytes.

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

Toma entrada como uma matriz: f([p,q]).

Casos de teste

f=(a,d=2,r)=>a.map(v=>b.push(v,...(v+=a[++i])%d<1?[r=v/d]:[]),b=i=[])|r?f(b,d+1):a

;[[1,1],[1,2],[1,3],[2,6],[3,13],[9,9],[60,68],[144,336],[12096,24192]]
.forEach(test=>O.innerText+=JSON.stringify(test)+" -> "+JSON.stringify(f(test))+"\n")

<pre id=O></pre>

Röda , 90 bytes

f a,d=2{A=[a()|slide 2|[_,(_1+_)/d]if[(_1+_2)%d=0]else[_1]]+a[-1]f A,d=d+1 if[a!=A]else A}

Experimente online!

Java 8, 180 bytes

import java.util.*;p->q->{List<Integer>r=new Stack();r.add(p);r.add(q);for(int d=1,f=d,i;f==d++;)for(i=1;i<r.size();i++)if((q=r.get(i)+r.get(i-1))%d<1)r.add(i++,q/(f=d));return r;}

Explicação:

Experimente aqui.

import java.util.*;           // Required import for List and Stack

p->q->{                       // Method with two integer parameters and List return-type
  List<Integer>r=new Stack(); //  Result-list
  r.add(p);r.add(q);          //  Add the two input-integers to the List
  for(int d=1,                //  Divisible integer (starting at 1)
          f=d,                //  Temp integer (starting at `d` / also 1)
          i;                  //  Index-integer
      f==d++;)                //  Loop (1) as long as `f` and `d` are equal
                              //  (and raise `d` by 1 so it starts at 2 inside the loop)
    for(i=1;                  //   Reset index-integer to 1
        i<r.size();i++)       //   Inner loop (2) over the List
      if((q=r.get(i)+r.get(i-1)) 
                              //    If the current + previous items (stored in `q`)
         %d<1)                //    are divisible by `d`:
        r.add(i++,q/(f=d));   //     Insert `q` divided by `d` to the List at index `i`
                              //     (and raise `i` by 1 and set `f` to `d` in the process)
                              //   End of inner loop (2) (implicit / single-line body)
                              //  End of loop (1) (implicit / single-line body)
  return r;                   //  Return the result-List
}                             // End of method

C #, 280 bytes

using System.Linq;class A{static void Main(string[] p){var l=new System.Collections.Generic.List<int>(p.Select(int.Parse));int r,d=2,c;do{c=0;for(int i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);l.ForEach(v=>System.Console.Write((v+" ")));}}

Primeira tentativa de código de golfe, que é todo o programa. Teste-o

Tentativa 2, 159 bytes

Retirando o andaime, uma vez que a tarefa é fornecer uma função que pode receber um par de números (uma matriz funciona) e retorna uma matriz. Dado que um Func <int [], int []> F pode ser usado para satisfazer os requisitos, basta definir F :

F=v=>{var l=new List<int>(v);int i,r,d=2,c;do{c=0;for(i=1;i<l.Count;++i){if((r=l[i-1]+l[i])%d==0){l.Insert(i++,r/d);++c;}}++d;}while(c>0);return l.ToArray();};

Teste o programa completo aqui

Isso pode ser menor se uma lista genérica for considerada uma saída válida (solte .ToArray () para salvar 10 bytes).

Se a entrada também puder ser modificada, passar uma Lista <int> em vez de uma matriz remove a necessidade de inicializar a saída (sai em 126 bytes).

Levando isso um passo adiante, realmente não precisa haver um valor de retorno nesse caso. O uso de uma ação remove os 9 bytes usados ​​pela instrução de retorno.

Geléia , 19 bytes

®‘©‘÷@+2\⁸żFfṀR$µÐL

Experimente online!