9
\$\begingroup\$

Sequences

You are given four number sequences, numbered 1 through 4.

  1. OEIS The location of 0's when the natural numbers are listed in binary. Here's an example of how to calculate the sequence:

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

    The start of the sequence goes like this: 0, 3, 7, 8, 10, 14, 19, 20, 21, 23, 24, 27, 29, 31, 36, 37, 40, 45, 51, ...


  1. OEIS This sequence includes the first natural number, skips the next two, then includes the next three, then skips the next four, and continues.

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

  1. OEIS Positive integers where both the number of 0's and the number of 1's in the binary representation of the number are powers of 2.

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

  1. OEIS The Hofstadter Q sequence.

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

    Little is proven rigorously about this sequence, but many empirical results exist. One is particularly important, and you may assume it's valid for the entire series:

    This paper observed that the elements of the series can be grouped into generations. If we number them starting at 1, then the kth generation contains exactly 2k elements. The relevant property is that all numbers in generation k are obtained by summing two numbers from generations k-1 and/or k-2, but never from earlier generations. You may use this (and only this) observation to put a lower bound on the remaining elements in the sequence.


Challenge

Your challenge is to print the first x numbers in the intersection of the given input sequences.

Input: Two numbers separated by a space on STDIN. The first number is an integer from 1 to 15 inclusive where each bit corresponds to a sequence. The lowest bit corresponds to sequence 1, and the highest corresponds to sequence 4. The second is amount of numbers, x, to output on STDIN.

Output: The first x numbers that intersect with the given input sequences. Print the numbers on STDOUT with any clear whitespace or punctuation as a delimiter (spaces, tabs, newlines, commas, colons, periods, etc).


Examples

1. Print the first 3 numbers that are in every sequence.

Input: 15 3

Output: 10,23,40


2. Print the first 12 numbers in sequences number 1 and 4.

Input: 9 12

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


3. Print the first 10 numbers in sequence 2.

Input: 2 10

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


4. Print the first 6 numbers in sequences 3 and 4.

Input: 12 6

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


Details

  • You may print the output as you go or all at once at the end.

Huge thanks to everyone who helped out with this in chat! This question benefited greatly from being in the sandbox.

\$\endgroup\$
  • \$\begingroup\$ @chilemagic: Actually how do you define "first X numbers" in an intersection? If you take both sequences in the 12 5 example up to the same index, then 10 does indeed come before 9 in the intersection... like, how would you, while going through the sequences, decide whether to skip the 9 in #3 as a possible intersection? Like if #3 had 7 in it then you would be required to skip over it since that doesn't appear in #4 \$\endgroup\$ – Claudiu Nov 17 '14 at 20:15
  • \$\begingroup\$ @Claudiu Your outputted numbers should always be increasing, and each number would only appear once in your output. \$\endgroup\$ – chilemagic Nov 17 '14 at 20:21
  • \$\begingroup\$ Is there a maximum limit to x? \$\endgroup\$ – Ypnypn Nov 18 '14 at 1:18
  • \$\begingroup\$ @ypnypn don't hard code a limit, but if your algorithm is very slow or won't finish for very large inputs that's ok. This is code golf so you can be inefficient to save bytes. \$\endgroup\$ – chilemagic Nov 18 '14 at 2:33
2
\$\begingroup\$

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

It performs reasonably well. Here are a couple of OP's examples:

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]
\$\endgroup\$
4
\$\begingroup\$

Python 3, 590 639 characters

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

This is the straight-forward solution: use generators to define each of the infinite sequences, and so long as the intersection isn't large enough, add a step to each sequence.

To account for the non-monotonically-increasing Hofstadter sequence: at each step I generate twice as many for that sequence, e.g. 1, then 2, 4, 8, 16, 32, etc. I think that satisfies the bound stated in the question, and it's still fast enough for all the test cases presented there.

\$\endgroup\$
  • 2
    \$\begingroup\$ Golfs: from itertools import count as C -> from itertools import* C=count, def s(i):return D(i)==1 -> s=lambda i:D(i)==1 (I don't even think this function makes it shorter...), "{0:04b}".format(int(L)))if U>'0' -> "{0:04b}".format(int(L)))if'0'<U \$\endgroup\$ – Justin Nov 19 '14 at 5:51
3
\$\begingroup\$

C#, 1923

It probably wont be the shortest program but i found the challenge interesting, so here is my solution.

Running all 4 with 35 Numbers (15 35) takes about 5 seconds.

You can test it here, but note that if you want OEIS4 the amount of digits you want needs to be small or netfiddle runs out of memory.

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

Readable

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

Explanation

This makes use of lazy evaluation bigtime which makes it prett fast i bellieve. Also i was lazy doing any "bitlogic" by using the frameworks Convert.ToString(number, 2) method. This turns any number into its binray representation as a string.

I had to write my own method to intersect the seuqences as the Linq-Method intersect computes the intersection of the full sequence, and that was literally impossible.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.