Sequências

Está dado quatro sequências de números, numerados 1através 4.

1. OEIS A localização de 0quando os números naturais estão listados em binário. Aqui está um exemplo de como calcular a sequência:

    0,1,10,11,100,101,110,111
    ^    ^     ^^  ^    ^
    0    3     78  10   14
   

   O início da sequência é assim: 0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...

2. OEIS Essa sequência inclui o primeiro número natural, pula os próximos dois, depois os três seguintes, depois os quatro seguintes e continua.

    0, 3, 4, 5, 10, 11, 12, 13, 14, 21, 22, 23, 24, 25, 26, 27, 36, ...
   

3. OEIS Inteiros positivos em que o número de 0's e o número de 1' s na representação binária do número são potências de 2.

   2, 4, 5, 6, 9, 10, 12, 16, 23, 27, 29, 30, 33, 34, 36, 39,
   

4. OEIS A sequência Q de Hofstadter .

   a (1) = a (2) = 1;
   a (n) = a (na (n-1)) + a (na (n-2)) para n> 2.

   1, 1, 2, 3, 3, 4, 5, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, 12, 12, 12, 16, 14, ...
   

   Pouco é provado rigorosamente sobre essa sequência, mas existem muitos resultados empíricos. Um é particularmente importante e você pode assumir que é válido para toda a série:

   Este artigo observou que os elementos da série podem ser agrupados em gerações. Se os numerarmos começando em 1, a k- ésima geração conterá exatamente 2 ^k elementos. A propriedade relevante é que todos os números da geração k são obtidos somando dois números das gerações k-1 e / ou k-2 , mas nunca das gerações anteriores. Você pode usar esta (e somente essa) observação para colocar um limite inferior nos elementos restantes na sequência.

Desafio

Seu desafio é imprimir os primeiros xnúmeros na interseção das seqüências de entrada fornecidas.

Entrada: Dois números separados por um espaço ativado STDIN. O primeiro número é um número inteiro de 1para 15inclusivo, em que cada bit corresponde a uma sequência. O bit mais baixo corresponde à sequência 1e o mais alto corresponde à sequência 4. O segundo é a quantidade de números x,, para saída STDIN.

Saída: Os primeiros xnúmeros que se cruzam com as seqüências de entrada fornecidas. Imprima os números STDOUTcom qualquer espaço em branco ou pontuação como delimitador (espaços, tabulações, novas linhas, vírgulas, dois pontos, pontos etc.).

Exemplos

1. Imprima os primeiros 3números que estão em todas as seqüências.

Entrada: 15 3

Resultado: 10,23,40

2. Imprima os primeiros 12números no número de seqüências 1e 4.

Entrada: 9 12

Resultado: 3,8,10,14,19,20,21,23,24,31,37,40

3. Imprima os primeiros 10números em sequência 2.

Entrada: 2 10

Resultado: 0,3,4,5,10,11,12,13,14,21

4. Imprima os primeiros 6números nas seqüências 3e 4.

Entrada: 12 6

Resultado: 2,4,5,6,9,10

Detalhes

• Você pode imprimir a saída à medida que avança ou ao mesmo tempo no final.

Muito obrigado a todos que ajudaram com isso no chat! Esta questão se beneficiou muito de estar na caixa de areia .

Haskell, 495 442 402

import Data.List
d=1:1:1%2
f=filter
p 0="0"
p 1="1"
p n=p(div n 2)++p(mod n 2)
l=length
u z[a,b]=sort.head.dropWhile((<b).l)$m(nub.foldl1 intersect.y(tail.p$31-a).(`m`[d,f(v.group.sort.p)[1..],z#1,y(z>>=p)z]).take)z
w=(=='0')
v[a]=1>2
v x=all(all w.tail.p.l)x
y x=m snd.f(w.fst).zip x
x#n=n`take`x++drop(n+n+1)x#(n+2)
n%m=d!!(m-d!!n)+d!!(m-d!!(n-1)):m%(m+1)
main=interact$show.u[0..].m read.words
m=map

Ele executa razoavelmente bem. Aqui estão alguns exemplos de OP:

Flonk@home:~>echo 15 10 | codegolf
[10,23,40,57,58,139,147,149,212,228]
Flonk@home:~>echo 9 12 | codegolf
[3,8,10,14,19,20,21,23,24,31,37,40]
Flonk@home:~>echo 2 10 | codegolf
[0,3,4,5,10,11,12,13,14,21]
Flonk@home:~>echo 12 6 | codegolf
[2,4,5,6,9,10]

Python 3, 590 639 caracteres

from itertools import count as C
D=lambda n,t='1':bin(n).count(t)
Y=range
def O():
 for n in C(0):yield from bin(n)[2:]
def B():
 s=i=0
 while 1:
  i+=s
  for j in Y(i,i+s+1):yield j
  s+=2;i+=s-1
def s(i):return D(i)==1
def F():
 a=[1]*3
 for n in C(3):a+=[a[n-a[n-1]]+a[n-a[n-2]]];yield a[-1]
L,R=input().split()
J=[x for x,U in zip([F(),(n for n in C(0)if s(D(n,'0')-1)and s(D(n))),B(),(i for i,c in enumerate(O())if'1'>c)],"{0:04b}".format(int(L)))if U>'0']
X=[set()for _ in J]
M=[]
Z=int(R);K=1
while len(M)<Z:
 for x,j in zip(X,J):x.add(next(j))
 for _ in Y(K):X[0].add(next(J[0]));K+=1
 M=X[0]
 for x in X:M=M&x
print(sorted(M)[:Z])

Esta é a solução direta: use geradores para definir cada uma das infinitas seqüências e, desde que a interseção não seja grande o suficiente, adicione uma etapa a cada sequência.

Para dar conta da sequência de Hofstadter que não aumenta monotonicamente: em cada etapa, gero o dobro dessa sequência, por exemplo, 1, depois 2, 4, 8, 16, 32 etc. Acho que satisfaz o limite indicado na pergunta , e ainda é rápido o suficiente para todos os casos de teste apresentados lá.

C #, 1923

Provavelmente não será o programa mais curto, mas achei o desafio interessante, então aqui está a minha solução.

A execução dos 4 com 35 números (15 35) leva cerca de 5 segundos.

Você pode testá-lo aqui , mas observe que, se desejar o OEIS4, a quantidade de dígitos que você deseja precisará ser pequena ou o netfiddle ficará sem memória.

Golfe

using System;using System.Collections;using System.Collections.Generic;using System.Linq;class p{public static void Main(string[] args){int b=0;IEnumerable<int>a=null;foreach(char c in Convert.ToString(int.Parse(args[0]),2).Reverse()){++b;if(c=='0')continue;switch(b){case 1: a=d(a,e());break;case 2: a=d(a,f());break;case 3: a=d(a,g());break;case 4: a=d(a,h(),true);break;}}if(a==null)return;bool j=true;foreach(int i in a.Take(int.Parse(args[1]))){if(j)j=false;else Console.Write(",");Console.Write(i);}}static IEnumerable<int>d(IEnumerable<int>k,IEnumerable<int>l,bool m=false){if(k==null)foreach(int n in l)yield return n;int o=0;int p=1;foreach(int i in k){Dictionary<int,HashSet<int>>q=m ? new Dictionary<int,HashSet<int>>(): null;int s=0;foreach(int n in l){if(!m){if(i<n)break;}else{if(!q.ContainsKey(o))q.Add(o,new HashSet<int>());q[o].Add(n);if(q.Count==1){int r=q[o].OrderBy(gi =>gi).Take(2).Sum();if(i<r)break;}else{int r=q[o].Concat(q[o-1]).OrderBy(gi =>gi).Take(2).Sum();if(i<r)break;}if(++s==p){o++;p=(int)Math.Pow(2,o);}}if(i==n){yield return i;break;}}}}static IEnumerable<int>e(){int t=0;for(int i=0;i<int.MaxValue;i++)foreach(char c in Convert.ToString(i,2)){if(c=='0')yield return t;t++;}}static IEnumerable<int>f(){int t=1;int u=0;bool v=true;using(IEnumerator<int>w=Enumerable.Range(0,int.MaxValue).GetEnumerator()){while(w.MoveNext()){if(v){if(u==0)u=t+1;yield return w.Current;if(--t==0)v=false;}else{if(t==0)t=u+1;if(--u==0)v=true;}}}}static IEnumerable<int>g(){for(int i=0;i<int.MaxValue;i++){string s=Convert.ToString(i,2);if(x(s.Count(c =>c=='0'))&& x(s.Count(c =>c=='1')))yield return i;}}static bool x(int y){return(y != 0)&&((y &(y-1))==0);}static IEnumerable<int>h(){return Enumerable.Range(1,int.MaxValue).Select(z);}static Dictionary<int,int>_=new Dictionary<int,int>();static int z(int n){int a;if(!_.TryGetValue(n,out a)){if(n<3)a=1;else a=z(n-z(n-1))+z(n-z(n-2));_.Add(n,a);}return a;}}

Legível

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

class Programm
{
    public static void Main(string[] args)
    {
        int index = 0;

        IEnumerable<int> intersection = null;

        foreach (char c in Convert.ToString(int.Parse(args[0]), 2).Reverse())
        {
            ++index;
            if (c == '0')
                continue;

            switch (index)
            {
                case 1: intersection = _join(intersection, OEIS1()); break;
                case 2: intersection = _join(intersection, OEIS2()); break;
                case 3: intersection = _join(intersection, OEIS3()); break;
                case 4: intersection = _join(intersection, OEIS4(), true); break;

                default: throw new ArgumentException();
            }
        }
        if (intersection == null)
            return;

        bool first = true;
        foreach (int i in intersection.Take(int.Parse(args[1])))
        {
            if (first) first = false;
            else Console.Write(",");

            Console.Write(i);
        }

        Console.ReadKey();
    }

    private static IEnumerable<int> _join(IEnumerable<int> intersection, IEnumerable<int> newSequence, bool hof = false)
    {
        if (intersection == null)
            foreach (int n in newSequence) yield return n;



        int generation = 0;
        int generationMax = 1;
        foreach (int i in intersection)
        {
            Dictionary<int, HashSet<int>> generationCache = hof ? new Dictionary<int, HashSet<int>>() : null;
            int count = 0;
            foreach (int n in newSequence)
            {
                if (!hof)
                {
                    if (i < n)
                        break;
                }
                else
                {
                    if (!generationCache.ContainsKey(generation))
                        generationCache.Add(generation, new HashSet<int>());

                    generationCache[generation].Add(n);

                    if (generationCache.Count == 1)
                    {
                        int lowerBound = generationCache[generation].OrderBy(gi => gi).Take(2).Sum();
                        if (i < lowerBound)
                            break;
                    }
                    else
                    {
                        int lowerBound = generationCache[generation].Concat(generationCache[generation - 1]).OrderBy(gi => gi).Take(2).Sum();
                        if (i < lowerBound)
                            break;
                    }

                    if (++count == generationMax)
                    {
                        generation++;
                        generationMax = (int)Math.Pow(2, generation);
                    }
                }

                if (i == n)
                {
                    yield return i;
                    break;
                }
            }
        }
    }


    static IEnumerable<int> OEIS1()
    {
        int position = 0;
        for (int i = 0; i < int.MaxValue; i++)
            foreach (char c in Convert.ToString(i, 2))
            {
                if (c == '0')
                    yield return position;
                position++;
            }
    }

    static IEnumerable<int> OEIS2()
    {
        int take = 1;
        int skip = 0;
        bool doTake = true;
        using (IEnumerator<int> enumerator = Enumerable.Range(0, int.MaxValue).GetEnumerator())
        {
            while (enumerator.MoveNext())
            {
                if (doTake)
                {
                    if (skip == 0)
                        skip = take + 1;
                    yield return enumerator.Current;
                    if (--take == 0)
                        doTake = false;
                }
                else
                {
                    if (take == 0)
                        take = skip + 1;
                    if (--skip == 0)
                        doTake = true;
                }
            }
        }
    }

    static IEnumerable<int> OEIS3()
    {
        for (int i = 0; i < int.MaxValue; i++)
        {
            string s = Convert.ToString(i, 2);
            if (_isPowerOfTwo(s.Count(c => c == '0')) && _isPowerOfTwo(s.Count(c => c == '1')))
                yield return i;
        }
    }

    static bool _isPowerOfTwo(int number)
    {
        return (number != 0) && ((number & (number - 1)) == 0);
    }

    static IEnumerable<int> OEIS4()
    {
        return Enumerable.Range(1, int.MaxValue).Select(HofstadterQ);
    }

    static Dictionary<int, int> _hofstadterQCache = new Dictionary<int, int>();

    static int HofstadterQ(int n)
    {
        int result;
        if (!_hofstadterQCache.TryGetValue(n, out result))
        {
            if (n < 3)
                result = 1;
            else
                result = HofstadterQ(n - HofstadterQ(n - 1)) + HofstadterQ(n - HofstadterQ(n - 2));

            _hofstadterQCache.Add(n, result);
        }
        return result;
    }
}

Explicação

Isso faz uso de bigtime de avaliação preguiçosa, o que o torna muito rápido e acredito. Também estava com preguiça de fazer qualquer "bitlogic" usando o método Convert.ToString (number, 2) do framework. Isso transforma qualquer número em sua representação em binray como uma string.

Eu tive que escrever meu próprio método para interceptar as suas seqüências, pois o Linq-Method intersect calcula a interseção da sequência completa, e isso era literalmente impossível.