Thue-Morse: Difference between revisions

*   YouTube entry: [https://www.youtube.com/watch?v=prh72BLNjIk The Fairest Sharing Sequence Ever]

*   YouTube entry: [https://www.youtube.com/watch?v=Tt5TTid6YXk Math and OCD - My story with the Thue-Morse sequence]

<br><br>

 

=={{header|Ada}}==

Implementation using an L-system.

 

 

procedure Thue_Morse is

Ada.Text_IO.Put_Line(Integer'Image(I) & ": " & Sequence(I));

end loop;

 

{{out}}

 

=={{header|ALGOL 68}}==

OP FLIP = ( STRING s )STRING:

BEGIN

print( ( tm, newline ) );

tm +:= FLIP tm

{{out}}

<pre>

0110100110010110100101100110100110010110011010010110100110010110

</pre>

 

=={{header|AppleScript}}==

 

{{Trans|JavaScript}}

 

 

-- thueMorse :: Int -> String

intercalate("", ¬

end thueMorse

 

 

on run

 

 

 

-- enumFromTo :: Int -> Int -> [Int]

on enumFromTo(m, n)

else

end if

end enumFromTo

 

-- foldl :: (a -> b -> a) -> a -> [b] -> a

end tell

end foldl

 

-- intercalate :: Text -> [Text] -> Text

return strJoined

end intercalate

 

-- map :: (a -> b) -> [a] -> [b]

end tell

end map

 

-- Lift 2nd class handler function into 1st class script wrapper

end script

end if

<pre>"0110100110010110100101100110100110010110011010010110100110010110"</pre>

 

=={{header|AWK}}==

 

=={{header|BASIC}}==

==={{header|BASIC256}}===

{{trans|FreeBASIC}}

tm = "0"

 

Next j

End

{{out}}

<pre>

 

==={{header|Sinclair ZX81 BASIC}}===

20 PRINT "T0=";T$

30 FOR I=1 TO 7

100 NEXT J

110 PRINT T$

{{out}}

<pre>T0=0

 

=={{header|BBC BASIC}}==

tm$ = "0"

PRINT tm$

IF MID$(previous$, i%, 1) = "1" THEN tm$ += "0" ELSE tm$ += "1"

NEXT

{{out}}

<pre>0

01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110</pre>

 

=={{header|Befunge}}==

This implements the algorithm that counts the 1 bits in the binary representation of the sequence number.

 

 

{{out}}

<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110</pre>

 

=={{header|C}}==

===C: Using string operations===

{{trans|Java}}

#include <stdlib.h>

#include <string.h>

puts(sequence);

return 0;

{{out}}

<pre>

 

===C: By counting ones in binary representation of an iterator===

 

/**

 

return 0;

 

{{out}}

 

===C: By counting ones in binary representation of an iterator (w/User options)===

 

/**

 

return 0;

 

{{out}}

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Text;

 

}

}

<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>

 

=={{header|C++}}==

#include <iostream>

#include <iterator>

return 0;

}

{{out}}

<pre>

0110100110010110100101100110100110010110011010010110100110010110

</pre>

 

=={{header|Common Lisp}}==

(loop with result = (make-array (length bit-vector) :element-type 'bit)

for b across bit-vector

do (print-bit-vector value)))

 

{{out}}

<pre>

0110100110010110100101100110100110010110011010010110100110010110

</pre>

 

=={{header|Crystal}}==

{{trans|Javascript}}

 

tmp = ""

}

 

 

{{out}}

=={{header|D}}==

{{trans|C}}

import std.stdio;

 

}

}

{{out}}

<pre>

0110100110010110100101100110100110010110011010010110100110010110

</pre>

 

=={{header|Elena}}==

{{trans|C#}}

import system'text;

 

var sb1 := TextBuilder.load("0");

var sb2 := TextBuilder.load("1");

{

var tmp := sb1.Value;

{

sequence(6)

{{out}}

<pre>

 

=={{header|Elixir}}==

IO.puts s

s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end)

Stream.iterate('0', fn s -> s ++ Enum.map(s, fn c -> if c==?0, do: ?1, else: ?0 end) end)

|> Enum.take(7)

 

{{out}}

01101001100101101001011001101001

0110100110010110100101100110100110010110011010010110100110010110

</pre>

 

=={{header|Factor}}==

{{works with|Factor|0.98}}

 

: thue-morse ( seq n -- seq' )

: print-tm ( seq -- ) [ number>string ] map "" join print ;

 

{{out}}

<pre>

=={{header|Fortran}}==

{{works with|Fortran|90 and later}}

implicit none

logical :: f(32) = .false.

end do

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

Dim As String tm = "0"

 

Next j

End

{{out}}

<pre>

01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

</pre>

 

=={{header|Go}}==

 

package main

fmt.Println( tmBuffer.String() )

}

{{out}}

<pre>

Computing progressively longer prefixes of the sequence:

 

thueMorsePxs = iterate ((++) <*> map (1 -)) [0]

 

-}

main :: IO ()

{{Out}}

<pre>[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]</pre>

The infinite sequence itself:

 

thueMorse = 0 : g 1

where

main :: IO ()

{{Out}}

<pre>[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1,1]</pre>

We only show a prefix of the sequence:

 

 

Or, more compactly:

 

 

=={{header|Java}}==

 

public static void main(String[] args) {

System.out.println(sb1);

}

<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>

 

===ES5===

{{trans|Java}}

'use strict';

var i, tmp, s1 = '0', s2 = '1';

}

console.log(s1);

<pre>0110100110010110100101100110100110010110011010010110100110010110</pre>

 

===ES6===

'use strict';

 

// MAIN ---

return main();

{{Out}}

<pre>[0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,0,1]</pre>

 

=={{header|Julia}}==

{{works with|Julia|0.6}}

 

rst = Vector{Int8}(len)

rst[1] = 0

end

 

 

{{out}}

 

=={{header|Kotlin}}==

{{trans|Java}}

val sb0 = StringBuilder("0")

val sb1 = StringBuilder("1")

val tmp = sb0.toString()

sb0.append(sb1)

}

 

for (i in 0..6) println("$i : ${thueMorse(i)}")

 

{{out}}

 

=={{header|Lambdatalk}}==

 

{def thue_morse

-> 0110100110010110100101100110100110010110011010010110100110010110

 

 

=={{header|Lua}}==

 

function ThueMorse:show ()

ThueMorse:show()

ThueMorse:addBlock()

{{out}}

<pre>0

01101001

0110100110010110</pre>

 

=={{header|Modula-2}}==

FROM Strings IMPORT Concat;

FROM Terminal IMPORT WriteString,WriteLn,ReadChar;

Sequence(6);

ReadChar;

 

=={{header|NewLISP}}==

 

(setf TM '(0))

(println TM)

(Thue-Morse 5)

(exit)

 

{{out}}

(0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0)

</pre>

 

=={{header|OASYS Assembler}}==

 

[*'A] ; Ensure the vocabulary is not empty

%@FO> ; Reset object pointer

CR ; Line break

The standard DOS-based interpreter will display an error message about word too long after 7 lines are output; this is because the 8th line does not fit in 80 columns.

 

=={{header|Objeck}}==

{{trans|Java}}

function : Main(args : String[]) ~ Nil {

Sequence(6);

}

}

 

Output:

===By counting ones in binary representation of an iterator===

{{trans|C}}

input: the number to have its bit counted

output: the number of bits set to 1 *)

| _ -> assert false)

done;

 

 

===Using string operations===

{{trans|Objeck}}

let sb1 = Buffer.create 100 in

let sb2 = Buffer.create 100 in

 

let () =

 

=={{header|Pascal}}==

{{works with|Free Pascal}}

Like the C++ Version [[http://rosettacode.org/wiki/Thue-Morse#C.2B.2B]] the lenght of the sequence is given in advance.

function fThueMorse(maxLen: NativeInt):AnsiString;

//double by appending the flipped original 0 -> 1;1 -> 0

const

cVal0 = '^';cVal1 = 'v';// cVal0 = '0';cVal1 = '1';

var

pOrg,

i,k,ml : NativeUInt;//MaxLen: NativeInt

Begin

//setlength only one time

setlength(result,Maxlen);

pOrg := @result[1];

pOrg[0] := cVal0;

IF maxlen = 1 then

EXIT;

pRpl := pOrg;

inc(pRpl);

i := 0;

repeat

inc(pRpl);

inc(i);

IF k > 0 then

repeat

inc(pRpl);

inc(i)

writeln(i:3,' ',fThueMorse(i));

fThueMorse(1 shl 30);

{{Output}}<pre>Compile with /usr/lib/fpc/3.0.1/ppc386 "ThueMorse.pas" -al -XX -Xs -O4 -MDelphi

without -O4 -> 2 secs

=={{header|Perl}}==

{{works with|Perl|5.x}}

{

my $s = shift;

$str .= complement($str);

}

{{out}}

<pre>

 

=={{header|Phix}}==

{{Out}}

<pre>

 

=={{header|Phixmonti}}==

dup len

for

dup print nl nl

inverte chain

 

=={{header|PHP}}==

(see https://en.wikipedia.org/wiki/Thue%E2%80%93Morse_sequence)

 

 

function thueMorseSequence($length) {

for ($n = 10 ; $n <= 100 ; $n += 10) {

echo sprintf('%3d', $n), ' : ', thueMorseSequence($n), PHP_EOL;

 

{{out}}

 

=={{header|PicoLisp}}==

(prinl R)

(for (X 1 (>= 32 X))

(bin (x| (dec (** 2 X)) R)) ) ) )

(prinl (pack 0 (bin R)))

 

=={{header|PowerShell}}==

{

# Start with seed 0

New-ThueMorse 5

New-ThueMorse 16

{{out}}

<pre>01101

=={{header|PureBasic}}==

{{trans|C}}

 

Procedure.i count_bits(v.i)

Next

PrintN(~"\n...fin") : Input()

{{out}}

<pre>0110100110010110100101100110100110010110011010010110100110010110100101100110100101101001100101100110100110010110100101100110100110010110011010010110100110010110011010011001011010010110011010010110100110010110100101100110100110010110011010010110100110010110

=={{header|Python}}==

===Python: By substitution===

m='0'

print(m)

m=m0+m

print(m)

{{out}}

<pre>0

 

===Python: By counting set ones in binary representation===

>>> def thue_morse_digits(digits):

... return [bin(n).count('1') % 2 for n in range(digits)]

 

>>>

 

===Python: By [http://mathworld.wolfram.com/SubstitutionSystem.html substitution system]===

>>> def thue_morse_subs(chars):

... ans = '0'

>>> thue_morse_subs(20)

'01101001100101101001'

 

>>>

 

=={{header|R}}==

thue_morse <- function(steps) {

sb1 <- "0"

}

cat(thue_morse(6), "\n")

{{out}}

<pre>

 

=={{header|Racket}}==

(define 1<->0 (match-lambda [#\0 #\1] [#\1 #\0]))

(define (thue-morse-step (s "0"))

(if (zero? n) (reverse rv) (inr (sub1 n) (cons (thue-morse-step (car rv)) rv)))))

 

{{out}}

<pre>0

{{Works with|rakudo|2018.03}}

First 8 of an infinite sequence

 

{{out}}

01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001

^C</pre>

 

=={{header|REXX}}==

===using functions===

Programming note: &nbsp; ''pop count'' &nbsp; (or &nbsp; ''weight'') &nbsp; is the number of &nbsp; <b>1</b>'s &nbsp; bits in the binary representation of a number.

parse arg N . /*obtain the optional argument from CL.*/

if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

$pop: return length( space( translate( arg(1), , 0), 0) ) /*count 1's in number.*/

{{out|output|text=&nbsp; when using the default input:}}

<pre>

 

===using in-line code===

parse arg N . /*obtain the optional argument from CL.*/

if N=='' | N=="," then N= 80 /*Not specified? Then use the default.*/

$= $ || length( space( translate( x2b( d2x(j) ), , 0), 0)) // 2 /*append to $.*/

end /*j*/

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}} <br>

 

 

Because of this, the displaying of the output lacks the granularity of the first two REXX versions.

parse arg N . /*obtain the optional argument from CL.*/

do j=1 for N /*generate sequence up to the Nth item.*/

end /*j*/

<pre>

0110100110010110100101100110100110010110011010010110100110010110

 

=={{header|Ring}}==

tm = "0"

see tm

see nl

return (previous + tm)

Output:

<pre>

01101001100101101001011001101001

0110100110010110100101100110100110010110011010010110100110010110

</pre>

 

=={{header|Ruby}}==

 

{{out}}

 

=={{header|Rust}}==

 

fn neg(sequence: &String) -> String {

sequence = format!("{}{}", sequence, neg(&sequence));

}

 

{{out}}

 

=={{header|Scala}}==

val (sb0, sb1) = (new StringBuilder("0"), new StringBuilder("1"))

(0 until n).foreach { _ =>

}

 

{{Out}} See it running in your browser by [https://scastie.scala-lang.org/rsF3Y5ABQoK0zZMMA3m6Ow Scastie (JVM)].

 

=={{header|Sidef}}==

func (repeat, seed) {

callback(seed)

}

 

{{out}}

<pre>

=={{header|SQL}}==

This example is using SQLite.

You can add a LIMIT clause to the end to limit how many lines of output you want.

 

Since <tt>string map</tt> correctly handles overlapping replacements, the simple map <tt>0 -> 01; 1 -> 10</tt> can be applied with no special handling:

 

# this could also be written as:

# interp alias {} tm_expand {} string map {0 01 1 10}

}

return $s

 

Testing:

 

puts [tm $i]

 

{{out}}

For giggles, also note that the above SQL solution can be "natively" applied in Tcl8.5+, which bundles Sqlite as a core extension:

 

package require sqlite3 ;# available with Tcl8.5+ core

sqlite3 db "" ;# create in-memory database

db eval {with recursive a(a) as (select '0' union all select replace(replace(hex(a),'30','01'),'31','10') from a) select a from a limit $LIMIT} {

puts $a

 

=={{header|uBasic/4tH}}==

Print Using "_#";x;": "; ' print sequence

For y = 0 To (2^x)-1 ' element loop

a@ = SHL(a@, -1) ' shift the number

Loop

{{Out}}

<pre> 0: 0

 

=={{header|VBA}}==

 

Sub Main()

End If

Thue_Morse = s & k

{{Out}}

<pre>1:=> 0

7:=> 0110100110010110100101100110100110010110011010010110100110010110

8:=> 01101001100101101001011001101001100101100110100101101001100101101001011001101001011010011001011001101001100101101001011001101001</pre>

 

=={{header|XLISP}}==

(defun flip-bits (s)

(defun flip (l)

; test THUE-MORSE by printing the strings it returns for n = 0 to n = 6

 

{{out}}

<pre>"0"

"01101001100101101001011001101001"

"0110100110010110100101100110100110010110011010010110100110010110"</pre>

 

=={{header|Yabasic}}==

{{trans|Phix}}

for i=1 to 8

? tm$

next

return tm$

 

=={{header|zkl}}==

"12233334444" - "23"-->"14444"

println() returns the result it prints (as a string).

{{trans|Java}}

var sb1=Data(Void,"0"), sb2=Data(Void,"1");

r:=sb1.text; sb1.append(sb2); sb2.append(r);

r

{{out}}

<pre>