# Let's study Neil numbers

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, 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 .

## 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. :-)

• technically there's also a gap between 1s with zero length too!
– Jo King
May 26 '20 at 12:53
• This is a great question! It reminds me that from time to time I will see a crossword where one or more of the words intersects with other words in the form --+---+-+----.
– Neil
May 26 '20 at 13:09
• Speaking of congratulations, I think you might have surpassed @xnor and become the 3rd place all-time high earlier this month?
– Neil
May 26 '20 at 14:56
• I knew it! Tributes to other users always include the word "user id". This one isn't an exception.
– user92069
May 26 '20 at 23:22
• @numbermaniac Good catch. Fixed! May 29 '20 at 7:30

# 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.

• I'm not sure, but I think you may qualify for the brownie points May 28 '20 at 17:45

# 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!

• This is slightly shorter if you use map instead of for Try it online! May 27 '20 at 13:51

# 05AB1E, 1615 13 bytes

b1¡€gZ©L¢PΘ®*


Outputs 0 as falsey result.

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)


# 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

• 15 May 26 '20 at 23:08

# Retina 0.8.2, 54 bytes

.+
$* +(1+)\1$1O
(O?1)+
1
OO+
(^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.

OO+


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.

# J, 30 24 bytes

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


Try it online!

-6 bytes thanks to Bubbler

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

• Using 0 for non-neil numbers seems better at 24 bytes, using the idea from APL answer. May 27 '20 at 1:38
• An interesting alternative 24 using determinant, which happens to ignore extra zero rows. May 27 '20 at 2:11
• @Bubbler Thanks. It definitely felt like I was missing a simplification but I missed that one. The determinant is slick, though I don't completely understand how it works. Might be worth posting separately with explanation. May 27 '20 at 2:31

# 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. # R, 948575 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'. • 75 bytes. Nice approach! We had the same sort of thoughts, but your Neil-number condition was much cleverer than mine -- I had 84 bytes May 26 '20 at 16:43 • I'm also wondering if you could do N=max(s<-z$l[!z$v]), but I always seem to miss an edge case where tricks like that don't work. May 26 '20 at 16:44 • Thanks (yet) again, Giuseppe! I'm quite ashamed about the number of 'fossil' parentheses and unused variable assignments that seem to be buried in my original post (some from previous-but-discarded attempts), waiting to be dug up... May 26 '20 at 18:47 • Could do this for 74 using max. May 26 '20 at 19:04 • Also, don't worry, when you golf for long enough, it becomes a habit. And then it starts to creep into your "real" code and it all becomes an unintelligible mess, at least to anybody else ;-) May 26 '20 at 19:05 # 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Ƒȧ$Ṫ # 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. • I got 79 bytes by rewriting from scratch with a single for loop. My solution uses ffs(). May 26 '20 at 20:30 • @Arnauld I got 77 bytes! :D May 27 '20 at 16:17 • Very nicely done! May 27 '20 at 16:27 # 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 !. # 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!

# 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].

# Java (JDK), 126117 116 bytes

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;
}

• Nov 18 '20 at 20:33
• @Arnauld Thanks!
– user
Nov 18 '20 at 20:36
• @ceilingcat Thanks!
– user
Nov 28 '20 at 16:11

# MATL, 14 bytes

BY'w~)SttfX=*z


For non Neil numbers the output is 0.

### 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


# 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.

• That looks much like my first attempt, but I found a shorter way. May 26 '20 at 19:47

# 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 :)

# 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.

• That approach is wrong. For instance, 81 = 0b1010001. Your code stops because it cannot find a sequence of length 2, and then concludes it's a Neil number of order 1. That's incorrect, because there is sequence of length 3, making this not a Neil number. May 26 '20 at 20:10
• Fixed it. Forget to check if there were any 0s in the binary representation when it's done. May 26 '20 at 20:29
• 56 bytes. Prints N in unary. May 26 '20 at 22:20

# 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...

# 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!

# 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!

# 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

• Save 2 bytes by testing the value of _1 instead of its size. Jun 3 '20 at 2:55

# Husk, 14 10 bytes

£ḣ∞0OfΛ¬gḋ


Try it online!

-4 bytes from Zgarb.

• o…1L can be ŀ Oct 17 '20 at 10:36
• In fact, you can use £ to get 10 bytes Oct 17 '20 at 10:39

# Japt, 15 bytes

Returns 0 for falsey.

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

¤ôÍ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


# 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!