Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Note, when I say "negate", I mean replace all ones with zeroes (i.e. a bitwise negation)

The Thue-Morse sequence goes like 01101001

The way you generate it is:

Start by taking 0. Negate what is left and append it to the end.

So, take 0. Negate it and add that to the end - 01

Then take that and negate it and add that to the end - 0110

And so on.

Another interesting property of this is that distance between zeros creates an "irrational" and non-repeating string.

So:

0110100110010110
|__|_||__||_|__|
 2  1 0 2 01 2          <------------Print this!

Can you write a program that, when input n, will output the first n digits of the string to printed?

This is code golf, so shortest number of bytes wins!

share|improve this question
6  
Not requiring a specific base for the output seems loopholey. The Thue-Morse sequence itself is the desired output, in unary and with 0 as separator. – Dennis Mar 14 at 19:04
5  
oeis.org/A036577 – xnor Mar 14 at 21:40

16 Answers 16

up vote 2 down vote accepted

Jelly, 9 bytes

;¬$‘¡TI’ḣ

Try it online!

How it works

;¬$‘¡TI’ḣ  Main link. Argument: n

  $        Create a monadic chain that does the following to argument A (list).
 ¬         Negate all items of A.
;          Concatenate A with the result.
   ‘¡      Execute that chain n + 1 times, with initial argument n.
     T     Get all indices of truthy elements (n or 1).
      I    Compute the differences of successive, truthy indices.
       ’   Subtract 1 from each difference.
        ḣ  Keep the first n results.
share|improve this answer

Python 3 2, 104 92 88 84 bytes

This is a pretty rudimentary solution based on building a ternary Thue-Morse sequence from scratch. This sequence is identical to the one being asked, though someone else will have to write a more thorough explanation of why that is. At any rate, this sequence is only a trivial modification of this one, A036580.

Edit: Changed the for loop into a list comprehension, changed from a function to a program, and changed the whole thing to Python 2. Thanks to Dennis for golfing help.

n=input()
s="2"
while len(s)<n:s="".join(`[1,20,210][int(i)]`for i in s)
print s[:n]
share|improve this answer

Julia, 56 50 bytes

n->(m=1;[m=[m;1-m]for _=0:n];diff(find(m))[1:n]-1)

This is an anonymous function that accepts an integer and returns an integer array. To call it, assign it to a variable.

We generate the bit-swapped Thue-Morse sequence by starting with an integer m = 1, then we append 1-m to m as an array n+1 times, where n is the input. This generates more terms than we need. We then locate the ones using find(m), get the difference between consecutive values using diff, and subtract 1 elementwise. Taking the first n terms of the resulting array gives us what we want.

Saved 6 bytes and fixed an issue thanks to Dennis!

share|improve this answer

PowerShell, 102 bytes

filter x($a){2*$a+([convert]::toString($a,2)-replace0).Length%2}
0..($args[0]-1)|%{(x($_+1))-(x $_)-1}

A little bit of a different way of computing. PowerShell doesn't have an easy way to "get all indices in this array where the value at that index equals such-and-such", so we need to get slightly creative.

Here we're using A001969, the "numbers with an even number of 1s in their binary expansion", which completely coincidentally gives the indices of the 0s in the Thue-Morse sequence. ;-)

The filter calculates that number. For example, x 4 would give 9. We then simply loop from 0 to our input $args[0], subtracting 1 because we're zero-indexed, and each iteration of the loop print out the difference between the next number and the current number. Output is added onto the pipeline and implicitly output with newlines.

Example

PS C:\Tools\Scripts\golfing> .\print-the-difference-in-the-thue-morse.ps1 6
2
1
0
2
0
1
share|improve this answer
    
The relation with A001969 is a great finding! – Luis Mendo Mar 14 at 22:53

Haskell, 42 bytes

l=2:(([[0..2],[0,2],[1]]!!)=<<l)
(`take`l)

Usage example: (`take`l) 7 -> [2,1,0,2,0,1,2].

It's an implementation of a036585_list from A036585 shifted down to 0, 1 and 2. Golfing: concat (map f l) is f =<< l and f 0=[0,1,2]; f 1=[0,2]; f 2=[1] is ([[0..2],[0,2],[1]]!!).

Note: l is the infinite sequence. It takes 10 bytes or about 25% to implement the take-first-n-elements feature.

share|improve this answer

Mathematica, 79 68 70 bytes

(Differences[Join@@Position[Nest[#~Join~(1-#)&,{0},#+2],0]]-1)[[;;#]]&
share|improve this answer
1  
Fails for n<3. – murphy Mar 14 at 20:54

MATL, 14 11 bytes

Q:qB!Xs2\dQ

Try it online!

As pointed out by @TimmyD in his answer, the desired sequence is given by the consecutive differences of A001969. The latter can in turn be obtained as the Thue-Morse sequence plus 2*n. Therefore the desired sequence is given by the (consecutive differences of the Thue-Morse sequence) plus one.

On the other hand, the Thue-Morse sequence can be obtained as the number of ones in the binary representation of n, starting from n=0.

Q:q    % take input n implicitly and generate row vector [0,1,...,n]
B!     % 2D array where columns are the binary representations of those numbers
Xs     % sum of each column. Gives a row vector of n+1 elements
2\     % parity of each sum
d      % consecutive differences. Gives a row vector of n elements
Q      % increase by 1. Display implicitly
share|improve this answer
    
May I request parenthesization in (consecutive differences of the Thue-Morse sequence) plus 1? – CalculatorFeline Mar 15 at 2:37
    
@CatsAreFluffy You are totally right. Done – Luis Mendo Mar 15 at 9:50

05AB1E, 14 13 bytes

Code:

ÎFDSÈJJ}¥1+¹£

Explanation:

Î              # Push 0 and input
 F     }       # Do the following n times
  DS           # Duplicate and split
    È          # Check if even
     JJ        # Join the list then join the stack
        ¥1+    # Compute the differences and add 1
           ¹£  # Return the [0:input] element

Try it online!

share|improve this answer

Python, 69 bytes

t=lambda n:n and n%2^t(n/2)
lambda n:[1+t(i+1)-t(i)for i in range(n)]

The ith term of this sequence is 1+t(i+1)-t(i), where t is the Thue-Morse function. The code implements it recursively, which is shorter than

t=lambda n:bin(n).count('1')%2
share|improve this answer

Mathematica, 65 bytes

SubstitutionSystem[{"0"->"012","1"->"02","2"->"1"},"0",#][[;;#]]&

Beats my other answer, but doesn't beat the extra-spicygolfed version. Now normally I stick my code in quotes, then pull it out because Mathematica loves adding spaces to your code (which do nothing) but it never messes with strings, but that doesn't work for code that itself has quotes...

Whatever, I'm just using the magic builtin for this. Output is a string.

share|improve this answer
    
We now have 4 Mathematica answers: My original, the nonverbal one (it's 5 if the symbolonly one counts), the extra-golfed one, and my magic builtin. – CalculatorFeline Mar 15 at 16:06

Mathematica, 58 bytes

Differences[Nest[Join[#,1-#]&,{0},#]~Position~0][[;;#]]-1&
share|improve this answer
1  
How do I know you didn't take my solution and golf it? – CalculatorFeline Mar 15 at 0:14
    
@catsarefluffy I did adapt your idea to generate the sequence (golfing it by cutting the infix operator), but felt that the method used here of transforming that into the intended output was very different and more suited to a new answer than a suggested edit. – A Simmons Mar 15 at 0:54
    
@catsarefluffy I've just seen your edit. the last I'd seen it was in its original form when I did this. I'll remove this answer but you'll just have to trust me that it was independent :) – A Simmons Mar 15 at 0:56
    
1;;# can be replaced with simply ;;#. – LegionMammal978 Mar 15 at 1:23
    
Actually I got the output transform from TimmyD's answer. (Specifically, the first paragraph made me remember about Position.) – CalculatorFeline Mar 15 at 2:32

Perl, 45 + 2 = 47 bytes

$_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;say$&

Requires the -p and -a flag:

$ perl -pa morse-seq.pl <<< 22                                                                            
2102012101202102012021

Port of @Sherlock9 answer

Saved 9 bytes thanks to Ton

share|improve this answer
    
The -a option gives you a free copy of the input, so $_=2;s/./(1,20,210)[$&]/ge until/.{@F}/;$_=$& – Ton Hospel Mar 15 at 13:02
    
@TonHospel Thats perfect, can't believe I didn't think of that :-) And I can save the -p with -E: say$& at the end if we assume that Perl > v5.18 – andlrc Mar 15 at 13:17

JavaScript (ES6), 73 67 bytes

f=(n,s="2")=>s[n]?s.slice(0,n):f(n,s.replace(/./g,c=>[1,20,210][c]))

Port of @Sherlock9's answer.

edit: Saved 6 bytes thanks to @WashingtonGuedes.

share|improve this answer
    
Would !s[n] work in place of s.length<n ? Or maybe just s[n] with ?: inverted? – removed Mar 15 at 11:49

CJam (19 bytes)

1ri){2b:^}%2ew::-f-

Online demo

This uses the approach of incrementing the successive differences between elements of the Thue-Morse sequence.


My shortest approach using rewriting rules is 21 bytes:

ri_2a{{_*5*)3b~}%}@*<

(Warning: slow). This encodes the rewriting rules

0  ->  1
1  ->  20
2  ->  210

as

x -> (5*x*x + 1) in base 3
share|improve this answer

Ruby, 57 bytes

A port of xnor's Python answer. The changes mostly lie in the ternary statement in t in place of the and due to 0 being truthy in Ruby, and using (1..n).map and 1+t[i]-t[i-1] to save bytes vs. importing the list comprehension directly.

t=->n{n<1?n:n%2^t[n/2]}
->n{(1..n).map{|i|1+t[i]-t[i-1]}}
share|improve this answer
    
0 is truthy? How does that work?? – CalculatorFeline Mar 15 at 16:06
    
@CatsAreFluffy In my experience, poorly – Sherlock9 Mar 15 at 16:47

Mathematica (almost nonverbal), 107 110 bytes

({0}//.{n__/;+n<2#}:>{n,{n}/.x_:>(1-x)/._[x__]:>x}//.{a___,0,s:1...,0,b___}:>{a,+s/.(0->o),0,b}/.o->0)[[;;#]]&

The sequence is generated by repeatedly applying a replacement rule. Another rule transforms it to the desired output. If enough people are interested, I'll explain in detail.

non-alphanumeric version

({$'-$'}//.{$__/;+$/#
<($'-$')!+($'-$')!}:>
{$,{$}/.$$_:>(($'-$')
!-$$)/.{$$__}:>$$}//.
{$___,$'-$',$$:($'-$'
)!...,$'-$',$$$___}:>
{$,+$$/.($'-$'->$$$$)
,$'-$',$$$}/.$$$$->$'
-$')[[;;#]]

as suggested by CatsAreFluffy.

share|improve this answer
    
I think it's safe to assume that people are sufficiently interested in an explanation for just about any answer. Speaking only for myself, I don't upvote submissions without explanations (unless the approach is obvious). – Alex A. Mar 14 at 21:13
    
And if you turn all letters into sequences of $ and replace 0 with x-x (where x is an unused sequence of $) (and use (x-x)! for 1 (ditto)), we be alphanumeric-free. – CalculatorFeline Mar 15 at 0:12
    
Bytesave: Use {x__} instead of _[x__] – CalculatorFeline Mar 15 at 2:39
    
I'm actually pretty sure that Mathematica is Turing-complete on symbols only or $[_]:=-/; (both by counter machine emulation) – CalculatorFeline Mar 15 at 16:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.