{{DISPLAYTITLE:de Bruijn sequences}}
The sequences are named after the Dutch mathematician &nbsp; Nicolaas Govert de Bruijn.


A note on Dutch capitalization: &nbsp; Nicolaas' last name is &nbsp; '''de Bruijn''', &nbsp; the &nbsp; '''de''' &nbsp; isn't normally capitalized
unless it's the first word in a sentence. &nbsp; Rosetta Code (more or less by default or by fiat) requires the first word in the task name to be
capitalized.


In combinatorial mathematics, &nbsp; a &nbsp; '''de Bruijn sequence''' &nbsp; of order &nbsp; <big> ''n'' </big> &nbsp; on
a &nbsp; <big> size-''k'' </big> &nbsp; alphabet (computer science) &nbsp; <big> ''A'' </big> &nbsp; is a cyclic sequence in which every
possible &nbsp; <big> length-''n'' </big> &nbsp; string (computer science, formal theory) &nbsp; on &nbsp; <big> ''A'' </big> &nbsp; occurs
exactly once as a contiguous substring.
<!--
──────────────────────────────────────────────────────────────────────────────────────────────────────────
Yeah,  I know,  it's a pretty big mouthful,  but it's what Wikipedia uses, so I went with that definition.
──────────────────────────────────────────────────────────────────────────────────────────────────────────
!-->

Such a sequence is denoted by &nbsp; <big> ''B''(''k'', ''n'') </big> &nbsp; and has
length &nbsp; <big>''k''<sup>''n''</sup></big>, &nbsp; which is also the number of distinct substrings of
length &nbsp; <big>''n''</big> &nbsp; on &nbsp; <big>''A''</big>; &nbsp; &nbsp;
<br>de Bruijn sequences are therefore optimally short.

<!--
──────────────────────────────────────────────────────────────────────────────────────────────────────────
Expressing the (below) equation with a  <math>  HTML tag causes it to "blow up" on Rosetta Code's version.
──────────────────────────────────────────────────────────────────────────────────────────────────────────
!-->
There are:
                          <big><big><big>(k!)<sup>k<sup>(n-1)</sup></sup> &nbsp; <big><b>&divide;</b></big> &nbsp; k<sup>n</sup></big></big></big>
distinct de Bruijn sequences &nbsp; <big> ''B''(''k'', ''n''). </big>


;Task:
For this Rosetta Code task, &nbsp; a &nbsp; '''de Bruijn''' &nbsp; sequence is to be generated that can be used to shorten a brute-force attack on
a &nbsp; [[wp:Personal_Identification_Number|PIN]]-like &nbsp; code lock that does not have an "enter"
key and accepts the last &nbsp; <big> ''n'' </big> &nbsp; digits entered.


Note: &nbsp; [[wp:Automated_teller_machine|automated teller machines (ATMs)]] &nbsp; used to work like
this, &nbsp; but their software has been updated to not allow a brute-force attack.


;Example:
A &nbsp; [[wp:digital_door_lock|digital door lock]] &nbsp; with a 4-digit code would
have ''B''&thinsp;(10,&nbsp;4) solutions, &nbsp; with a length of &nbsp; '''10,000''' &nbsp; (digits).

Therefore, only at most &nbsp; &nbsp; '''10,000 + 3''' &nbsp; &nbsp; (as the solutions are cyclic or ''wrap-around'') &nbsp; presses are needed to
open the lock.

Trying all 4-digit codes separately would require &nbsp; '''4 &times; 10,000''' &nbsp; or &nbsp; '''40,000''' &nbsp; presses.


;Task requirements:
:* &nbsp; Generate a de Bruijn sequence for a 4-digit (decimal) PIN code.
:::* &nbsp; Show the length of the generated de Bruijn sequence.
:::* &nbsp; (There are many possible de Bruijn sequences that solve this task, &nbsp; one solution is shown on the ''discussion'' page).
:::* &nbsp; Show the first and last &nbsp; '''130''' &nbsp; digits of the de Bruijn sequence.
:* &nbsp; Verify that all four-digit (decimal) &nbsp; '''1,000''' &nbsp; PIN codes are contained within the de Bruijn sequence.
:::* &nbsp; 0000, 0001, 0002, 0003, &nbsp; ... &nbsp; 9996, 9997, 9998, 9999 &nbsp; (note the leading zeros).
:* &nbsp; Reverse the de Bruijn sequence.
:* &nbsp; Again, perform the (above) verification test.
:* &nbsp; Replace the 4,444<sup>th</sup> digit with a period (.) in the original de Bruijn sequence.
:::* &nbsp; Perform the verification test (again). &nbsp; There should be four PIN codes missing.


(The last requirement is to ensure that the verification tests performs correctly. &nbsp; The verification processes should list
any and all missing PIN codes.)

Show all output here, on this page.

{{Template:Strings}}


;References:
:* &nbsp; Wikipedia           entry: &nbsp; [[wp:De_Bruijn_sequence|de Bruijn sequence]].
:* &nbsp; MathWorld           entry: &nbsp; [http://mathworld.wolfram.com/deBruijnSequence.html de Bruijn sequence].
:* &nbsp; An &nbsp;OEIS&nbsp; entry: &nbsp; [[oeis:A166315|A166315 lexicographically earliest binary de Bruijn sequences, B(2,n)]] &nbsp; &nbsp; --- Not B(10,4), &nbsp; but possibly relevant.
<br><br>

