Последовательности

Вам даны четыре числовые последовательности, пронумерованные до 1конца 4.

1. OEIS Местоположение 0's, когда натуральные числа перечислены в двоичном виде. Вот пример того, как рассчитать последовательность:

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

   Начало последовательности выглядит так: 0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...

2. OEIS Эта последовательность включает в себя первое натуральное число, пропускает следующие два, затем включает следующие три, затем пропускает следующие четыре и продолжает.

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

3. OEIS Положительные целые числа, где как число 0's, так и число 1' s в двоичном представлении числа являются степенями 2.

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

4. OEIS Q последовательность Хофштадтера .

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

   Мало что строго доказано об этой последовательности, но существует много эмпирических результатов. Один из них особенно важен, и вы можете предположить, что он действителен для всей серии:

   В этой статье отмечается, что элементы ряда могут быть сгруппированы в поколения. Если мы нумеруем их, начиная с 1, то k- е поколение содержит ровно 2 ^k элементов. Соответствующим свойством является то, что все числа в поколении k получаются суммированием двух чисел из поколений k-1. и / или k-2 , но никогда из предыдущих поколений. Вы можете использовать это (и только это) наблюдение, чтобы установить нижнюю границу для оставшихся элементов в последовательности.

Вызов

Ваша задача - напечатать первые xчисла на пересечении заданных входных последовательностей.

Ввод: два числа, разделенные пробелом STDIN. Первое число представляет собой целое число от 1до 15включительно, где каждый бит соответствует последовательности. Самый младший бит соответствует последовательности 1, а самый старший - последовательности 4. Второе количество цифр,x , на которое нужно вывести STDIN.

Выход: первые xчисла, которые пересекаются с заданными входными последовательностями. Распечатать цифры наSTDOUT с любым свободным пробелом или пунктуацией в качестве разделителя (пробелы, символы табуляции, новые строки, запятые, двоеточия, точки и т. Д.).

Примеры

1. Напечатайте первые 3числа в каждой последовательности.

Входные данные: 15 3

Вывод: 10,23,40

2. Напечатайте первые 12числа в порядковом номере1 и 4.

Входные данные: 9 12

Вывод: 3,8,10,14,19,20,21,23,24,31,37,40

3. Распечатайте первый10 числа в последовательности 2.

Входные данные: 2 10

Вывод: 0,3,4,5,10,11,12,13,14,21

4. Напечатайте первые 6числа в последовательностях 3и4 .

Входные данные: 12 6

Вывод: 2,4,5,6,9,10

подробности

• Вы можете распечатать вывод на ходу или все сразу в конце.

Огромное спасибо всем, кто помог с этим в чате! Этот вопрос получил большую выгоду от того, чтобы быть в песочнице .

Хаскелл, 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

Работает достаточно хорошо. Вот пара примеров 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 символов

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

Это простое решение: используйте генераторы для определения каждой из бесконечных последовательностей, и, пока пересечение недостаточно велико, добавьте шаг к каждой последовательности.

Чтобы учесть немонотонно увеличивающуюся последовательность Хофштадтера: на каждом шаге я генерирую вдвое больше для этой последовательности, например, 1, затем 2, 4, 8, 16, 32 и т. Д. Я думаю, что удовлетворяет границе, указанной в вопросе и это все еще достаточно быстро для всех тестовых случаев, представленных там.

С # 1923

Это, вероятно, не самая короткая программа, но я нашел задачу интересной, так что вот мое решение.

Выполнение всех 4 с 35 номерами (15 35) занимает около 5 секунд.

Вы можете проверить это здесь , но обратите внимание, что если вы хотите OEIS4, количество цифр, которое вы хотите, должно быть маленьким, или netfiddle исчерпает память.

Golfed

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

Удобочитаемый

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

объяснение

Это использует ленивую оценку, что делает ее претенциозно быстрой, я верю. Также мне было лениво делать какие-либо «битлогические», используя метод Convert.ToString (число, 2). Это превращает любое число в его представление binray в виде строки.

Мне пришлось написать свой собственный метод для пересечения последовательностей, так как пересечение Linq-Method вычисляет пересечение полной последовательности, и это было буквально невозможно.