Sekwencje

Otrzymasz cztery sekwencje liczb, ponumerowane 1przez 4.

1. OEIS Lokalizacja 0, kiedy liczby naturalne są wymienione w postaci binarnej. Oto przykład obliczania sekwencji:

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

   Początek sekwencji wygląda następująco: 0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...

2. OEIS Sekwencja ta obejmuje pierwszą liczbę naturalną, pomija następne dwie, następnie obejmuje kolejne trzy, następnie pomija następne cztery i trwa dalej.

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

3. Liczby całkowite dodatnie OEIS, w których zarówno liczba 0, jak i liczba 1w binarnej reprezentacji liczby są potęgami 2.

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

4. OEIS Hofstadter P sekwencji .

   a (1) = a (2) = 1;
   a (n) = a (na (n-1)) + a (na (n-2)) dla 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, ...
   

   Niewiele udowodniono rygorystycznie na temat tej sekwencji, ale istnieje wiele wyników empirycznych. Jedna jest szczególnie ważna i możesz założyć, że jest ważna dla całej serii:

   W artykule zaobserwowano, że elementy serii można pogrupować w pokolenia. Jeśli policzymy je od 1, wówczas k- ta generacja zawiera dokładnie 2 ^k elementów. Właściwą właściwością jest to, że wszystkie liczby w generacji k są uzyskiwane przez zsumowanie dwóch liczb z generacji k-1 i / lub k-2 , ale nigdy z poprzednich generacji. Możesz użyć tej (i tylko tej) obserwacji, aby wyznaczyć dolną granicę pozostałych elementów w sekwencji.

Wyzwanie

Twoim wyzwaniem jest wydrukowanie pierwszych xliczb na przecięciu podanych sekwencji wejściowych.

Wejście: dwie liczby oddzielone spacją na STDIN. Pierwsza liczba jest liczbą całkowitą od 1do 15włącznie, gdzie każdy bit odpowiada sekwencji. Najniższy bit odpowiada sekwencji 1, a najwyższy odpowiada sekwencji 4. Drugi to ilość liczb x, na których ma zostać wyprowadzone STDIN.

Wyjście: pierwsze xliczby, które przecinają dane sekwencje wejściowe. Wydrukuj liczby STDOUTz dowolną wyraźną białą spacją lub interpunkcją jako separatorem (spacje, tabulatory, znaki nowej linii, przecinki, dwukropki, kropki itp.).

Przykłady

1. Wydrukuj pierwsze 3liczby w każdej sekwencji.

Wejście: 15 3

Wynik: 10,23,40

2. Wydrukuj pierwsze 12liczby w numerze sekwencji 1i 4.

Wejście: 9 12

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

3. Wydrukuj pierwsze 10cyfry po kolei 2.

Wejście: 2 10

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

4. Wydrukuj pierwsze 6liczby w sekwencjach 3i 4.

Wejście: 12 6

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

Detale

• Możesz wydrukować dane wyjściowe na bieżąco lub na raz na końcu.

Ogromne podziękowania dla wszystkich, którzy pomogli z tym na czacie! To pytanie bardzo skorzystało z przebywania w piaskownicy .

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

Działa dość dobrze. Oto kilka przykładów 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 znaków

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])

Jest to proste rozwiązanie: użyj generatorów, aby zdefiniować każdą nieskończoną sekwencję, i dopóki przecięcie nie jest wystarczająco duże, dodaj krok do każdej sekwencji.

Aby uwzględnić nie monotonicznie rosnącą sekwencję Hofstadtera: na każdym kroku generuję dwa razy więcej dla tej sekwencji, np. 1, a następnie 2, 4, 8, 16, 32 itd. Myślę, że spełnia ona granicę podaną w pytaniu i nadal jest wystarczająco szybki dla wszystkich prezentowanych tam przypadków testowych.

C #, 1923

Prawdopodobnie nie będzie to najkrótszy program, ale wyzwanie było dla mnie interesujące, więc oto moje rozwiązanie.

Uruchamianie wszystkich 4 z 35 liczbami (15 35) zajmuje około 5 sekund.

Możesz to przetestować tutaj , ale pamiętaj, że jeśli chcesz OEIS4, liczba cyfr, które chcesz, musi być mała lub w netfiddle zabraknie pamięci.

Grał w golfa

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;}}

Czytelny

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;
    }
}

Wyjaśnienie

Wykorzystuje to leniwą ocenę bigtime, która sprawia, że ​​jest ona bardzo szybka. Byłem też leniwy, robiąc jakąkolwiek „bitlogikę”, używając metody Convert.ToString (liczba, 2). To zamienia dowolną liczbę w jej reprezentację binray jako ciąg.

Musiałem napisać własną metodę przecięcia sekwencji, ponieważ metoda Linq oblicza przecięcie pełnej sekwencji, co było dosłownie niemożliwe.