Problem 57492. Compute the Tetris sequence

Created by ChrisR

Solve Later

In the Tetris sequence, which starts with a 1, the next term is the smallest positive integer not already in the sequence that has no common 1-bits with the previous term. The first five terms are 1, 2, 4, 3, and 8 because the binary expansions 0001, 0010, 0100, 0011, and 1000 have no common ones among consecutive terms, and they are the smallest numbers with that property not already in the sequence. 
The discussion of this sequence involves odd gaps in the plot of the terms  (say) as a function of their position n in the sequence. A plot of  vs.  (below) makes one think of the Sierpinski gasket. Neil J.A. Sloane uses this resemblance to propose using “facial recognition” to connect sequences.  
Write a function to compute the nth term of the Tetris sequence.

Solve

Solution Stats

8 Solutions
4 Solvers

Last Solution submitted on Jan 06, 2023

Last 200 Solutions

Problem Comments

5 Comments

5 Comments

Show 2 older comments

Christian Schröder on 4 Jan 2023

This should really be titled "Compute the Tetris sequence, FAST", since the challenge (for me anyway) isn't computing it as much as doing it fast enough to not time-out on the Cody test suite. :P

ChrisR on 4 Jan 2023

Yes, that's part of the challenge. I was struggling to get beyond the list that is available at [redacted]. Pre-allocating an array, which bumps up the Cody score, helped to reduce the execution time. I also used a command that I've never tried before, though I've used related commands.

Christian Schröder on 5 Jan 2023

Yeah, pre-allocation was the first thing I did (and it helped cut execution time to about one quarter). After that I spent about two hours profiling the code and trying out different kinds of caching to avoid recomputing binary expansions, but they were all slower than the benchmark code in the end (dictionaries in particular). Same for using bitand, that made things (much) worse.

I may try again, but I'm not seeing any obvious avenues for refinement right now.

Side note: disallowing "if" (to combat cheating?) is a pretty tough restriction.

ChrisR on 5 Jan 2023

OK, I removed the restriction on IF. In any case, David found a clever way around that restriction (as well as submitted legitimate solutions.)

You did try the command that I hinted at. I did not compute any binary representations.

Christian Schröder on 5 Jan 2023

Yeah, not being able to used if statements required me to get creative too, doubly so since (in the interest of cutting down running time) I did not want to compute a result needlessly. Turns out that while loops can be used as a sort of poor man's if.

Perhaps I'll try that function again then. I was really surprised that it made the code run (much) slower, I would've thought that it was implemented in some optimized way that would beat hand-coded dec2bin()'s by a handy amount. It might be that I did not use it in the optimal manner.

Solution Comments

Show comments

Problem Recent Solvers4

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 57492. Compute the Tetris sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author249

Problem Tags

Community Treasure Hunt

Problem 57492. Compute the Tetris sequence

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers4

Suggested Problems

More from this Author249

Problem Tags

Community Treasure Hunt

Players