Urutan

Anda diberi empat urutan nomor, dinomori 1melalui 4.

1. OEIS Lokasi 0ketika bilangan asli terdaftar dalam biner. Berikut ini contoh cara menghitung urutan:

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

   Awal urutannya seperti ini: 0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...

2. OEIS Urutan ini termasuk bilangan asli pertama, lewati dua berikutnya, kemudian sertakan tiga berikutnya, kemudian lewati empat berikutnya, dan lanjutkan.

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

3. OEIS Bilangan bulat positif di mana baik jumlah 0's dan jumlah 1' s dalam representasi angka biner adalah kekuatan 2.

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

4. Oei The Hofstadter Q urut .

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

   Sedikit yang dibuktikan secara ketat tentang urutan ini, tetapi banyak hasil empiris ada. Satu sangat penting, dan Anda dapat menganggap itu valid untuk seluruh seri:

   Makalah ini mengamati bahwa unsur-unsur dari seri dapat dikelompokkan menjadi beberapa generasi. Jika kita beri nomor mulai dari 1, maka generasi k mengandung tepat 2 elemen ^k . Properti yang relevan adalah bahwa semua angka dalam generasi k diperoleh dengan menjumlahkan dua angka dari generasi k-1 dan / atau k-2 , tetapi tidak pernah dari generasi sebelumnya. Anda dapat menggunakan pengamatan ini (dan hanya ini) untuk menempatkan batas bawah pada elemen yang tersisa dalam urutan.

Tantangan

Tantangan Anda adalah mencetak xangka pertama di persimpangan urutan input yang diberikan.

Input: Dua angka dipisahkan oleh spasi STDIN. Angka pertama adalah bilangan bulat dari 1hingga 15inklusif di mana setiap bit sesuai dengan urutan. Bit terendah sesuai dengan urutan 1, dan tertinggi berhubungan dengan urutan 4. Yang kedua adalah jumlah angka x,, untuk output aktif STDIN.

Output: Angka pertama xyang bersinggungan dengan urutan input yang diberikan. Cetak angka-angka STDOUTdengan spasi kosong atau tanda baca yang jelas sebagai pembatas (spasi, tab, baris baru, koma, titik dua, titik, dll).

Contohnya

1. Cetak 3angka pertama yang ada di setiap urutan.

Memasukkan: 15 3

Keluaran: 10,23,40

2. Cetak 12angka pertama dalam urutan nomor 1dan 4.

Memasukkan: 9 12

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

3. Cetak 10angka pertama secara berurutan 2.

Memasukkan: 2 10

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

4. Cetak 6angka pertama secara berurutan 3dan 4.

Memasukkan: 12 6

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

Detail

• Anda dapat mencetak output saat Anda pergi atau sekaligus di akhir.

Terima kasih banyak untuk semua orang yang membantu dengan ini dalam obrolan! Pertanyaan ini sangat diuntungkan dari berada di kotak pasir .

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

Berkinerja cukup baik. Berikut adalah beberapa contoh 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 karakter

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

Ini adalah solusi lurus ke depan: gunakan generator untuk menentukan masing-masing urutan tak terhingga, dan selama persimpangan tidak cukup besar, tambahkan langkah ke setiap urutan.

Untuk menjelaskan urutan Hofstadter yang tidak meningkat secara monoton: pada setiap langkah saya menghasilkan dua kali lebih banyak untuk urutan itu, misalnya 1, kemudian 2, 4, 8, 16, 32, dll. Saya pikir itu memenuhi batas yang dinyatakan dalam pertanyaan , dan itu masih cukup cepat untuk semua kasus uji yang disajikan di sana.

C #, 1923

Mungkin tidak akan menjadi program terpendek tetapi saya menemukan tantangan yang menarik, jadi inilah solusi saya.

Menjalankan semua 4 dengan 35 Angka (15 35) membutuhkan waktu sekitar 5 detik.

Anda dapat mengujinya di sini , tetapi perhatikan bahwa jika Anda ingin OEIS4 jumlah digit yang Anda inginkan harus kecil atau netfiddle kehabisan memori.

Golf

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

Dapat dibaca

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

Penjelasan

Ini menggunakan evaluasi malas malas yang membuatnya cepat cepat saya percaya. Juga saya malas melakukan "bitlogic" apa pun dengan menggunakan kerangka kerja Convert.ToString (angka, 2) metode. Ini mengubah angka apa pun menjadi representasi binray sebagai string.

Saya harus menulis metode saya sendiri untuk memotong seuqences karena metode Linq memotong persimpangan dari urutan penuh, dan itu benar-benar mustahil.