text:
Is this string a letter doing a cartwheel?
Challenge inspiration was this that I saw somewhere:

The word "nun" is just the letter n doing a cartwheel

Your challenge is to take a string and determine if it is the first letter doing a cartwheel.
Rules
A string is a letter doing a cartwheel if:

The first letter is the same as the last letter. (The letter can't land on its head.)
The string alternates between cartwheeling letters every one character.

The cartwheeling letters are n and u, m and w, b and q. Note that n and w together are not cartwheeling letters, and neither are w and b.

You will take a string using any of our standard input methods.
You will output a truthy value if the string is a cartwheeling letter, and a falsy value if it is not. Output can be done using any standard output methods.

Additional rules:

Only lowercase cartwheel letters n/u/m/w/b/q need to be handled.
You may assume that input is never empty.
A one-character string is not a valid cartwheel.

Test cases
Input        -> Output
nun          -> truthy
nunun        -> truthy
nunununu     -> falsy
wmw          -> truthy
wmwun        -> falsy
bqbqbqbqbqb  -> truthy
v^v^v        -> falsy
AVAVA        -> falsy
OOO          -> falsy
ununununu    -> truthy
nunwmwnun    -> falsy
nun unun     -> falsy
nunwmw       -> falsy
nnuunnuunnuu -> falsy
nwnwnwnwn    -> falsy
m            -> falsy
nunuuunun    -> falsy

Winner
As with code-golf, the shortest code (in each language) wins!

I think b cartwheels into q, doesn't it? d and p are also cartwheel buddies. They key is that they rotate, not flip.

Another testcase suggestion: uwuwuwuwuwu

Why bqb but not pdp?

@aschepler I messed up.

Since dpd, pdp  and such don't work, I think you should have them in the test cases with a falsy answer.

Jelly, 23 bytes
This took more work than one might think!
“nmbuwq”iÐ€o⁵IAs2⁼€3,3Ȧ

A monadic link taking a list of characters and returning 1 (truthy) or 0 (falsey).
Try it online! or see a test suite.
How?
Finds the index of each character of the input in the 1-indexed list of characters nmbuwq. This string is arranged such that the indexes of pairs are three apart, as such the incremental difference of the indexes for valid cartwheels will be repetitions of one of [-3,3] or [3,-3].
When an item is not found in a list by the "index of" atom, i, it returns 0, which would pair unfound characters with b, making input like bxbxb truthy. So 0s are replaced by 10 a value more than three away from any other value prior to checking for validity.
“nmbuwq”iÐ€o⁵IAs2⁼€3,3Ȧ - Link: list of characters, s
         Ð€             - map across c in s:
        i               -   first index of c in (1-indexed; 0 if not present)
“nmbuwq”                -   literal "nmbuwq"
            ⁵           - literal 10
           o            - logical or (vectorises - replace any 0s with 10s)
             I          - incremental differences (i.e. deltas)
              A         - absolute value (vectorises)
               s2       - split into chunks of 2 (possibly with a single remainder)
                   3,3  - pair three with three = [3,3]
                 ⁼€     - equals? for €ach (1 if so, otherwise 0 - including a single 3)
                      Ȧ - any and all? (0 if any 0s or if empty, 1 otherwise)

sed 4.2.2, 30 + 1 -r = 43 31 bytes
Saved 12 bytes thanks to @Neil by shortening the first line
/nu|wm|qb/!d
/^((.).)\1*\2$/!d

Try it online!
Deletes input if falsey, otherwise does nothing to the input.
Explanation
With the -r flag, we do not need to use \( and \) for capturing groups and this saves bytes.
/nu|wm|qb/!                # On every line that does not match this regex
           d               # Delete
/^((.).)\1*\2$/!           # On every line that does not math
 ^((.).)                   #  the first two characters at the beginning of the line
        \1*                #  repeated
           \2$             #  with the first character at the end of the line
                d          # Delete

Here comes the sed wizard...

@MDXF I'm far from being a wizard, still a beginner :)

Everything in sed looks like wizardry to me. :P

You only have to check for containment of half of the letter pairs e.g. both unu and nun contain nu and the second line ensures that the rest of the letters match those two.

JavaScript (ES6), 82 78 77 bytes
Saved 1 byte by using two falsy values, as suggested by ThePirateBay and MD XF.
([c,...s],S='bqwmun')=>s.reduceRight((r,a)=>r&a==S[S.search(c)^++k&1],k=s>'')

Test cases

let f =

([c,...s],S='bqwmun')=>s.reduceRight((r,a)=>r&a==S[S.search(c)^++k&1],k=s>'')

console.log('Truthy ...')
console.log(f("nun"         )) // -> truthy
console.log(f("nunun"       )) // -> truthy
console.log(f("wmw"         )) // -> truthy
console.log(f("bqbqbqbqbqb" )) // -> truthy
console.log(f("ununununu"   )) // -> truthy

console.log('Falsy ...')
console.log(f("nunununu"    )) // -> falsy
console.log(f("wmwun"       )) // -> falsy
console.log(f("v^v^v"       )) // -> falsy
console.log(f("AVAVA"       )) // -> falsy
console.log(f("OOO"         )) // -> falsy
console.log(f("nunwmwnun"   )) // -> falsy
console.log(f("nun unun"    )) // -> falsy
console.log(f("nunwmw"      )) // -> falsy
console.log(f("nnuunnuunnuu")) // -> falsy
console.log(f("m"           )) // -> falsy

Any reason for leaving && instead of &?

@ThePirateBay Well, the only reason is the consistency of the returned falsy value, although it doesn't really seem to be a requirement for this challenge. (Using & would produce either false or 0.)

@Arnauld You may remove the second &; I specified (in chat) sometime that inconsistent falsy values are allowed.

Python 3, 111 bytes
-2 bytes thanks to Mr. Xcoder.
lambda s:s[0]==s[-1]and any(any({*s[::2]}=={i[j]}and{*s[1::2]}=={i[j<1]}for j in[0,1])for i in['nu','mw','bq'])

Try it online!

sighs as you pass me in rep again

I don't feel good about this, since you're about to reach my byte count again, but -2 bytes.

Python 3, 71 bytes
lambda n:''.join(sorted({*n[1::2]}|{*n[::2]}))in"nu,mw,bq"*(n==n[::-1])

Try it online!
-1 thanks to @HyperNeutrino and -13 thanks to @ovs
If the above is found to fail for any test case, there is an alternative:
lambda n:(sorted(list({*n[1::2]}.union({*n[::2]})))in[[*'nu'],[*'mw'],[*'bq']])*n[0]==n[-1]

Try it online!

Explanation

''.join(sorted(list({*n[1::2]}).union({*n[::2]})))) - Gets the characters at odd indexes and the characters at even indexes, de-duplicates them and sorts the list formed by their union.

in'nu,mw,bq' - Checks if they are valid cart-letter combinations.

n[0]==n[-1] - Checks if the first character is the same as the last one.

Fails no test cases, good job +1

@MDXF Oh thanks! I am so relieved rn... >_<

@MDXF It does fail, in fact. Fixing soon EDIT: Fixed

You use s only once I think. You could probably get rid of the argument then.

Huh, it looked like it did in the TIO link...

@totallyhuman Yes, was just changing that. That was left from a previous version of my code.

uwuwuwuwuwu results in true

@Cowsquack So it should, I think :)

Great job fixing this!

@MDXF Thanks. It ended up being really short.

I ask the downvoter to remove the downvote (if the reason was this answer being invalid in the past). It's now fixed.

71 bytes

Invalid: nunuuunun

nuuun -> True.  This is not right.

Python 2, 63 bytes
lambda s:s[:3]in'ununqbqbwmwm'and s==s[:2]*max(len(s)/2,1)+s[0]

Try it online!

Nice answer, welcome to the site! Some tips: You could do "nu un nm mn bp pb".split() to save 4 bytes, and you could remove some whitespace. 75 bytes: lambda s:any(s==c[-1]+c*max(len(s)/2,1)for c in"nu un nm mn bp pb".split())

You could save 1 byte by doing s[0] instead of c[-1].

The 61 byte answer returns True for unmnu and unmwnu.  Really it returns false positives when (s==s[::-1])+len(set(s)) is 4, which is easy to force.  Even just 4 different characters makes it return True.

The 59 bytes breaks with single character inputs.  Sorry for picking on this one, I like Python :)

Aren't exceptions falsey? That break is intentional

Exceptions ruled not falsey - updated from 59 to 63 bytes

JavaScript (ES6), 40 bytes
s=>/^(nu|un|bq|qb|wm|mw)+$/.test(s+s[1])

Checks to see if the input string concatenated with the second character of the input string is a repeating string of the same pair of cartwheel characters.
Tests:

[
  "nun",
  "nunun",
  "nunununu",
  "wmw",
  "wmwun",
  "bqbqbqbqbqb",
  "v^v^v",
  "AVAVA",
  "OOO",
  "ununununu",
  "nunwmwnun",
  "nun unun",
  "nunwmw",
  "nnuunnuunnuu",
  "nwnwnwnwn",
  "m",
  "nunuuunun"
].forEach( x=>console.log( x, (s=>/^(nu|un|bq|qb|wm|mw)+$/.test(s+s[1]))(x) ) )

Really love the logic here! I never would have thought of adding a character at the end and testing. Nice, clean code, too, even when golfed.

Retina, 24 bytes
G`nu|mw|bq
^((.).)\1*\2$

Outputs 1 for truthy, 0 for falsy.
Port of Cows quack's answer.
Try it online!

The newer version outputs truthy for nunwmwnun (when it should be false), which was why I had the \1* in my sed answer.

@Cowsquack Ah I see.

The first line can be G`nu|mw|bp since all truthy strings contain one of those letter pairs and the second line will ensure that all of the rest of the string contains those letters too..

@Neil That fails the test case ununununu

@Okx Neil's suggestion still seems to work for that testcase Try it online!

Try it online! All test cases at once.

@Neil Sorry, my mistake. I kept the ^. Anyways, thanks for the suggestion.

If 1 is both truthy and falsy, I guess you always win? (You have a typo in your description)

@trlkly Haha. Fixed.

Haskell, 80 78 bytes
f s|l<-length s=odd l&&l>1&&any((==s).take l.cycle)(words"un nu mw wm bq qb")

Try it online!
How it works:
l<-length s        -- let l be the length of the input string

f s         =      -- return True, if
    odd l          -- l is odd and
    l > 1          -- l is greater than 1 and
    any            -- any of the following is also True
      (     )(words "  ...  ")
                   -- apply the function to each of the words "un", "nu" ... "qb"
           cycle   --  infinitely repeat the word
      take l       --  take the first l characters
     (==s)         --  and compare to s

Clojure, 156 bytes
(fn[w](let[s["nu""wm""bq"]c #(= 1(count(set %)))e #(take-nth 2 %)r #(and(c(e %))(c(e(drop 1 %))))](and(=(first w)(last w))(r w)(some #(=(set w)(set %))s))))

This was deceptively difficult! I ended up having to break it down into 3 sub problems:

Is the first letter the same as the last?
Do the letters repeat?
Are all the letters a part of one of the valid sets?

I certainly didn't win, but this was a good morning exercise! Full explanation below:
(defn cartwheel? [word]
  (let [; Valid Character Sets
        cs ["nu" "wm" "bq"]

        ; Is the list composed of only a single character?
        count-1? #(= 1 (count (set %)))

        ; Grabs every other element of the list
        every-other #(take-nth 2 %)

        ; Do the characters repeat? Works by checking if every other element is the same, then drops the first letter
        ; to check all the odd indexed characters
        repeating? #(and (count-1? (every-other %))
                         (count-1? (every-other (drop 1 %))))]

    ; Do all the predicates hold?
    (and (= (first word) (last word))
         (repeating? word)
         ; Is the set of letters in the word part of some set of the valid characters?
         (some #(= (set word) (set %)) cs))))

Python 2, 45 bytes
lambda s:s[2:]+s[1:3]==s>s[:2]in'bqbunuwmw'

Try it online!
The spaces in the string are DEL characters.

|u| is interpreted as a cartwheel.

@Harrichael I put in DEL characters to be clear.

DEL characters can still be input characters though. I like your solution but you should borrow a trick from my answer: s[:3]in'bqbqnunuwmwm'

Grime, 28 bytes
e`..-#!"nu\|bq\|mw"oTv&..v+.

Try it online!
Prints 1 for truthy inputs and 0 for falsy ones.
Explanation
Grime syntax resembles regular expressions, and a Grime program specifies a pattern that may or may not match a rectangle of characters.
e`..-#!"nu\|bq\|mw"oTv&..v+.
e`                            Match input against pattern:
      !                       Does not
     #                        contain
  ..                          a 2-character substring
    -                         which is not
       "nu\|bq\|mw"           any of these strings
                   oT         potentially reversed,
                     v&       AND
                       ..     two characters
                         v+   one or more times
                           .  then one more character.

Some features of Grime that helped shorten this:

Normally a character literal must be escaped with a backslash, but "" changes this: syntax elements are escaped but literals are not. Without the quotes, the part that enumerates the character pairs would be (\n\u|\b\p|\m\w)oT.
Unary operators that follow a binary operator (here -) act on its result: ..-#!"…"oT is equivalent to (..-"…"oT)#!.
The vs lower the precedence of the syntax elements that follow them. A lone & has higher precedence than -, but v& has lower. Similarly, ..+ is parsed as .(.+), but ..v+ is equivalent to (..)+.

Python 2, 103 bytes
lambda x:len(x)>1and{x[0],x[1]}in[{i,j}for i,j in zip('ubw','nqm')]and x==(-~len(x)/2*(x[0]+x[1]))[:-1]

Try it online!

Japt, 47 bytes
g ¦U¬o ª`q¿nwm`ò má c aU¯2)<0?0:UÅë ä¥ ©Uë ä¥ e

Try it online!

Can you compress the string to save any bytes?

nwnwn is true when it ahould be false

@Harrichael Thanks, fixed!

Pyth, 27 bytes
&qeQhQ/"nu,mw,bq"S+{%2tQ{%2

Test Suite.
Outputs 1 for truthy and False or 0 for falsy, as the OP allowed in chat.

Jelly, 27 bytes
Ḋm2Qµ³m2Q;Ṣe“nu“mw“bq”ȧ³⁼U¤

Try it online!
How it works
Ḋm2Qµ³m2Q;µṢe“nu“mw“bq”ȧ³⁼U¤  Main link; z is the argument
Ḋ                             z[1:]
 m2                           z[1::2]
   Q                          deduplicate(z[1::2])
    µ                         New Chain
     ³                        z
      m2                      z[::2]
        Q                     deduplicate(z[::2])
         ;                    deduplicate(z[1::2]) + deduplicate(z[::2])
          Ṣ                  Sort the result
           e                 Is it an element of the following?
            “nu“mw“bq”       ["nu", "mw", "bq"]
                      ȧ      It has the correct characters and:
                       ³  ¤  Nilad followed by links as nilad
                       ³     z
                        ⁼      ==
                         U        z[::-1]
                          ¤  [End chain]

Jelly... longer than Pyth?!

@Mr.Xcoder shhhh I'm working on it... xD

Hah well I'm tied with you now xD

Python 2, 69 bytes
lambda x:any([x in p*len(x)for p in'nu','mw','bq'])*len(x)%2*len(x)>2

Try it online!

Python 3, 88 bytes
lambda x:[len(x)%2,x[:2]in'nu,un,bq,qb,mw,wm',len(set(x[::2])),len(set(x[1::2]))]==[1]*4

len(x)%2: an even-length string can't end on the first character
x[:2] in: check for any of the 6 valid beginning pairs
len(set()): get the length of the sets of characters at 0,2,4... and 1,3,5...
Returns True if the list of evaluations is equal to [1,1,1,1], else False.
Try it online!

Perl 5, 55 + 1 (-p) = 56 bytes
$c={"nuunmwwmbppb"=~/./g}->{$l=chop};$_=/^($l$c)+$/&&$c

Try it online!
Prints the "upside down" version of the first character for true, nothing for false.

Beat me by a solid 18 bytes. Nice answer!

Not quite so many now.  The original was returning true for any string of all the same character.

MATL, 25 bytes
'nuwmbq'&mq2&\d~wdts~Gnqv

The ouput is a non-empty numeric column vector, which is truthy if all its entries are nonzero, and falsy otherwise. Try it online!
To verify all test cases, an if branch is added in the footer that replaces any truthy value by the string 'truthy', or any falsy value by the string 'falsy', and then displays the string.
Explanation
'nuwmbq'  % Push this string
&m        % Implicit input. For each char, push index of membership in the above
          %  string, or 0 if not member
q         % Subtract 1
2         % Push 2
&\        % Divmod. Pushes remainders, then quotients
d~        % Consecutive differences negated. Gives an array of ones iff all
          % quotients were equal
w         % Swap. Moves remainders to top
d         % Consecutive differences. Gives nonzeros iff no consecutive
          % remainders were equal
ts~       % Duplicate, sum, negate. Gives true iff sum was 0. For unequal
          % consecutive differences of remainders, this corresponds to an odd
          % number of remainders
Gnq       % Push input, length, subtract 1. True iff input longer than 1
v         % Concatenate into column vector. Truthy iff all entries are nonzero

PHP, 59+1 bytes
<?=preg_match('#^(nu|un|mw|wm|bq|qb)\1+$#',$argn.$argn[1]);

Run as pipe with -F.
partly regex solution, 101+1 bytes:
for($s=$argn;$c=$s[$i++];$p=$c)$c!=$p||die;echo$i%2<1&&preg_match("#^(nu|mw|bq)#",count_chars($s,3));

Empty output for falsy. Run as pipe with -nR.

Java 8, 57 bytes
s->s.matches("(nu)+n|(un)+u|(mw)+m|(wm)+w|(bq)+b|(qb)+q")

Try it here.
Simple regex to match all six cases. Note that Java's String#matches automatically matches the entire String, so there is no need for ^...$.

Python 2, 74 bytes
import re
re.compile('(n(un)+|u(nu)+|m(wm)+|w(mw)+|b(pb)+|p(bp)+)$').match

Try it online! This take on the problem is surprisingly competitive.

Clojure, 115 bytes
(apply some-fn(map(fn[r]#(re-matches r %))(map(fn[[x y]](re-pattern(str x"("y x")+")))["nu""un""mw""wm""bq""qb"])))

Build a regex out of each letter pair and see if the input matches one. Lots of more elegant ways to do all of these parts, but they're all more verbose. Such is life with Clojure golfing.

Perl 5, 68 + 1 = 69 bytes
if(/../&&$&=~/nu|un|bq|qb|mw|wm/){s/^($&)*//;$&=~/./;print if/^$&$/}

Run with -n.
Explanation:
# Match the first two characters, and if they exist, then...
if (/../ &&
 # Make sure they are a pair of compatible cartwheel characters.
 $&=~/nu|un|bq|qb|mw|wm/) {
  # If that's true, then eliminate as many of that pair of characters
  # from the beginning of the string as possible.
  s/^($&)*//;
  # Then get the first character out of the match (the first character
  # of the original string).
  $&=~/./;
  # Print the text (which is truthy since it's nonempty) if the original
  # first character matches exactly the remaining string.
  print if/^$&$/
  # Otherwise, print nothing (the empty string in Perl is falsy).
}

TXR Lisp, 50 bytes
(f^$ #/n(un)+|u(nu)+|m(wm)+|w(mw+)|b(qb)+|q(bq)+/)

Run:
1> (f^$ #/n(un)+|u(nu)+|m(wm)+|w(mw+)|b(qb)+|q(bq)+/)
#<intrinsic fun: 1 param>
2> [*1 "nun"]
"nun"
3> [*1 "nuns"]
nil
4> [*1 "mwm"]
"mwm"
5> [*1 "wmw"]
"wmw"
6> [*1 "abc"]
nil

f^$ is a combinator which takes a regex object and returns a function which matches that regex in an anchored way. (By itself, a regex object is function-callable object which takes a string and searches for itself through it.)

Python 3, 66 bytes
lambda x:x==len(x)//2*x[:2]+x[0]and{*x}in[{*'nu'},{*'mw'},{*'bq'}]

Try it online!

TXR: 78 74 bytes
@{x 2}@(rep :gap 0)@x@(end)@y
@(bind(x y)(#"nu un mw wm bq qb"@[x 0..1]))

Run, from system prompt. Number in prompt is termination status: 0 = success, 1 = failure:
0:$ ./txr cart.txr
nun
0:$ ./txr cart.txr
abc
1:$ ./txr cart.txr
bab
1:$ ./txr cart.txr
mwm
1:$ ./txr cart.txr
nununununun
0:$

Explanation:

@{x 2}: match two characters, bind to x variable.
@(rep :gap 0)@x@(end): repeated match with no skipped gaps: zero or more occurrences of x, the previously matched digraph.
@y: remainder of line matched, captured into y.
@(bind(x y)(foo bar)): bind x to foo, y to bar. Since x and y are already bound, they have to match foo and bar, or else there is a failure.
foo is  #"nu un mw wm bq qb", a  word list literal, syntactic sugar for the Lisp list ("nu" "un" ... "qb"). A bind match between a variable and a list means that the variable must match an element.
bar is @[x 0..1]: the one-character substring of x from its beginning. The bind match between y and this forces the last letter of the line to match the first.

C++, 268 bytes
#include<map>
#include<string>
std::map<char,char>c{{'n','u'},{'m','w'},{98,'q'},{'w','m'},{'u','n'},{'q',98}};
int w(std::string s){if(s[0]!=s[s.size()-1]||c.find(s[0])==c.end()||s.size()<3)return 0;for(int i=0;i<s.size()-1;i+=2)if(s[i+1]!=c[s[i]])return 0;return 1;}

Save 10 bytes by using the ASCII values for all the characters instead of just two.

@MDXF n = 110, u = 117, m = 109, w = 119, q = 113. So using ASCII values or not does not matter for any chars higher than c ( 99 )

JavaScript (ES6), 63 bytes
s=>/bq|wm|un/.test(s)&s.replace(RegExp(s[0]+s[1],'g'),'')==s[0]

Returns 1 or 0.
Explanation
All cartwheel strings will have one or more of bq, wm, or un.  We test for that with:
/bq|wm|un/.test(s)

If you replace all instances of the first two letters of a cartwheel string with nothing, you're left with the first letter of the string.  We test for that with:
s.replace(RegExp(s[0]+s[1],'g'),'')==s[0]

let f=
s=>/bq|wm|un/.test(s)&s.replace(RegExp(s[0]+s[1],'g'),'')==s[0]

console.log(f('nun'))          // truthy
console.log(f('nunun'))        // truthy
console.log(f('nunununu'))     // falsy
console.log(f('wmw'))          // truthy
console.log(f('wmwun'))        // falsy
console.log(f('bqbqbqbqbqb'))  // truthy
console.log(f('v^v^v'))        // falsy
console.log(f('AVAVA'))        // falsy
console.log(f('OOO'))          // falsy
console.log(f('ununununu'))    // truthy
console.log(f('nunwmwnun'))    // falsy
console.log(f('nun unun'))     // falsy
console.log(f('nunwmw'))       // falsy
console.log(f('nnuunnuunnuu')) // falsy
console.log(f('nwnwnwnwn'))    // falsy
console.log(f('m'))            // falsy

Japt, 28 bytes
`wmq¿n`pw ò øU¯2)«(U+g1)rU¯2

Test it online!
Explanation
`wmq¿n` pw ò øU¯  2)«  (U+ g1)rU¯  2
"wmqbun"pw ò øUs0,2)&&!(U+Ug1)rUs0,2
                                       Implicit: U = input string
"wmqbun"                               Take this string.      "wmqbun"
        pw                             Append its reverse.    "wmqbunnubqmw"
           ò                           Form into groups of 2. ["wm","qb","un","nu","nq","mw"]
             ø     )                   Check whether this contains
              Us0,2                      the first two chars of U.
                        U+             Take U and append
                       (  Ug1)           the second char of U.
                              r        Remove all copies of
                               Us0,2     the first two chars of U.
                                       This returns "" iff U has the pattern "xyxyxyx".
                      !                Take the logical NOT: true iff the result is "".
                    &&                 Return whether both of these conditions are true.
                                       Implicit: output result of last expression

Okay not so related but is the TIO version of Japt outdated? If so, should it be updated?

@ASCII-only It is outdated, but I've made a bunch of breaking changes since it was updated (most of them unintentional and still broken :P) so I'm going to hold off on requesting an update for the moment...

oh no Dennis already pulled (so sorry) also D: why do you still have breaking changes pls fix immediately

Javascript, 58 bytes
s=>/^((nu)+n|(un)+u|(mw)+m|(wm)+w|(bq)+b|(qb)+q)$/.test(s)

Tests string for all possible cartwheel strings. Port of this Java answer

C (gcc), 91 90 bytes
Fixed to support strings longer than 255 bytes, which also saves a byte.
f(i){char*s=i,*p=strchr("nunmwmbqb",*s);for(i=0;p&&*s;p=p[i++%2]^*s++?0:p);i=i^1&&i&1&&p;}

Try it online!

Japt, 20 bytes
Êu *`q¿nwm`pÔò d@¥îX

Try it
Êu *`...`pÔò d@¥îX     :Implicit input of string U
Ê                      :Length
 u                     :Mod 2
   *                   :Times
    `...`              :  Compressed string "wbunwm"
         p             :  Append
          Ô            :    Reverse
           ò           :  Partitions of length 2
             d         :  Any true
              @        :  When passed through the following function as X
               ¥       :    Test U for equality with
                îX     :    X repeated and sliced to length of U


text:
Be My Navigator
Oh no, I am lost on the way to finding the great treasures of Marakov! And all I have are these useless instructions that look like S10R10D30... I have no idea what they mean! Can you help me?
Challenge
Given directions consisting of N E S W U D L R 1 2 3 4 5 6 7 8 9 0, output how far I will be from where I started when I follow those directions (i.e. Euclidean Distance).
N E S W refer to me turning North, East, South, and West;
U D L R refer to me turning Up, Down, Left, and Right (So NR is the same as E, and so is SL; SLL is the same as N). Up means keep going forward; Down means turn around.
After each letter direction will be a number, which is how far I will go in that direction. N10E20 means go North 10 units, then turn East, and go East 20 units.
Input Details

Input will always start with one of NESW (so blank input need not be accounted for).
Two letter instructions in a row are allowed. NE should be interpreted, "Turn North, then immediately turn East". It's the same as just E. SLL is "Turn South, then immediately turn Left twice". It's the same as N.
All numbers will be integers (note how . isn't in the character set)
Input will only consist of NESWUDLR1234567890 (If it needs something else, like '\0' in C; or if your language's input functions has a trailing newline, or something, that's fine.)

Output

The norm.
If using a function, should output a numeric datatype or a string.
Must be accurate to 3 decimal places.

Test Cases

N10: 10
N10E10: 14.1421
N10S10: 0
NSEWUDLR10: 10
N100RR20E300D40L12: 268.7452
ERR10LL20UN30D100: 70.71067

The unimaginative Python program I used to make these.
Winning
This is codegolf, so lowest bytes after a week wins!

@AdmBorkBork Right. Lemme edit.

Related

@AdmBorkBork Also this, but all are slightly different.

Can we assume the input consists only of NESWUDLR1234567890?

@darrylyeo Sure, let me edit.

I thought Logo would be a cute language to submit this in, with the following search and replace pairs: N → seth 0 fd , E → seth 90 fd , S → seth 180 fd , W → seth 270 fd , U → fd , D → fd -, L → lt 90 fd , R → rt 90 fd ; then split, run and print sqrt (xcor ^ 2 + ycor ^ 2) to get the normal. Alas, Logo has no search and replace string operations!

@YiminRong Perhaps Python search and replace + this Python logo interp (if ext. libraries are allowed in ppcg)? Or any other comparable language!

(Go)Ruby, 111 bytes
x=0
c=1,1i,-1,-1i
gs.sc(/(\w)(\d*)/){|o,a|x+=c.ro!('URDL'.ix(o)||'NESW'.ix(o)+c.ix(1)).fs*a.toi}
p Mh::hy *x.rc

Try it online!
Takes input on STDIN, outputs it on STDOUT.
Basically, this approach uses complex numbers to store the current position, as well as a stack (c), containing offsets for each direction. If a direction is in URDL, the stack is rotated by the index of the direction in that string; if the direction is in NESW, it's rotated by the index of the direction in that string, plus the index of 1 in the stack. This transforms a rotation relative to the current position into a rotation relative to the position of 1. In any event, the top of the stack is multiplied by the number of steps in the direction and added to the current position.

What's "(Go)Ruby"?

@Carcigenicate It's Ruby, where the interpreter has been compiled with a special flag that makes it more suitable for golfing. Among other changes, it allows you to abbreviate method names, and changes the behavior of certain built-ins. If you visit my TiO link, you'll see the code in the header, which is the majority of changes that are made.

Python 3, 137 bytes
v=n=0
d=1
for i in input()+'U':x="NUERSDW0123456789".find(i);c=x<7;v+=d*n*c;n=[n*10+x-7,0][c];d=[d,d**(x%2)*1j**(~-x/2)][c]
print(abs(v))

Try it online!
-9 bytes thanks to Jonathan Allan

You can save six bytes with the else clause: else:v+=d*n;n=0;h='NUERSDW'.find(i);d=d**(h%2)*1j**(~-h/2)- note that L can be lopped off the end of the find string here because -1%2 equals 7%2 and 1j**(-1) equals 1j**3.

@JonathanAllan Nice tricks! Thanks!

Save another three by inlining the for: for i in input()+'U':x="NUERSDW0123456789".find(i);c=x<7;v+=d*n*c;n=[n*10+x-7,0][c];d=[d,d**(x%2)*1j**(~-x/2)][c]

@JonathanAllan Hey cool, thanks!

Tried my own hand at a Python answer, couldn't get below 179 bytes. Bravo.

@Quelklef Thanks! Did you try using complex numbers? They're very useful for challenges about 2D coordinates because for distance you can just do abs(coords) and you can rotate by multiplying by 1j or -1j.

@HyperNeutrino Yeah, I stole that from you as well as your .find instead of .index trick... Just couldn't make it. I Think the fundamental difference lies in your use of "NUERSDW0123456789".find(i). I have no idea what that does (conceptually).

@Quelklef If x < 7 then it's a direction; otherwise, it's a number. It serves to act as a conditional without an if statement (to avoid needing indentation). It also serves to modify the current number of the instruction and to give the index of the command.

@HyperNeutrino Ah, it's not as complicated as I though. I think we went for similar approaces (I, too, had a negative/positive * complex/non-complex * scalar) but you just golfed better =]

JavaScript (ES6), 148 142 140 138 137 134 bytes
s=>s.replace(/\d+|./g,_=>~(i='NESW'.search(_))?d=i:~(i='URDL'.search(_))?d+=i:a[d&3]+=+_,a=[0,0,0,0])&&Math.hypot(a[1]-a[3],a[0]-a[2])

f=

s=>s.replace(/\d+|./g,_=>~(i='NESW'.search(_))?d=i:~(i='URDL'.search(_))?d+=i:a[d&3]+=+_,a=[0,0,0,0])&&Math.hypot(a[1]-a[3],a[0]-a[2])

for(test of [
  'N10',
  'N10E10',
  'N10S10',
  'NSEWUDLR10',
  'N100RR20E300D40L12',
  'ERR10LL20UN30D100',
]) console.log(f(test))

-2 bytes: Use .search() instead of .indexOf() (@Shaggy)
-1 byte: Rearrange program to remove enclosing parentheses (@Shaggy)
-3 bytes: Use .replace() instead of .match().map() (@ThePirateBay)

We're getting different answers for the second-to-last test.

@Quelklef Fixed.

Can you save a couple of bytes using search instead of indexOf?

I think you can also save a byte by moving a into the map, replacing the , before Math with && and removing the enclosing parentheses.

@Shaggy Awesome, thanks!

You can save 3 bytes by replacing match(...).map(...) with replace.

@ThePirateBay Nice one, thanks!

Perl 5, 149 + 1 (-p) = 150 bytes
while(s/(\D+)(\d+)//){$p=/N/?0:/E/?1:/S/?2:/W/?3:/L/?$p-1:/R/?$p+1:/D/?$p+2:$p for split//,$1;$m[$p%4]+=$2}$_=sqrt(($m[0]-$m[2])**2+($m[1]-$m[3])**2)

Try it online!
Explained:
# Each direction is assigned a number:
#
#     0     North
#     1     East
#     2     South
#     3     West
#
# Variables:
#     $p     present direction
#     @m     total movement in each direction
# Inside loop:
#     $1     a set of direction instructions
#     $2     distance

while(s/(\D+)(\d+)//)    # Remove and preserve the first direction set and distance
   for split//,$1        # Loop through individual letters to set new direction
      $p=/N/?0:          # North
         /E/?1:          # South
         /S/?2:          # East
         /W/?3:          # West
         /L/?$p-1:       # Turn left
         /R/?$p+1:       # Turn right
         /D/?$p+2:       # Turn around
         $p              # Do not change direction
   $m[$p%4]+=$2          # Add the directional movement to previous movements

   $_=sqrt(              # Calculate distance
       ($m[0]-$m[2])**2  # Net North/South movement
      +($m[1]-$m[3])**2  # Net East/West movement
      )

source: Stack Exchange

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/

sort: votes


text:
Find prime gaps
A prime gap is the difference between two consecutive primes. More specifically, if p and q are primes with p <q and p+1, p+2, ..., _q_−1 are not primes, the primes p and q define a gap of n = q_−_p. The gap is said to be started by p, and to have length n.
It is known that arbitrarily large prime gaps exist. That is, given n there exists a prime gap of length n or larger. However, a prime gap of length exactly n may not exist (but a larger one will).
The challenge
Given a positive integer n, output the first prime that starts a gap of length n or larger.
As an example, for input 4 the output should be 7, because 7 and 11 are the first consecutive primes that differ by at least 4 (the previous gaps are 1, from 2 to 3; 2, from 3 to 5; and 2, from 5 to 7). For input 3 the answer should also be 7 (there are no gaps of length 3).
Additional rules

The algorithm should theoretically work for arbitrarily high n. In practice, it is acceptable if the program is limited by time, memory or data-type size.

Input and output can be taken by any reasonable means.

Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.

Shortest code in bytes wins.

Test cases
Input -> Output

1        2
2        3
3        7
4        7
6        23
10       113
16       523
17       523
18       523
30       1327
50       19609
100      370261
200      20831323

Related

By p-q you mean q-p right?

@EriktheOutgolfer Yes; corrected, thanks!

OEIS A104138

OEIS A002386 (Related)

Gaps of most odd lengths will not exist.

@PaŭloEbermann Yes, all gaps except the first are even, because all primes except the first (2) are odd, so they are separated by even lengths

Gaia, 6 bytes
zṅọ⊃∆ṇ

This is extremely inefficient (the 16 test case took over an hour to compute on my machine).
Try it online!
Explanation
The sequence seems to have the property that a(n) <= 2^n.
z       Push 2^input.
 ṅ      Get the first 2^input prime numbers.
  ọ     Get the deltas of the list.
   ⊃∆   Find the index of the first that is greater than or equal to the input.
     ṇ  Push the index-th prime number.

Jelly, 10, 9, 8 10 bytes
Æn_$:ð1#»2

Try it online!
Two bytes saved thanks to @Dennis! (and then added back again due to edge-cases)
Explanation:
Æn          #   The next prime after 'P'
  _$        #   Minus 'P'
    :       #   Divided by 'N'
            #
            # This will give a falsy value unless the distance to the next prime is >= N
            #
     ð      # Treat all of that as a single dyad (fucntion with two arguments).
            # We'll call it D(P, N)
            #
      1#    # Find the first 'P' where D(P, input()) is truthy
        »2  # Return the maximum of that result and 2

Do we know for certain that the result will always be greater-than-or-equal-to the input? (# will count up from the input here) It seems reasonable to assume this but I for one have no idea if it's a valid assumption. EDIT: FYI to fix (if necessary) prefix with 2ð

@JonathanAllan Bertrand's postulate implies that a prime's gap is strictly less than the prime itself.

@Dennis brilliant thank you very much! TMYK...

Mathematica, 30 bytes
2//.x_ /;NextPrime@x-x<#:>x+1&

Try it online!
Mathematica, 35 bytes
(t=2;While[NextPrime@t-t<#,t++];t)&

Try it online!
Mathematica, 77 bytes
Prime@Min@Position[s=Differences@Prime@Range[(r=#)^3+1],#&@@Select[s,#>=r&]]&

Clever clever... you don't even need to make sure both p and q are prime... The first code seems invalid, though, because it only goes up to 65535 unless you explicitly feed the argument MaxIterations.

Also, -2 bytes for the 35-byte version: (For[t=2,NextPrime@t-t<#,t++];t)&

Haskell, 106 102 93 77 73 72 bytes
This generates an infinite list of primes first, then looks for the prime gaps. The prime list was taken from here. It can probably be shortened, but I haven't figured out how yet:)
Thanks to @BruceForte for -4 bytes and @Zgrab for -1 byte!
f n=[x|(y,x)<-zip=<<tail$[n|n<-[2..],all((>0).rem n)[2..n-1]],y-x>=n]!!0

Try it online!

Of course there is some monad magic, thanks :)

zip=<<tail$[...] saves a byte.

"This generates an infinite list of primes first, then ..." : well, then should never happen ? (ie, it will only happen after an infinitely long time, the time to "first generate" procedurally an infinite list of primes)

Haskell uses lazy evaluation, so only as many entries of that list are generated as are actually used. So those primes are generated up to the point where we actually find the points. If you try it you'll see that for any n it will stop after a finite amount of time :) (Haskell is not a procedural, but a functional language with lazy evaluation.)

PS: I highly recommend learning Haskell, as it has a lot of concepts that are just no applicable in the more (up to known) widely known procedural or imperative languages!

@flawr: I guessed it was something like it (like pipelining in unix), but I was "tongue-in-cheek"ly pointing out that the wording "generate ... first, then" is not 100% correct ^^ just change "then" to "while it" ? )

Well it is an infinite list, by definition it does not have an end. What I described is just what is happening under the hood in the usual interpreters, but that is not specified as part of the language so you cannot tell that!

Pyth - 14 bytes
It filters from [1, inf), filtering by primality(P_) and that the next prime filtered from (n, inf), has a different >= to the input.
f&P_T<tQ-fP_Yh

Test Suite.

PowerShell, 97 96 91 bytes
param($n)for($a=$b=2){for(;'1'*++$b-match'^(?!(..+)\1+$)..'){if($b-$a-ge$n){$a;exit}$a=$b}}

Try it online!
Takes input $n, sets $a and $b equal to 2, then enters an infinite for loop. Inside, we loop up on $b until we get to the next prime. Then we check if $b-$a (i.e., the gap) is -greaterthanorequal to $n. If it is, we output $a and exit. Otherwise we set $a to be $b and increment $b and start our next search.
Warning: This is slow for large input. In fact, it can't complete the 50 or higher tests within the 60s timeout on TIO. Oh well.

Husk, 13 11 10 bytes
´ȯ!V≥⁰Ẋ-İp

Try it online!
´       İp  -- with the primes
 ȯ!         -- get the value at position
      Ẋ-    -- where the difference of the current and next prime
   V≥⁰      -- is greater or equal than the input N

Mathematica, 39 bytes
(For[i=2;p=NextPrime,i+#>p@i,i=p@i];i)&
(* or *)
(For[i=1;p=Prime,p@i+++#>p@i,];p[i-1])&

33 byte version (not valid because it only goes up to the 65535th prime)
p=NextPrime;2//.i_/;p@i-i<#:>p@i&

Python 2, 96 88 bytes
- 8 bytes Thanks to @Maltysen
n,p,r=input(),3,[2]
while p-r[-1]<n:r+=[p]*all(p%i for i in range(2,p));p+=1
print r[-1]

Try it online!

saved a bunch of bytes: https://repl.it/JwBe

Perl 6, 63 bytes
->\d{(grep &is-prime,^∞).rotor(2=>-1).first({-d>=[-] $_})[0]}

Try it online!

R + gmp, 55 bytes
Makes use of the nextprime function from the gmp library
s=2;n=scan();while((x=gmp::nextprime(s))-s<n)s=x;cat(s)

You need to add cat(s) at the end. Implicit printing doesn't work in full programs.

Mathematica, 37 bytes
gNestWhile[p=NextPrime,2,p@#-#<g&]

Function with first argument g. Starting with 2, applies the function p=NextPrime repeatedly as long as p@#-#<g& gives True (the gap between the current prime and the next prime is less than g).

C = 141 109 bytes ; C++, D = 141 bytes ; C#, Java = 143 bytes
WARNING : LOW PERFORMANCE ALGORITHM
This code was not able to calculate the prime gap for g(200) within 10 minutes. For g(100), it needed 10 seconds ( C++ version )
C++ and D version :
int p(int d){for(int i=2;i<=d/2;++i){if(!(d%i))return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(!p(n));}return f;}

C# and Java version :
int p(int d){for(int i=2;i<=d/2;++i){if(d%i==0)return 0;}return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do{++n;}while(p(n)==0);}return f;}

C version, -32 bytes thanks to ceilingcat  :
i;p(d){for(i=2;d/2/i;)if(!(d%i++))return 0;return 1;}f;n;g(d){for(f=2,n=3;n-f<d;)for(f=n;!p(++n););return f;}

Differences between the C#/Java and C/C++/D version : !p(n) <==> p(n)==0

Can reverse return 0; return 1 and remove the ! before p(++n)

d%i==0 and !(d%i) can be d%i<0. Also, using D's template system the solution in D can be: T p(T)(T d){for(T i=2;i<=d/2;++i)if(d%i<1)return 0;return 1;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;do++n;while(!p(n));}return f;. (The removal of braces after the for and the do might apply to C++ as well)

I posted the separate D version, which utilizes D specific tricks that can't be found in C/C++/C#/Java.

int p(int d){for(int i=2;i<=d/2;++i)if(!(d%i))return 0;return 1;}int g(int d){int f=2,n=3;while(n-f<d){f=n;do++n;while(!p(n));}return f;} <- that should work for the C++ version

Ruby, 61 bytes
->g{*r,f=2,3;f+=1while r.find{|n|f%n<1}||r<<f&&g>f-z=r[-2];z}

Try it online!

D, 127 125 122 bytes
WARNING: LOW PERFORMANCE ALGORITHM!!
T p(T)(T d){T r;for(T i=2;i<=d/2;)r=d%i++<1||r;return r;}T g(T)(T d){T f=2,n=3;while(n-f<d){f=n;while(p(++n)){}}return f;}

Try it online!
How?
HatsuPointerKun again, but I'll do the D specific sorcery.

Template system can infer types T p(T)(T d), and is shorter than C++
r=d%i++<1||r, D specific shenanigans, might work in C/C++, but I don't know.
p(++n), same as above, not sure if it works in C/C++
while(p(++n)){}, here one sees why D is bad at golfing, one can't use ; as an empty statement.

Perl 6, 41 37 bytes
{+(1...(^$_+*)>>.is-prime eqv!<<^$_)}

Try it online!
Explanation
{                                   }  # Block taking n as $_
   1...   # Sequence 1,2,... until
       (^$_+*)  # Range [i,i+n)
              >>.is-prime  # is-prime for each
                          eqv!<<^$_  # Equals (True,False,False,False,...)?
 +(                                )  # Length of sequence

Haskell, 64 bytes
f n=until(\p->and[any((<1).mod k)[2..k-1]|k<-[p+1..p+n-1]])(+1)2

Try it online!
Count up from 2 looking for a p such that [p+1..p+n-1] are all composite.
p itself will always be prime: otherwise [p..p+n-1] is a larger prime gap and we'd have returned p-1.

QBIC, 28 bytes
{~µs||~s-r>=:|_Xr\r=s]]s=s+1

Explanation
{         DO
~µs||     IF s is prime THEN (note, s starts as 3)
~s-r>=:   IF the gap between s (current prime) and r (prev prime) is big enough
|_Xr      THEN QUIT, printing prev prime r
\r=s      ELSE (gap too small, but s is prime), set r to prime s
]]        END IF x2, leaving us in the WHILE
s=s+1     increment s, retest for primality ...

05AB1E, 9 bytes
∞<ØD¥I@Ïн

Try it online or verify all test cases. (Test Suite doesn't contain the last two test cases, because TIO times out for those.)
Since the other question is closed as a dupe of this one, I'm posting my answer here as well.
Explanation:
∞           # Get an infinite list in the range [1, ...]
 <          # Decrease it by one to make it in the range [0, ...]
  Ø         # Get for each the (0-indexed) n'th prime: [2,3,5,7,11,...]
   D        # Duplicate this list of primes
    ¥       # Get all deltas (difference between each pair): [1,2,2,4,2,...]
     I@     # Check for each if they are larger than or equal to the input
            #  i.e. 4 → [0,0,0,1,0,1,0,1,1,0,...]
       Ï    # Only keep the truthy values of the prime-list
            #  → [23,31,47,53,61,...]
        н   # And keep only the first item (which is output implicitly)
            #  → 23

Java 8, 99 92 bytes
n->{int a=2,b=3,f,k;for(;b-a<n;)for(f=0,a=b;f<2;)for(f=++b,k=2;k<f;)f=f%k++<1?0:f;return a;}

Try it online. (Largest test case is excluded, because it times out in TIO.)
Explanation:
n->{               // Method with integer as both parameter and return-type
  int a=2,b=3,     //  Prime-pair `a,b`, starting at 2,3
      f,           //  Prime-checker flag `f`, starting uninitialized
      k;           //  Temp integer, starting uninitialized
  for(;b-a         //  Loop as long as the difference between the current pair of primes
          <n;)     //  is smaller than the input
    for(f=0,       //   (Re)set the prime-checker flag to 0
        a=b;       //   Replace `a` with `b`, since we're about to search for the next prime-pair
        f<2;)      //   Inner loop as long as the prime-checker flag is still 0 (or 1)
                   //   (which means the new `b` is not a prime)
      for(f=++b,   //    Increase `b` by 1 first, and set this value to the prime-checker flag
          k=2;     //    Set `k` to 2
          k<f;)    //    Inner loop as long as `k` is still smaller than the prime-checker flag
        f=         //     Change the prime-checker flag to:
          f%k++<1? //      If the prime-checker flag is divisible by `k`
           0       //       Set the prime-checker flag to 0
          :        //      Else:
           f;      //       Leave it unchanged
                   //    (If any integer `k` in the range [2, `b`) can evenly divide `b`,
                   //     the prime-checker flag becomes 0 and the loop stops)
  return a;}       //  And finally after all the nested loops, return `a` as result

Tidy, 33 bytes
{x:({v:⊟v<=-x}↦primes+2)@0@0}

Try it online!
Or, 28 chars/34 bytes: {x:({v:⊟v≤-x}↦primes+2)@0@0}
I'll explain this using an equivvalent, ASCII equivalent:
{x:({v:(-)over v<=-x}from primes+2)@0@0}
{x:                                    }    lambda w/ parameter `x`
                          primes+2          overlapping pairs of primes
                                            [[2, 3], [3, 5], [5, 7], ...]
    {v:             }from                   select prime pairs `v = [a, b]`...
       (-)over v                            ...where `a` - `b`...
                <=-x                        is <= `x`
   (                              )@0@0     select the first element of the first pair

APL(NARS), 36 char, 72 bytes
∇r←h w;k
r←2
→0×⍳w≤r-⍨k←1πr⋄r←k⋄→2
∇

1π is the function "next prime"; test:
  h¨1 2 3 4 6 10 16 17 18 30 50 100 200
2 3 7 7 23 113 523 523 523 1327 19609 370261 20831323

Japt, 14 bytes
@§XnÈj}aX+j}a2

Try it or run all test cases (except 200 - seriously, don't even try it! If you want to verify that 200 returns the correct result, you can increase the starting value of 2 at the end to something closer to the expected output.)
@§XnÈj}aX+j}a2     :Implicit input of integer U
@                  :Function taking an integer X as argument
 §                 :  Is U <= ...
  Xn               :  Subtract X from
    È              :    Function taking an integer as input
     j             :      Is prime?
      }            :    End function
       a           :    Get the first integer that returns true when passed through that function starting at
        X+j        :      X plus is X prime
           }       :End function
            a2     :Get the first integer that returns true when passed through that function starting at 2

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/


text:
Count arrays of periods
The period of a string is the shortest non-zero shift so that the string matches itself, ignoring any parts that overhang. So for example, abcabcab has period 3. By convention we say that if there is no such shift then a string has period equal to its length. So the period of abcde is 5 and the period of a is 1.
In more formal terms, the period of a string S is the minimum i > 0 so that S[1,n-i] == S[i+1,n] (indexing from 1).
For a given string S of power of two length, we will compute the period of all its prefixes of power of two length.  For example, consider S = abcabcab.  The periods we will compute are:
'a', 1
'ab', 2
'abca', 3
'abcabcab', 3

We will in fact just output the array of periods, that is [1, 2, 3, 3].
For a given  positive power of two n, consider all possible binary strings S.   Recall that a binary string is simply a string of 1s and 0s so there are exactly 2^n such strings (that is 2 to the power n). For each one we can compute this array of periods.

The challenge is to write code that takes n (a power of two)  as input and computes how many distinct such arrays there are.

The answers for n = 1, 2, 4, 8, 16, 32, 64, 128 are:
1, 2, 6, 32, 320, 6025, 216854, 15128807

The full set of distinct period arrays for n = 4 is:
1, 1, 1
1, 1, 3
1, 1, 4
1, 2, 2
1, 2, 3
1, 2, 4

Score
I will run your code on my computer running Ubuntu for 10 minutes. Your score is the largest n for which your code terminates in that time. In the case of a tie, the answer that completes the joint largest n fastest wins. In  the case that there is a tie within 1 second on timings, the first answer posted wins.
Languages and libraries
You can use any available language and libraries you like. Please include a full explanation for how to run/compile your code in Linux if at all possible.`
Your code should actually compute the answers and not, for example, just output precomputed values.
Leading entries

2 minutes and 21 seconds for n = 128 in C# by Peter Taylor
9 seconds for n = 32 in Rust by isaacg

This made my head hurt.

The challenge is interesting, but I still cannot see objective criterium you're using to distinguish between "precomputed" and "actually computed" answers. If you, for example, cannot understand how my code works, but it gives correct answers for huge n, would you accept it? It is not well defined where is the border between hardcoding and actual computing.

A123903?

@H.PWiz I doubt it :)  The answer for n=32 will make that clear I suspect.

@Lembik I hope not, as that would undermine your challenge severely

@ThePirateBay https://codegolf.meta.stackexchange.com/a/1063/9206 . It's a standard rule.

When I saw the title of this challenge, I thought it would be about arrays like this: [".",".","...."]

@Lembik Huh, it's 6025? Strange

https://gist.github.com/somebody1234/fb6494f3a3f350a4ffdc8c8ef213a4c2

I don't understand this challenge quite yet. Could you show how the period of abcabcab is 3?

@Cowsquack All but the first three letters of the string is abcab. All but the last 3 letters is abcab. These match, and removing a smaller number of letters does not match.

C#, n=128 in about 2:40
using System;
using System.Collections.Generic;
using System.Linq;

namespace Sandbox
{
    class PPCG137436
    {
        public static void Main(string[] args)
        {
            if (args.Length == 0) args = new string[] { "1", "2", "4", "8", "16", "32", "64", "128" };

            foreach (string arg in args)
            {
                Console.WriteLine(Count(new int[(int)(0.5 + Math.Log(int.Parse(arg)) / Math.Log(2))], 0));
            }
        }

        static int Count(int[] periods, int idx)
        {
            if (idx == periods.Length)
            {
                //Console.WriteLine(string.Join(", ", periods));
                return 1;
            }

            int count = 0;
            int p = idx == 0 ? 1 : periods[idx - 1];
            for (int q = p; q <= 1 << (idx + 1); q++)
            {
                periods[idx] = q;
                if (q == p || q > 1 << idx || p + q - Gcd(p, q) > 1 << idx && UnificationPasses(periods, idx, q)) count += Count(periods, idx + 1);
            }

            return count;
        }

        private static int Gcd(int a, int b)
        {
            while (a > 0) { int tmp = a; a = b % a; b = tmp; }
            return b;
        }

        private static bool UnificationPasses(int[] periods, int idx, int q)
        {
            UnionSet union = new UnionSet(1 << idx);
            for (int i = 0; i <= idx; i++)
            {
                for (int j = 0; j + periods[i] < Math.Min(2 << i, 1 << idx); j++) union.Unify(j, j + periods[i]);
            }

            IDictionary<int, long> rev = new Dictionary<int, long>();
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] = 0L;
            for (int k = 0; k < 1 << idx; k++) rev[union.Find(k)] |= 1L << k;

            long zeroes = rev[union.Find(0)]; // wlog the value at position 0 is 0

            ISet<int> onesIndex = new HashSet<int>();

            // This can be seen as the special case of the next loop where j == -1.
            for (int i = 0; i < idx; i++)
            {
                if (periods[i] == 2 << i) onesIndex.Add((2 << i) - 1);
            }
            for (int j = 0; j < idx - 1 && periods[j] == 2 << j; j++)
            {
                for (int i = j + 1; i < idx; i++)
                {
                    if (periods[i] == 2 << i)
                    {
                        for (int k = (1 << j) + 1; k <= 2 << j; k++) onesIndex.Add((2 << i) - k);
                    }
                }
            }

            for (int i = 1; i < idx; i++)
            {
                if (periods[i] == 1) continue;

                int d = (2 << i) - periods[i];
                long dmask = (1L << d) - 1;
                if (((zeroes >> 1) & (zeroes >> periods[i]) & dmask) == dmask) onesIndex.Add(periods[i] - 1);
            }

            long ones = 0L;
            foreach (var key in onesIndex) ones |= rev[union.Find(key)];

            if ((zeroes & ones) != 0) return false; // Definite contradiction!

            rev.Remove(union.Find(0));
            foreach (var key in onesIndex) rev.Remove(key);

            long[] masks = System.Linq.Enumerable.ToArray(rev.Values);

            int numFilteredMasks = 0;
            long set = 0;
            long M = 0;
            for (int i = 1; i <= idx; i++)
            {
                if (periods[i - 1] == 1) continue;

                // Sort the relevant masks to the start
                if (i == idx) numFilteredMasks = masks.Length; // Minor optimisation: skip the filter because we know we need all the masks
                long filter = (1L << (1 << i)) - 1;
                for (int j = numFilteredMasks; j < masks.Length; j++)
                {
                    if ((masks[j] & filter) != 0)
                    {
                        var tmp = masks[j];
                        masks[j] = masks[numFilteredMasks];
                        masks[numFilteredMasks++] = tmp;
                    }
                }

                // Search for a successful assignment, using the information from the previous search to skip a few initial values in this one.
                set |= (1L << numFilteredMasks) - 1 - M;
                M = (1L << numFilteredMasks) - 1;
                while (true)
                {
                    if (TestAssignment(periods, i, ones, masks, set)) break;
                    if (set == 0) return false; // No suitable assignment found

                    // Gosper's hack with variant to reduce the number of bits on overflow
                    long c = set & -set;
                    long r = set + c;
                    set = (((r ^ set) >> 2) / c) | (r & M);
                }
            }

            return true;
        }

        private static bool TestAssignment(int[] periods, int idx, long ones, long[] masks, long assignment)
        {
            for (int j = 0; j < masks.Length; j++, assignment >>= 1) ones |= masks[j] & -(assignment & 1);
            for (int i = idx - 1; i > 0; i--) // i == 0 is already handled in the unification process.
            {
                if (Period(ones, 2 << i, periods[i - 1]) < periods[i]) return false;
            }

            return true;
        }

        private static int Period(long arr, int n, int min)
        {
            for (int p = min; p <= n; p++)
            {
                // If the bottom n bits have period p then the bottom (n-p) bits equal the bottom (n-p) bits of the integer shifted right p
                long mask = (1L << (n - p)) - 1L;
                if ((arr & mask) == ((arr >> p) & mask)) return p;
            }

            throw new Exception("Unreachable");
        }

        class UnionSet
        {
            private int[] _Lookup;

            public UnionSet(int size)
            {
                _Lookup = new int[size];
                for (int k = 0; k < size; k++) _Lookup[k] = k;
            }

            public int Find(int key)
            {
                var l = _Lookup[key];
                if (l != key) _Lookup[key] = l = Find(l);
                return l;
            }

            public void Unify(int key1, int key2)
            {
                int root1 = Find(key1);
                int root2 = Find(key2);

                if (root1 < root2) _Lookup[root2] = root1;
                else _Lookup[root1] = root2;
            }
        }
    }
}

Extending to n=256 would require switching to BigInteger for the masks, which probably kills the performance too much for n=128 to pass without new ideas, let alone n=256.
Under Linux, compile with mono-csc and execute with mono.
Basic explanation
I'm not going to do a line-by-line dissection, just an overview of the concepts.
As a rule of thumb, I'm happy to iterate through on the order of 250 elements in a brute-force combinatoric program. To get to n=128 it is therefore necessary to use an approach which doesn't analyse every bitstring. So rather than working forwards from bit strings to period sequences, I work backwards: given a period sequence, is there a bitstring which realises it? For n=2x there's an easy upper bound of 2x(x+1)/2 period sequences (vs 22x bitstrings).
Some of the arguments use the string periodicity lemma:

Let p and q be two periods of a string of length n. If p + q ≤ n + gcd(p, q) then gcd(p, q) is also a period of the string.

Wlog I will assume that all of the bitstrings under consideration start with 0.
Given a period sequence [p1 p2 ... pk] where pi is the period of the prefix of length 2i (p0 = 1 always), there are some easy observations about possible values of pk+1:

pk+1 ≥ pk since a period of a string S is also a period of any prefix of S.
pk+1 = pk is always a possible extension: just repeat the same primitive string for twice as many characters.
2k < pk+1 ≤ 2k+1 is always a possible extension. It suffices to show this for pk+1 = 2k+1 because an aperiodic string of length L can be extended to an aperiodic string of length L+1 by appending any letter which isn't its first letter.
Take a string Sx of length 2k whose period is pk and consider the string SxyS of length 2k+1. Clearly SxyS has a period 2k+1. Suppose its period q is smaller.
Then 2k+1 + q ≤ 2k+1+1 ≤ 2k+1 + gcd(2k+1, q) so by the periodicity lemma gcd(2k+1, q) is also a period of SxyS, and since the greatest divisor is less than or equal to its arguments and q is the smallest period, we require q to be a proper factor of 2k+1. Since its quotient cannot be 2, we have q ≤ (2k+1)/3.
Now, since q ≤ 2k is a period of SxyS it must be a period of Sx. But the period of Sx is pk. We have two cases:

gcd(pk, q) = pk, or equivalently pk divides exactly into q.
pk + q > 2k + gcd(pk, q) so that the periodicity lemma doesn't force a smaller period.

Consider first the second case. pk > 2k + gcd(pk, q) - q ≥ 2k+1 - q ≥ 2k+1 - (2k+1)/3 ≥ 2q, contradicting the definition of pk as the period of Sx. Therefore we are forced into the conclusion that pk is a factor of q.
But since q is a period of Sx and pk is the period of Sx, the prefix of length q is just q/pk copies of the prefix of length pk, so we see that pk is also a period of SxyS.
Therefore the period of SxyS is either pk or 2k+1. But we have two options for y! At most one choice of y will give period pk, so at least one will give period 2k+1. QED.
The periodicity lemma allows us to reject some of the remaining possible extensions.
Any extension which hasn't passed a quick-accept or a quick-reject test needs to be tested constructively.

The construction of a bitstring given a period sequence is essentially a satisifiability problem, but it has a lot of structure. There are 2k - pk simple equality constraints implied by each prefix period, so I use a union set data structure to combine bits into independent clusters. This was enough to tackle n=64, but for n=128 it was necessary to go further. I employ two useful lines of argument:

If the prefix of length M is 01M-1 and the prefix of length L > M has period L then the prefix of length L must end in 1M. This is most powerful precisely in the cases which would otherwise have most independent clusters, which is convenient.
If the prefix of length M is 0M and the prefix of length L > M has period L - d with d < M and ends in 0d then it must in fact end in 10d. This is most powerful at the opposite extreme, when the period sequence starts with a lot of ones.

If we don't get an immediate contradiction by forcing the cluster with the first bit (assumed to be zero) to be one then we brute force (with some micro-optimisations) over the possible values for the unforced clusters. Note that the order is in descending number of ones because if the ith bit is a one then the period cannot be i and we want to avoid periods which are shorter than the ones which are already enforced by the clustering. Going down increases the chances of finding a valid assignment early.

This is a really great achievement!  I am very impressed.

@Lembik, I've simplified and optimised the code and reduced runtime for n=128 by about a third.

I would love to know what algorithm you have designed for this. Your code has remarkably little logic in it and must be doing something very clever.

Rust, 32, 10s 11s 29s on my laptop
Call it with the bitsize as the command line argument.
Clever techniques: represent bitstrings directly as numbers, use bittwiddling to check for cycles. Only search the first half of the bitstrings, those starting with 0, because the array of periods of a bitstring and its inverse (0s swapped for 1s) are identical. If every possibility for the final position has already occured, I don't search it.
More clever stuff:
To deduplicate each block (strings where the first half of the bits are the same) I use a bitvector, which is much faster than a hashset, since the final cycle lengths don't need hashing.
Also, I skip the first steps of the cycle checking, because I know that the final cycle can't be shorter than the second-to-last cycle.
After lots of profiling, I can now tell that almost all of the time is being used productively, so algorithmic improvements will be required to improve from here, I think. I also switched to 32 bit integers to save a little more time.
//extern crate cpuprofiler;
//use cpuprofiler::PROFILER;

extern crate bit_vec;
use bit_vec::BitVec;

use std::collections::HashSet;

fn cycle_len(num: u32, mask: u32, skip_steps: usize) -> usize {
    let mut left = num >> skip_steps;
    let mut mask = mask >> skip_steps;
    let mut steps = skip_steps;
    loop {
        left >>= 1;
        if left == (num & mask) {
            return steps;
        }
        mask >>= 1;
        steps += 1;
    }
}

fn all_cycles(size_log: usize) -> HashSet<Vec<usize>> {
    let mut set = HashSet::new();
    if size_log == 0 {
        set.insert(vec![]);
        return set;
    } else if size_log == 1 {
        set.insert(vec![0]);
        set.insert(vec![1]);
        return set;
    }
    let size: usize = 1 << size_log;
    let half_size: usize = 1 << size_log - 1;
    let shift_and_mask: Vec<(usize, u32)> = (1..size_log)
        .map(|subsize_log| {
            let subsize = 1 << subsize_log;
            (size - subsize, (1 << (subsize - 1)) - 1)
        })
        .collect();
    let size_mask = (1 << (size - 1)) - 1;
    for block in 0..(1 << (half_size - 1)) as u32 {
        let start: u32 = block << half_size;
        if block % 1024 == 0 {
            eprintln!(
                "{} ({:.2}%): {}",
                start,
                start as f64 / (1u64 << size - 1) as f64 * 100f64,
                set.len()
            );
        }
        let leader = {
            let mut cycles = Vec::new();
            for &(shift, mask) in &shift_and_mask {
                let subnum = start >> shift;
                cycles.push(cycle_len(subnum, mask, 0));
            }
            cycles
        };
        let &end = leader.last().unwrap();
        if (end..size).all(|count| {
            let mut new = leader.clone();
            new.push(count);
            set.contains(&new)
        })
        {
            continue;
        }
        let mut subset = BitVec::from_elem(size, false);
        for num in start..start + (1 << half_size) {
            subset.set(cycle_len(num, size_mask, end), true);
        }
        for (unique_cycle_len, _) in subset.into_iter().enumerate().filter(|x| x.1) {
            let mut new_l = leader.clone();
            new_l.push(unique_cycle_len);
            set.insert(new_l);
        }
    }
    set
}

fn main() {
    let size: f32 = std::env::args().nth(1).unwrap().parse().unwrap();
    let size_log = size.log2() as usize;
    //PROFILER.lock().unwrap().start("./my-prof.profile").unwrap();
    let cycles = all_cycles(size_log);
    //PROFILER.lock().unwrap().stop().unwrap();
    println!(
        "Number of distinct arrays of periods of bitstrings of length {} is {}",
        1 << size_log,
        cycles.len()
    );
}

Put bit-vec = "0.4.4" in your Cargo.toml
If you'd like to run this, clone this: github.com/isaacg1/cycle then Cargo build --release to build, then Cargo run --release 32 to run.

Looks like eprintln needs a version of rust after 0.16.0.  It works if I change it to println.

This answer is very impressive. time gives it 27 user seconds on my laptop.

@Lembik why are you in such an old version of rust? Rust 1.0 came out years ago.

Typo :) I meant 1.16.0. https://blog.rust-lang.org/2017/03/16/Rust-1.16.html

For the rust newbies, would you mind spelling out exactly how to compile your code using cargo?

9 seconds! Now I am wondering how long it will take for n = 64 :)

@Lembik Thanks! Clone this: https://github.com/isaacg1/cycle then Cargo build --release to build, then Cargo run --release 32 to run.

Rust, 16
use std::collections::HashSet;
use std::io;

fn main() {
	print!("Enter a pow of two:");
	let mut input_text = String::new();
    io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");

    let n_as_string = input_text.trim();
	match n_as_string.parse::<usize>() {
		Ok(n) => {
			let log2 = (n as f64).log(2_f64) as usize;
			if n != 1 << log2 {
				panic!("{} is not a power of two", n);
			}
			let count = compute_count_array(log2, n);
			println!("n = {} -> count = {}", n, count);
		}
		Err(_) => { panic!("{} is not a number", n_as_string); }
	}
}

fn compute_count_array(log2:usize, n: usize) -> usize {
	let mut z = HashSet::new();

	let mut s:Vec<bool> = vec!(false; n);
	loop {
		let mut y:Vec<usize> = vec!();
		for j in 0..log2+1 {
			let p = find_period(&s[0..1<<j]);
			y.push(p);
		}
		z.insert(y);
		if !next(&mut s) {
			break;
		}
	}
	z.len()
}

#[inline]
fn find_period(s: &[bool]) -> usize {
	let n=s.len();
	let mut j=1;
	while j<n {
		if s[0..n-j] == s[j..n] {
			return j;
		}
		j+=1;
    }
	n
}

#[inline]
fn next(s:&mut Vec<bool>) -> bool {
	if s[0] {
		s[0] = false;
		for i in 1..s.len() {
			if s[i] {
				s[i] = false;
			} else {
				s[i] = true;
				return true;
			}
		}
		return false
	} else {
		s[0] = true;
	}
	true
}

Try it online!
Compilation: rustc -O <name>.rs
The string is implemented as a Bool vector.

The next function iterate through the combinations ;
The find_period takes a Bool slice and returns the period ;
The compute_count_array does the job for each "power of two" subsequence of each combinations of Bools.

Theoretically, no overflow is expected until 2^n exceeds the u64 maximum value, ie n > 64. This limit could be outreached with an expensive test on s=[true, true, ..., true].
Bad news is:  it returns 317 for n=16, but I don't know why. I don't know either if it will make it in ten minutes for n=32, since the Vec<bool> is not optimized for this kind of computation.
EDIT

I've managed to remove the limit of 64 for n. Now, it won't crash until n is greater than the max usize integer.
I found why the previous code returned 317 for n=32. I was counting sets of periods and not arrays of periods. There were three arrays with the same elements:

[1, 2, 3, 3, 8] -> {1, 2, 3, 8}
[1, 2, 3, 8, 8] -> {1, 2, 3, 8}
[1, 1, 3, 3, 7] -> {1, 3, 7}
[1, 1, 3, 7, 7] -> {1, 3, 7}
[1, 1, 3, 3, 8] -> {1, 3, 8}
[1, 1, 3, 8, 8] -> {1, 3, 8}

Now it works. It is still slow but it works.

Here are all 320 for n = 16 https://bpaste.net/show/3664e25ebc01 .

@Lembik I found the explanation for 317 thanks to your list.

C - 16
It fails on values greater than 16 cuz of overflow.
I have no idea how fast this runs cuz im on a chromebook running it on repl.it.
Just implements the question as it reads, goes through all bit strings, calculates the period arrays, and checks if they have already been counted.
#include "stdio.h"
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int per(int s[], int l) {
  int period = 0;
  while (1) {
    period++;

    bool check = 1;
    int i;
    for (i=0; i<l-period; i++) {
      if (s[i]!=s[i+period]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return period;
    }
  }
}

bool perar(int* s, int l, int* b, int i) {
  int n = 1;
  int j=0;
  while (n<=l) {
    b[i*l+j] = per(s, n);
    n=n<<1;
    j++;
  }

  for (j=0;j<i;j++) {
    int k;
    bool check = 1;
    for(k=0; k<l; k++) {
      if (b[j*l+k] != b[i*l+k]) {
        check = 0;
        break;
      }
    }
    if (check) {
      return 0;
    }
  }
  return 1;
}

int main(int argc, char* argv[]) {
  int n;
  scanf("%d", &n);
  puts("Running...");
  int i;
  int c = 0;
  int* a = malloc(n*sizeof(int));
  int m=pow(2, n);
  int* b = malloc(m*n*sizeof(int));
  for (i=0; i<m; i++) {
    int j;
    for (j=0; j<n; j++) {
      a[j] = (i>>j)&1;
    }
    c+=perar(a, n, b, i);
  }
  printf("Answer: %d\n", c);
  return 0;
}

Just compile it with gcc, etc.

FYI - It was erroring for 16 then when the code was changed so that the two mallocs were malloc(...int*)) and ...** respectively 16 printed Answer: 320 as expected, however 32 printed Answer: 0 (and pretty quickly).

@JonathanAllan fixed the stuff, just made b an int*.

@JonathanAllan the 32 thing is cuz 2**32 overflows the int. Also i'll prolly run out of memory.

@ThePirateBay i made i and m longs, and that just segfaults when i try 32. https://repl.it/JwJl/2 I'm guessing it runs out of memory.

@Maltysen. It seems that it segfaults because you messed something up in allocation/deallocation rather than lack of available memory. I got segfault for n = 8 but after the result is printed, which means that the stack is corrupted. Probably you're somewhere writting beyond allocated memory block(s).

@ThePirateBay does this still segfault for you at 8&16: https://repl.it/JwJl/3

The code takes about 1 second for n = 16 but fails for n = 32.  Also, could you change it so it takes a command line argument please? I need to time the code.

@Lembik You can use <-like shell syntax I suppose?

Haskell
import qualified Data.Set as S
import Data.Bits

period :: Int -> Int -> Int
period num bits = go (bits-2) (div prefix 2) (clearBit prefix $ bits-1)
  where
  prefix = (2^bits-1) .&. num
  go p x y
    | x == y    = p
    | otherwise = go (p-1) (div x 2) (clearBit y p)

allPeriods :: Int ->  [[Int]]
allPeriods n = map periods [0..div(2^n)2-1]
  where
  periods num = map (period num) powers
  powers = takeWhile (<=n) $ iterate (*2) 2

main = readLn >>= print . S.size . S.fromList . allPeriods

Compile with ghc -O2. Try it online!
Runs in less than 0.1sec on my 6 year old laptop hardware for n=16. n=32 takes 99 92min, so I'm factor 9 or 10 off. I've tried caching the periods in a lookup table so I don't have to recalculate them over and over again, but this quickly runs out of memory on my 4GB machine.

Despite being a factor of 10 off, your code is very good looking.

@Lembik. Thanks. I'm just trying an improvement: the above code calculates periods for substrings of length 1, but that's completely unnecessary. Besides not to have to calculate them, it also saves some time when finding unique arrays of periods, because they are all one element shorter.

@Lembik: omitting length 1 substrings saves about 7min for n=32. Still far too long.

There is a fast linear algorithm for computing the period which might help.

Can you really not build a look up table of size 2^16 ? That doesn't seem too big.

@Lembik: yes, Data.IntMap.Strict doesn't need much memory and works as a lookup table, however it has O(log n) lookup and insert time, so it's still too slow (im at 65min, now).

Python 2 (PyPy), 16
import sys
import math
def do(n):
 masks=[]
 for i in range(n):
  masks+=[(1<<((2<<i)-1))-1]
 s=set()
 bits=1<<n
 for i in xrange(1<<bits):
  r=[0,]*n
  for j in range(len(masks)):
   mask=masks[j]
   k,c=i>>bits-(2<<j),1
   d=k>>1
   while k&mask^d:
    d>>=1
    mask>>=1
    c+=1
   r[j]=c
  s|={tuple(r)}
 return len(s)
print do(int(math.log(int(sys.argv[1]),2)))

:| why does 32 have to take so long

I know I can skip half of them but IDK how :/

Your code seems to only output "None" for me. How are you running it? osboxes@osboxes:~/python$ python ascii_user.py 16 None

crap sorry this isn't actually what i run

@Lembik fixed now

[C++], 32, 4 minutes
#include <iostream>
#include <vector>

typedef unsigned int u;
template<typename T, typename U>
u Min(T a, U b) {
    return a < b ? a : b;
}

template<typename T, typename U>
u Max(T a, U b) {
    return a > b ? a : b;
}

u Mask(int n) {
    if (n < 0) n = 0;
    return ~((u)(-1) << n);
}
u MASKS[32];

inline u Rshift(u v, int n) {
    return n < 0 ? v >> (-1*n)
    : n > 0 ? v << n
    : n;
}

int GetNextPeriodId(u pattern, int pattern_width, int prior_id) {
    int period = (prior_id % (pattern_width>>1)) + 1;
    int retval = prior_id * pattern_width;

    for (; period < pattern_width; period+=1) {
        u shift = pattern >> period;
        int remainder = pattern_width-period;
        u mask = MASKS[period];

        for (;remainder >= period && !((pattern ^ shift) & mask);
             shift >>= period, remainder -= period);

        if (remainder > period) continue;
        if (remainder == 0 || !((pattern ^ shift) & MASKS[remainder])) {
            retval += (period-1);
            break;
        }
    }
    if (period == pattern_width) {
        retval += pattern_width-1;
    }
    return retval;
}

int ParseInput(int argc, char** argv) {
    if (argc > 1) {
        switch(atoi(argv[1])) {
            case 1:
                return 1;
            case 2:
                return 2;
            case 4:
                return 4;
            case 8:
                return 8;
            case 16:
                return 16;
            case 32:
                return 32;
            default:
                return 0;
        }
    }
    return 0;
}

void PrintId(u id, int patternWidth) {
    for(;patternWidth > 0; id /= patternWidth, patternWidth >>= 1) {
        std::cout << (id % patternWidth)+1 << ",";
    }
    std::cout << std::endl;
}

int TestAndSet(std::vector<bool>& v, int i) {
    int retval = v[i] ? 0 : 1;
    v[i] = true;
    return retval;
}

std::vector<bool> uniques(1<<15);
int uniqueCount = 0;

void FillUniques(u i, int id, int target_width, int final_width) {
    int half_size = target_width / 2;
    u end = 1u<<(half_size-1);
    u mask = MASKS[half_size];
    u lowers[] = { i, (~i)&mask };
    for (u j = 0ul; j < end; j++) {
        u upper = j << half_size;
        u patterns[] = { (upper|lowers[0]), (upper|lowers[1]) };
        for (int k=0; k < sizeof(patterns)/sizeof(patterns[0]); k+=1) {
            int fid = GetNextPeriodId(patterns[k], target_width, id);
            if (target_width != final_width) {
                FillUniques(patterns[k], fid, target_width*2, final_width);
            } else {
                if (TestAndSet(uniques, fid)) {
                    uniqueCount += 1;
                }
            }
        }
    }
}

int main(int argc, char** argv) {
    for (int i = 0; i < 32; i++) {
        MASKS[i] = Mask(i);
    }
    int target_width = 32; // ParseInput(argc, argv);
    if (!target_width) {
        std::cout << "Usage: " << argv[0] << " [1|2|4|8|16|32]" << std::endl;
        return 0;
    }
    if (target_width == 1) {
        std::cout << 1 << std::endl;
        return 0;
    }
    FillUniques(0, 0, 2, target_width);
    std::cout << uniqueCount << std::endl;
    return 0;
}


text:
When do the lights blink?
Imagine you have two lights. These lights blink on and off at a specific rate:
Light 0: Delay 0ms and then blink every 1000ms
Light 1: Delay 500ms and then blink every 1000ms

Let's simulate these lights for the first 2000ms:
0ms:    Light 0 on
500ms:  Light 1 on
1000ms: Light 0 off
1500ms: Light 1 off
2000ms: Light 0 on

The challenge
Given a list of ordered pairs representing the timing for lights, write a program or function to output the sequence for when they blink.
Input
The input should be in the following format:
TimeToSimulate
Light0Delay,Light0Period
Light1Delay,Light1Period
...

In this format, the example above would be:
2000
0,1000
500,1000

Output
The output should be a series of ordered triples:
Time,LightNum,LightStatus

LightStatus is a truthy value if the light turns on and a falsy value if the light turns off.
The output from the above example would be:
0,0,True
500,1,True
1000,0,False
1500,1,False
2000,0,True

If two lights blink at the same time, the light with the lower number should display first in the output.
Other stuff

The input and output formats aren't strict
Code shouldn't produce any errors
The solution shouldn't rely on race conditions
No standard loopholes
This is code-golf, so shortest solution wins!

Test cases
Input:

2000
0,1000
500,1000

Output:

0,0,True
500,1,True
1000,0,False
1500,1,False
2000,0,True

----

Input:

2
0,1
0,1

Output:

0,0,True
0,1,True
1,0,False
1,1,False
2,0,True
2,1,True

----

Input:

500
100,50
200,100
300,150

Output:

100,0,True
150,0,False
200,0,True
200,1,True
250,0,False
300,0,True
300,1,False
300,2,True
350,0,False
400,0,True
400,1,True
450,0,False
450,2,False
500,0,True
500,1,False

----

Input:

1000
23,345
65,98
912,12
43,365

Output:

23,0,True
43,3,True
65,1,True
163,1,False
261,1,True
359,1,False
368,0,False
408,3,False
457,1,True
555,1,False
653,1,True
713,0,True
751,1,False
773,3,True
849,1,True
912,2,True
924,2,False
936,2,True
947,1,False
948,2,False
960,2,True
972,2,False
984,2,True
996,2,False

Leaderboard Snippet:

var QUESTION_ID=137465,OVERRIDE_USER=41505;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="
"+e.body.replace(OVERRIDE_REG,"")+"
")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
 <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">

Leaderboard

	Author	Language	Size

Winners by Language

Language	User	Score

{{PLACE}}	{{NAME}}	{{LANGUAGE}}	{{SIZE}}	Link

{{LANGUAGE}}	{{NAME}}	{{SIZE}}	Link

How much output is enough?

@aschepler What do you mean? The input specifies an amount of time to "simulate"

JavaScript, 98 97 bytes
a=>b=>[...Array(a+1)].map((_,i)=>b.map((d,j)=>d[0]--||c.push([i,j,d[d[0]=d[1]-1,2]^=1])),c=[])&&c

Try it online
Saved a byte thanks to Shaggy - use currying input syntax.

Save a byte with currying: a=>b=>.

@Shaggy. You're so fast, I was preparing an edit.

Rule of thumb: if there are 2 inputs, always curry!

Python 2, 93 bytes
lambda t,l:sorted(sum([zip(range(x[0],-~t,x[1]),[i]*-~t,[1,0]*t)for i,x in enumerate(l)],[]))

Try it online!

Jelly,  26  25 bytes
Ḣrm⁸ð€µ;€€"J;"J$€€ẎẎḂ0¦€Ṣ

A dyadic link taking a list of delay, period number-lists and a time-frame number and returning a list of time, light, action integers.
The lights are 1-indexed and 0 represents the 'off' action, while 1 represents the 'on' action.
Try it online!
How?
Ḣrm⁸ð€µ;€€"J;"J$€€ẎẎḂ0¦€Ṣ - Link: [[delay, period],...], time-frame
    ð€                    - for €ach [delay, period]:
Ḣ                         -   head (get the delay and modify the item to [period])
 r                        -   inclusive range to time-frame = [delay,delay+1,...,time-frame]
   ⁸                      -   chain's left argument = [period]
  m                       -   modulo slice = [delay, delay+period, delay+2*period, ...]
      µ                   - monadic chain separation, call that v
           J              - range(length(v)) = [1,2,...,nLights]
          "               - zip with:
       ;€€                -   concatenate for €ach for €ach (add light indexes to times)
               $€€        - last two links as a monad for €ach for €ach:
              J           -   range (length(switch-times-for-a-light))
             "            -   zip with:
            ;             -     concatenation (i.e. append a 1-based index)
                  ẎẎ      - tighten & tighten again (flatten by 2 to a list of triples)
                      |€  - sparse application of (for €ach):
                     0    - ...to indexes: 0 (=last entry)
                    Ḃ     - ...action: modulo by 2 (even appended indexes ->0s; odds -> 1s)
                        Ṣ - sort the resulting list of triples

Python 2, 206 214 bytes

Added eight bytes to comply with the rules (taking input via stdin).

Q=input();D,T=Q[0],[map(int,q.split(","))for q in Q[1:]];O,l=[],len(T)
for j in range(l):
	t,b=T[j][0],9>8
	while t<=int(D):O+="%0*d,%0*d,%s"%(len(D),t,len(str(l)),j,b),;b=not b;t+=T[j][1]
print"\n".join(sorted(O))

Try it online!
This code generates an unordered lists containing each light's switching times, pads those times and the light identifier, sorts said list and outputs it.

By standard rules you must take input you cannot expect it to pre-exist in a variable. You'll probably find that using input() will allow you to cut they byte-count down too (no string parsing will be required since Python 2's input() is eval(raw_input())) :).

...also if you use numbers rather than strings in O they'll sort, which would probably also cut the byte count,

@JonathanAllan Thanks for noticing the rule discrepency; I will not incorporate your suggestions as there is a significantly shorter Python 2 answer by now.

Perl 5, 106 +  1 (-n) = 107 bytes
($a[$i],$b[$i++])=eval for<>;for$i(0..$_){for(0..$#a){$a[$_]+=$b[$_],say"$i,$_,".($s[$_]^=1)if$i==$a[$_]}}

Try it online!

Röda, 105 87 85 bytes
{|t|enum|[([_+_]*(t-_1[0]+1))()|enum|(_+_)]|{[[_+_4,_3,_4//_2%2=0]]if[_4%_2=0]}|sort}

Try it online!
Explanation:
{|t| /* Declare a lambda with one parameter */
/* The input stream contains arrays */
enum| /* For each array in the input, push an ascending number after it */
/* [1] (for stream content in this point, see below) */
[ /* For each array-number pair in the stream: */
    (
        [_+_] /* Create a copy of the array with the number as the last element */
        *(t-_1[0]+1) /* Create copies of the array for every ms simulated */
    )()| /* Push all copies to the stream */
    enum| /* After each copy, push an ascending number to the stream */
    (_+_) /* Append the number to each array before */
]|
/* [2] (for stream content in this point, see below) */
{
    /* Push an on or off event to the stream: */
    [[
        _+_4,      /* delay + time = actual time */
        _3,        /* light-id */
        _4//_2%2=0 /* does the light go on or off? */
    ]]
    if[_4%_2=0] /* if the light goes on or off (time%period=0) */
}|
/* [3] (for stream content in this point, see below) */
sort /* Sort the events */
}

The stream contains at point [1] values in the following order:
[delay, period], light-id
 _1[0]  _1[1]    _2

The stream contains at point [2] values in the following order:
delay, period, light-id, time
_1     _2      _3        _4

The stream contains at point [3] arrays with the following structure:
[time, light-id, on_or_off]

Haskell, 121 bytes
import Data.List
t!l=sort$(zip[0..]l)>>=takeWhile(\(a,_,_)->a<=t).(\(i,(d,w))->iterate(\(t,i,s)->(t+w,i,not s))(d,i,2>1))

Try it online.
This is the program I started from:
import Data.List

type LightId = Int
type Time = Int
type State = Bool
type LightEvent = (Time, LightId, State)

lightSimulation :: Time -> Time -> [(Time, State)]
lightSimulation delay interval = iterate step (delay, True)
  where step (time, state) = (time+interval, not state)

addId :: LightId -> (Time, State) -> LightEvent
addId id (t, s) = (t, id, s)

simulate :: Time -> [(Time, Time)] -> [LightEvent]
simulate timeLimit lights = sort $ concatMap lightSim (zip [0..] lights)
  where withinTimeLimit = ((<=timeLimit) . fst)
        lightSims (id, (delay, interval)) = map (addId id) $ takeWhile withinTimeLimit (lightSimulation delay interval)

And before final golfing I has shortened it to:
import Data.List

light (id,(delay,interval)) = iterate step (delay, id, True)
  where step (time, id, state) = (time+interval, id, not state)

simulate timeLimit lights = sort $ concatMap lightSims (zip [0..] lights)
  where lightSims l = takeWhile(\(a,b,c)->a<=timeLimit)$light l


text:
Champernowne up to me
Inspired by this question.
Champernowne's constant is an infinite decimal number that consists of "0." followed by all natural numbers concatenated together.  It begins like so: 0.123456781011121314151617181920212223242526272829303132333435363738394041424344454647484950, etc. The digits of Chamernowne's constant are sequence A033307 in the OEIS.
Your Task:
Write a program or function that, when given an integer as input, outputs/returns Champernowne's constant up to the first occurance of the input.  For example, if the input is 13, you should output 0.12345678910111213.  If you wish, for inputs greater than 0, you may drop the leading "0." in your output.
Input:
An integer, or a string containing only numbers.
Output:
Champernowne's constant up to the first occurance of the input.
Test Cases:
0   -> 0
1   -> 0.1 OR 1
14  -> 0.1234567891011121314 OR 1234567891011121314
91  -> 0.1234567891 OR 1234567891
12  -> 0.12 OR 12
101 -> 0.123456789101 OR 123456789101

Scoring:
This is code-golf, lowest score in bytes wins!

Very related.

@ETHproductions, thanks, I hadn't seen that.  It is very closely related, but I don't think it is quite close enough to qualify as a dupe.  However, if you disagree, feel free to CV.

@ETHproductions I can't believe I'm getting to the point where I'm forgetting about questions that I actually answered. Anyway to me that seems like a dupe, so I'll close this for now.

05AB1E, 6 bytes
Code
LJ¹¡н«

Uses the 05AB1E encoding. Try it online!
Explanation
L         # Create the range [1, 2, ..., input]
 J        # Join into a single string
  ¹¡      # Split at occurences of the input
    н     # Take the first element
     «    # Append the input to the first element and implicitly output

And I thought this would actually be somewhat difficult :(

Python 3, 70 63 61  bytes
A bunch of bytes removed thanks to @Rod, and some more thanks to @WheatWizard
lambda x:''.join(map(str,range(1,x))).split(str(x))[0]+str(x)

Try it online!

you can save 13  bytes using map instead list comprehension, and backticks instead str

@Rod Thanks! I've used your map suggestion

@WheatWizard Good idea, thanks!

MATL, 20 15 14 bytes
U:VXzG&Yb1X)Gh

Takes the input as a string. Try it online!
Explanation
U      % Implicitly input a string. Convert to number
:      % Range from 1 to that
V      % Convert to string. Includes spaces as separators
Xz     % Remove spaces
G      % Push input again
&Yb    % Split at that. Gives a cell array
1X)    % Get contents of the first cell
G      % Push input again
h      % Concatenate horizontally. Implicitly display

Haskell, 82 73 55 bytes
x!b|or$zipWith(==)x b=x
x!(a:b)=a:x!b
(!(show=<<[1..]))

Try it online!
Explanation
First we define !.  x!b truncates b to the first appearance of x.  It does this by checking if b starts with x (or$zipWith(==)x b) returning x if it does and moving one down the string otherwise.  Then we define our main function.  Our main function is a point-free function that takes the constant (show=<<[1..]) and truncates it to the first appearance of x.  This takes x as a string.

Pyth, 11 8 bytes
+hcjkSQ`

Try it online! or run a Test Suite.
Simply creates the constant (jkSQ) and then prints the constant up to the input (c ... `) followed by the input (+ ...).

Mathematica, 111 bytes
(m=Min@SequencePosition[s=Flatten[IntegerDigits/@Range[0,#]],t=IntegerDigits@#];FromDigits@Join[s[[;;m-1]],t])&