Let's study Neil numbers

Question

Congratulations to Neil for hitting 100k rep! As a tribute, we are going to study 'Neil numbers'.

Neil's user ID is 17602 and there's something special about the binary representation of this number:

$$17602_{10}=1\color{blue}{000}1\color{blue}{00}11\color{blue}{0000}1\color{blue}{0}_2$$

$$\begin{array}{c|c} 1&\color{blue}{000}&1&\color{blue}{00}&11&\color{blue}{0000}&1&\color{blue}{0}\\ \hline &3&&2&&4&&1 \end{array}$$

There's exactly one group of consecutive zeros of length 1, one group of length 2, one group of length 3 and one group of length 4.

This is an order-4 Neil number.

More generally:

An order-\$n\$ Neil number is a positive integer whose binary representation contains exactly \$n\$ groups of consecutive zeros and for which there's exactly one group of consecutive zeros of length \$k\$ for each \$0<k\le n\$, with \$n>0\$.

Clarifications:

• Leading zeros are obviously ignored.
• Groups of consecutive zeros are indivisible (e.g. 000 is a group of length 3 and cannot be seen as a group of length 1 followed by a group of length 2, or the other way around).

Examples

Order-1 Neil numbers are A030130 (except 0, which is not a Neil number as per our definition).

The first few order-2 Neil numbers are:

18, 20, 37, 38, 41, 44, 50, 52, 75, 77, 78, 83, 89, 92, 101, 102, 105, 108, 114, ...

Your task

Given a positive integer as input, return \$n\ge 1\$ if this is an order-\$n\$ Neil number or another consistent and non-ambiguous value (0, -1, false, "foo", etc.) if this is not a Neil number at all.

This is code-golf.

Test cases

Using 0 for non-Neil numbers:

Input   Output
1       0
2       1
8       0
72      0
84      0
163     0
420     0
495     1
600     3
999     0
1001    2
4095    0
8466    4
16382   1
17602   4
532770  5

Or as lists:

Input : 1, 2, 8, 72, 84, 163, 420, 495, 600, 999, 1001, 4095, 8466, 16382, 17602, 532770
Output: 0, 1, 0, 0, 0, 0, 0, 1, 3, 0, 2, 0, 4, 1, 4, 5

Brownie points if your user ID is a Neil number. :-)

Answer 1

Charcoal, 21 bytes

≔Φ⪪⍘Ｎ²1ιθＩ×Ｌθ⬤θ№θ×0⊕κ

Try it online! Link is to verbose version of code. Outputs 0 for irrelevant numbers. Happens to output 1 for 0 as per the OEIS sequence. Explanation:

≔Φ⪪⍘Ｎ²1ιθ

Convert the input to binary, split on 1s, and remove empty elements.

Ｉ×Ｌθ⬤θ№θ×0⊕κ

Check that the array contains all lengths of 0s and output its length if it does or 0 if it does not.

Answer 2

Python 2, 88 86 bytes

-2 bytes thanks to @David!

s=sorted([0]+map(len,bin(input()).split("1")[1:]))
n=s[-1]
print(s[~n:]==range(n+1))*n

Try it online!

Finds the length of all zero groups, sorts them, and check if the sorted list is 1, 2, 3, ...

---

Same idea in Python 3.8:

Python 3.8, 85 82 bytes

lambda n:(m:=max(s:=sorted(map(len,f"{n:b}".split("1")))))*(s[~m:]==[*range(m+1)])

Try it online!

Answer 3

05AB1E, 16 15 13 bytes

b1¡€gZ©L¢PΘ®*

Outputs 0 as falsey result.

Try it online or verify all test cases.

Explanation:

b              # Convert the (implicit) input to a binary-string
               #  i.e. 163 → "10100011"
               #  i.e. 420 → "110100100"
               #  i.e. 600 → "1001011000"
 1¡            # Split it on 1s
               #  → ["","0","000","",""]
               #  → ["","","0","00","00"]
               #  → ["","00","0","","000"]
   €g          # Take the length of each chunk
               #  → [0,1,3,0,0]
               #  → [0,0,1,2,2]
               #  → [0,2,1,0,3]
     Z         # Get the maximum (without popping)
               #  → 3
               #  → 2
               #  → 3
      ©        # Store it in variable `®` (without popping)
       L       # Pop an push a list in the range [1,maximum]
               #  → [1,2,3]
               #  → [1,2]
               #  → [1,2,3]
        ¢      # Get the count of each in the list of chunk-lengths
               #  → [0,1,3,0,0] and [1,2,3] → [1,0,1]
               #  → [0,0,1,2,2] and [1,2] → [1,2]
               #  → [0,2,1,0,3] and [1,2,3] → [1,1,1]
         P     # Get the product of that
          Θ    # And check that it's exactly 1
               #  → 0 ==1 → 0 (falsey)
               #  → 2 ==1 → 0 (falsey)
               #  → 1 ==1 → 1 (truthy)
           ®*  # Multiply it by the maximum we stored in variable `®`
               #  → 0*3 → 0
               #  → 0*2 → 0
               #  → 1*3 → 3
               # (after which the result is output implicitly)

Answer 4

APL (Dyalog Extended), 17 bytes

Anonymous tacit prefix function. Any visual similarity with OP is entirely unintentional.

(≢×⍳⍤≢≡∘∧≢¨)~⍤⊤⊆⊤

Try it online!

The structure and order of execution is as follows:

  ┌────────┴───────┐  
┌─┼──────┐      ┌──┼──┐
≢ ×  ┌───┼───┐ ~⍤⊤ ⊆  ⊤
    ⍳⍤≢ ≡∘∧ ≢¨
7 8  5   6   4  2  3  1

⊤ base-Two representation

⊆ extract sub-lists according to the runs of 1s in…

~⍤⊤ negated (0→1, 1→0) base-Two representation

(…) apply the following function to that:

 ≢¨ the length of each run

 ≡∘∧ when sorted, does it (0/1) match…

 ⍳⍤≢ the indices of the length?

× multiply that by…

≢ the length

Answer 5

Retina 0.8.2, 54 bytes

.+
$*
+`(1+)\1
$1O
(O?1)+
1
O`O+
(^1O|\1O)+1?$|.+
$1
O

Try it online! Link includes test cases. Explanation:

.+
$*

Convert to unary.

+`(1+)\1
$1O

Begin base 2 conversion, but using O instead of 0 as \10 would be an octal escape.

(O?1)+
1

As part of base 2 conversion we need to remove one O before each 1. This additionally also collapses all runs of 1s into a single 1, which simplifies matching the consecutive runs of Os later.

O`O+

Sort the runs of Os in ascending order of length.

(^1O|\1O)+1?$|.+
$1

Try to match 1O, then in each repeat match one more O than last time, finally matching an optional 1 at the end. If this succeeds, output the last match (including the leading 1), otherwise output nothing.

O

Count the Os in the last match.

Answer 6

J, ³⁰ 24 bytes

0(#*/:~-:#\)@-.~#;._1@#:

Try it online!

-6 bytes thanks to Bubbler

Fittingly, J has been bested here by Neil's Charcoal answer.

Answer 7

Zsh, 76 bytes

for g (${(s[1])$(([#2]$1))#??})((a[$#g]++))
<<<${${${${a/#%/0}:#1}:+0}:-$#a}

Try it online!

Explanation:

${(s[1])$(([#2]$1))#??}

Convert to binary, remove the 2# prefix, and split the string on 1, giving us our groups of zeroes.

for g ( ... )((a[$#g]++))

For each group of zeroes, increment the array at the index given by the length of that string.

${a/#%/0}

Substitute the array with empty elements filled with zeroes. (If we only increment the array at a[3], then this will set a[1]=a[2]=0)

${${${${ ... }:#1}:+0}:-$#a}

Remove all 1s. If there is anything left (some a[n] != 1), then substitute 0. Otherwise (all a[n] = 1) substitute the length of the array.

Answer 8

R, 94 85 75 74 bytes

n=scan();z=rle(n%/%2^(0:log2(n))%%2);N=max(0,s<-z$l[!z$v]);N*all(1:N%in%s)

Try it online!

Edit: -10 bytes thanks to Giuseppe

Edit 2: -1 more byte thanks again to Giuseppe

Finds differences (diff) between remainders of each power-of-two (n%%2^(0:(l=log2(n))); when sequential remainders are the same, this corresponds to a run of 'zero bits'. rle calculates run lengths, and s extracts runs of zeros. If s contains all the integers up to it's length N, then it's a 'Neil number'.

Answer 9

Jelly, 12 bytes

BŒɠḊm2ṢJƑȧ$Ṫ

A monadic Link accepting a positive integer which yields the order (or 0 if not a Neil number).

Try it online! Or see the test-suite.

How?

BŒɠḊm2ṢJƑȧ$Ṫ - Link: positive integer, V       e.g. 600
B            - convert V to binary                  [1,0,0,1,0,1,1,0,0,0]
 Œɠ          - run lengths of equal elements        [1,2,1,1,2,3]
   Ḋ         - dequeue                              [2,1,1,2,3]
    m2       - modulo-two slice                     [2,1,3]
      Ṣ      - sort                                 [1,2,3]
          $  - last to links as a monad:
        Ƒ    -   is invariant under?:               1
       J     -     range of length                  (since range(len([1,2,3]))==[1,2,3])
         ȧ   -   logical AND                        [1,2,3]
           Ṫ - tail (if empty yields 0)             3

---

Alternative start: Bṣ1Ẉḟ0ṢJƑȧ$Ṫ

Answer 10

C (gcc), ^{116 \$\cdots\$ 78} 77 bytes

Saved 8 11 bytes thanks to ceilingcat!!!
Had to fix a bug, for numbers like \$84\$ (\$1010100_{2}\$) which have multiple runs of single \$0\$s, which added 3 bytes.
Saved 14 bytes thanks to a suggestion from the man himself Arnauld!!!
Added 6 bytes to fix bugs for numbers with multiple runs of zeros of the same length.

c;b;f(n){for(c=3;n;n/=b,c=c&b&~3?n=0:c|b)b=1<<ffs(n);n=ffs(++c)-3;n*=c<8<<n;}

Try it online!

Returns \$n\$ for an input of an order-\$n\$ Neil number or \$0\$ otherwise.

How?

Performs a bit-wise logical-or summation \$c=3+\sum{2^{r+1}}\$, where \$r\$ is the length of a zero bit run for all runs in the input number (including zero length runs). Checks to see if we've seen the same non-zero length run before and returns \$0\$ if we have. After all the input's zero-bit runs have been added to \$c\$ in this manner, \$c\$ is tested to see if we've seen \$n\$ zero-bit runs of lengths \$(1,2,\dots,n)\$ by testing if \$c\stackrel{?}{=}2^{n+2}-1\$ and returns \$n\$ if this is true, \$0\$ otherwise.

Answer 11

Brachylog, 13 bytes

ḃḅ{h0&l}ˢo~⟦₁

Try it online!

 ḅ               Take the runs of
ḃ                the input's binary digits,
  {h0  }ˢ        keep only those that start with 0,
  {  &l}ˢ        and map them to their lengths.
         o       The sorted run lengths
          ~⟦₁    are the range from 1 to the output.

Fun fact, my original attempt was ḃḅo{h0&l}ˢ~⟦₁, but it mysteriously created a choice point giving me some false positives, so I moved the o later to save on a !.

Answer 12

Haskell, 113 bytes

g.f
f 0=[0]
f x|h:t<-f$div x 2=[0|odd x]++(h+1-mod x 2):t
g x|n<-maximum x,r<-[1..n]=sum[n|r==[k|k<-r,y<-x,k==y]]

Try it online!

Answer 13

COW, 234 bytes

oomMMMMOOOOOmoOMMMMOOMOomoOMoOmOoMMMMOOMMMMOomoOMOomOomOoMoOmoOMMMOOOmooMMMmoomoOmoOMoOmOoMOOmoOMOoMOOMMMmoOmoOMMMMOomoomoOMoOmOoMoOMOOmOomOomoomoOmoOOOOmOoOOOmoomOomOoMMMmoomoOmoOmoOmoOmoOMOOMMMMoOMMMmoOMOoMOOOOOMMMmOomoomoOmooMMMOOM

Try it online!

Forms a "string" \$S\$ where:

\$k\in \{1,\dots,n\}\$

• Even indexes (or control cells) \$2k-2\$ serve:
  • to navigate \$S\$
  • to know where \$S\$ ends
  • to count up to \$n\$
• Odd indexes (or k-cells) \$2k-1\$ contain how many consecutive \$k\$ zeros there are

The idea is: when a group of consecutive \$k\$ zeros is found, its k-cells in \$S\$ is incremented.
Hence the input is a order-\$n\$ Neil number if and only if all k-cells are \$1\$.
If so, their quantity \$n\$ will be returned.
0 is returned otherwise.

Explanation

moo ]    mOo <    MOo -    OOO *    OOM i
MOO [    moO >    MoO +    MMM =    oom o


[0]: a/2     [1]: a     [2]: a%2     [3]: counter of current group of 0 (k)     [4]: // unused stuff    [5]: S(0)


i=                               ;   Read a in [0], copy
[                                ;   While [0]
    *>=                          ;      Clear [0], paste in [1]
    [                            ;      While [1]
        ->+<=[=->-<<+>=*]=       ;          {REPEATED SUBTRACTION}
    ]                            ;      [0] is a/2, [1] is 0, [2] is a%2
    >>+<                         ;      Increment [3]                                                   // here [3] is k+1
    [                            ;      If [2] {UPDATE THE STRING}                                      // if a%2==1 the current group of 0 it's been truncated
        >-                       ;          Decrement [3]                                                   // [3]-=1 (k)
        [=>>=-]                  ;          While [x] copy it in [x+2] and decrement it                     // moves to control cell 2k-2 and leaves a trail of control cells behind
        >+<                      ;          Increment [x+3]                                                 // k-cell 2k-1 +=1
        +[<<]                    ;          "Open" [x+2], while [x] x-=2                                    // use the trail to return back to [1]
        >>*<*                    ;          Clear [2] and [3]
    ]                            ;      
    <<=                          ;   Point to [0], copy
]                                ;
>>>>>                            ;      Point to [5]                                                    // the first control cell in S
[                                ;      While [x] is non-zero                                           // while S has not ended
    =+=                          ;          Paste, increment [x], copy                                  // counting (n)
    >-                           ;          Move to [x+1] and decrement                                     // k-cell-=1
    [                            ;          {NOT A NEIL NUMBER}                                             // iff k-cell is non-zero
        *=<                      ;              Divert the flow (performs this loop 2 times, copy 0)
    ]                            ;              will now break the parent while|
    >                            ;      Point to [x+2]                         |                        // next control cell
]                                ;                                             |
=o                               ;   Paste (n or 0) and print                  v

Cell [4] contains the number of groups of consecutive ones that are larger than \$1\$, +1 if LSB is 1.
Nothing relevant for the task, but I couldn't get rid of it staying in this byte count.
Here's a var dump from [4].

Answer 14

Java (JDK), 126 117 116 bytes

• Saved 1 byte thanks to ceilingcat
• Saved 6 bytes - 9, really - thanks to Arnauld

q->{int C[]=new int[9],s=0,n=0;for(;q>0;q/=2)C[s]-=q%2<1?(n=++s>n?s:n)-n:~(s=0);while(q++<n)n=C[q]!=1?0:n;return n;}

Try it online!

Returns 0 for non-Neil numbers.

I feel like this should be smaller, even though it is in Java.

Ungolfed:

q -> {
  int C[] = new int[9],  //C[i] is how many times a streak of length i appeared
      s = 0,             //Length of current streak of zeroes
      n = 0;             //Max streak
  for(; q > 0; q /= 2)   //Go through all of q's digits until q=0
    C[s] -= q % 2 < 1                //If there's a 0 here
            ? (n = ++s > n ? s : n)//Increment s and set n to the max of s and n
               - n      //Subtract n from that because C[s] should stay the same
            : ~(s = 0);  //Otherwise, set s to 0 and add 1 to C[s] (the previous value of s)
  while(q++ < n)           //For every q 0 < q <= n
    n = C[q] != 1 ? 0 : n; //if there was not exactly 1 group of length q, set n to 0
  return n;
}

Answer 15

MATL, 14 bytes

BY'w~)SttfX=*z

For non Neil numbers the output is 0.

Try it online! Or verify all test cases.

Explanation

Consider input 532770 as an example.

B     % Impicit input. Convert to binary
      % STACK: [1 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0]
Y'    % Run-length encoding. Gives values and run lengths
      % STACK: [1 0 1 0 1 0 1 0 1 0], [1 5 1 4 1 2 1 3 1 1]
w~    % Swap, negate element-wise
      % STACK: [1 5 1 4 1 2 1 3 1 1], [0 1 0 1 0 1 0 1 0 1]
)     % Indexing (use second input as a mask into the first)
      % STACK: [5 4 2 3 1]
S     % Sort
      % STACK: [1 2 3 4 5]
tt    % Duplicate twice
      % STACK: [1 2 3 4 5], [1 2 3 4 5], [1 2 3 4 5]
f     % Find: (1-based) indices of nonzeros
      % STACK: [1 2 3 4 5], [1 2 3 4 5], [1 2 3 4 5]
X=    % Equal (as arrays)?
      % STACK: [1 2 3 4 5], 1
*     % Multiply, element-wise
      % STACK: [1 2 3 4 5]
z     % Number of nonzeros. Implicit display
      % 5

Answer 16

perl -MList::Util=max -MList::Util=uniq -pl, 72 71 bytes

@==map{y===c}sprintf("%b",$_)=~/0+/g;$_=(@===max@=)&(@===uniq@=)?0+@=:0

Try it online!

Reads a number from the input, convert it to a string with the number in binary format, extracts the sequences of 0, takes their length, then prints the number of sequences of 0s if 1) there are no duplicates, and 2) the max length equals the number of sequences. Else, 0 is printed.

Edit: Saved a byte by replace && with & which works, since the result of == is 1 or the empty string, which perl treats as 0 if the operator expects a number.

Answer 17

Python 2, 90 bytes

a=[len(z)-1for z in sorted(bin(input())[2:].split('1'))if z]
n=len(a)
print(range(n)==a)*n

Try it online!

I found almost the same solution as Surculose Sputum.

They had the further insight to get rid of the [] so go upvote them :)

Answer 18

Perl 5 -pl, 61 bytes

$a=1;$_=sprintf'%b',$_;$a++while s/10{$a}(?!0)//;$_=!/0/*--$a

Try it online!

Converts number to binary, then removes the 0 sequences in order, starting at 1. When it no longer finds a match, that's the Neil number.

Answer 19

Factor, 146 bytes

: f ( n -- n ) >bin [ = ] monotonic-split [ first 48 = ] [ length ] filter-map
natural-sort dup dup length [1,b] >array = [ last ] [ drop 0 ] if ;

Try it online!

Not golfy at all with all the mandatory spaces and those long words...

Answer 20

Wolfram Language (Mathematica), 93 bytes

If[Sort[s=Length/@Take[Split@IntegerDigits[#,2],{2,-1,2}]]==Range@If[s=={},t=0,t=Max@s],t,0]&

Try it online!

Answer 21

Haskell, 118 bytes

n#0=[n]
n#i|mod i 2<1=(n+1)#div i 2|u<-0#div i 2=n:u
n%[]=n-1
n%x|1/=sum[1|a<-x,a==n]=0|m<-n+1=m%filter(>n)x
(1%).(0#)

Try it online!

Answer 22

Ruby, 67 58 57 55 bytes

->n{i=0;('%b'%n).scan(/0+/).sort.all?{_1==?0*i+=1}?i:0}

Try it online! (+2 bytes because TIO doesn't support ruby 2.7's _1)

-2 bytes thanks to Dingus

Answer 23

Husk, ¹⁴ 10 bytes

£ḣ∞0OfΛ¬gḋ

Try it online!

-4 bytes from Zgarb.

Answer 24

Japt, 15 bytes

Returns 0 for falsey.

¤ôÍmÊÍf
Ê*UeUÊõ

Try it or run all test cases

¤ôÍmÊÍf\nÊ*UeUÊõ     :Implicit input of integer                         > 17602
¤                    :To binary string                                  > "100010011000010"
 ô                   :Split at elements that return truthy
  Í                  :  When converted to decimal (0=falsey, 1=truthy)  > ["","000","00","","0000","0"]
   m                 :Map
    Ê                :  Length                                          > [0,3,2,0,4,1]
     Í               :Sort                                              > [0,0,1,2,3,4]
      f              :Filter, to remove 0s                              > [1,2,3,4]
       \n            :Assign to variable U
         Ê           :Length                                            > 4
          *          :Multiplied by
           Ue        :  Test U for equality with
             UÊ      :    Length of U                                   > 4
               õ     :    Range [1,length]                              > [1,2,3,4]
                     :Implicit output of result                         > 4

Answer 25

Io, 124 bytes

Just a port of the 05AB1E answer.

method(x,i :=x asBinary lstrip("0")split("1")map(size);if(Range 1 to(i max)map(x,i select(o,o==x)size)reduce(*)==1,i max,0))

Try it online!