# Largest Binary Area

Take the sequence of all natural numbers in binary, (1, 10, 11, ..) then write them vertically beside each-other like this (least significant bit on top; 0s have been replaced with spaces):

1 1 1 1 1 1 1 1 1
11  11  11  11
1111    1111
11111111
11


Notice there are areas of connected 1s in the binary representation of the number.

Your task is, for a given n, calculate the biggest continuous area in the binary representation of all numbers less than n. If you start with n=1 and consider all numbers less than or equal to n, the sequence starts like this:

(1, 1, 3, 3, 3, 4, 7, 7, 7, 7, 7, 7, 8, 11, 15, 15, 15...)


Areas are joined if they connect horizontally or vertically, diagonals don't count.

rules apply: you can choose to consider either all numbers strictly less than N or those less than or equal to N, and either 0 or 1. This is , shortest answer wins.

• Sandbox link Mar 2 at 13:46
• @LuisMendo In accordance to sequence rules you can start with either 1 or 0, so you can pick either option for your answer Mar 2 at 14:04

# JavaScript (V8), 67 bytes

Prints the sequence infinitely.

for(m=n=0;g=k=>k?!(k&k+1)+g(k>>1):s;print(m=m>s?m:s))s=n&++n?g(n):1


Try it online!

### How?

This is based on the observation that the biggest local area is always those of the pattern formed by the leading 1's (in red below).

If the area of the leading pattern is $$\N\$$, any non-leading pattern may at best reach an area of $$\N-1\$$ (like the green one in figure 2).

(Figure 1 is for $$\n=8\$$ to $$\n=15\$$. Figure 2 is for $$\n=16\$$ to $$\n=23\$$.)

### Commented

for(              // infinite loop:
m =             //   m = current maximum
n = 0;          //   n = counter
g = k =>        //   g is a helper recursive function taking k
//   and returning the sum of s and the number
//   of leading 1's in k
k ?           //   if k is not 0:
!(          //     increment the final result if ...
k & k + 1 //     ... k and k+1 have no bits in common
) +         //     (i.e. k+1 is a power of 2)
g(k >> 1)   //     do a recursive call with floor(k / 2)
:             //   else:
s;          //     stop and return s
print(          //   after each iteration, print ...
m = m > s ? m //   ... the maximum of m and s
: s //   (and update m accordingly)
)               //
)                 //
s =             //   s is the area of the pattern of leading 1's
n & ++n ?     //   increment n; if n is not a power of 2:
g(n)        //     update s to g(n)
:             //   else:
1           //     reset s to 1

• Sad, I was hoping it would take a bit longer before someone found a efficient solution, nice job Mar 2 at 17:46
• @mousetail Well, it's probably not optimal. A more direct formula may exist, or at least an approach with a single recursion giving the answer for any $n$ without having to keep track of the maximum from the beginning. Mar 2 at 17:54

# MATL, 14 13 bytes

1 byte saved thanks to @Suever

:B4&1ZIXz5#XM


Inputs n and outputs the n-th term of the sequence, using the "less or equal" definition.

Try it MATL online!

### Explanation

:       % Implicit input: n. Range [1 2 ... n]
B       % Convert to binary. Gives an n-row matrix
4&1ZI   % Label connected components, using 4-neighbourhood. This labels each
% connected component of cells equal to 1 with an integer, starting at 1
Xz      % Nonzeros. Removes zeros and reshapes into a column vector
5#XM    % Second output of 'mode' function: gives the number of times that the
% mode occurs. Implicit display

• You may be able to use the second output of mode rather than 8#uX> like this. That may be a good candidate for & for XM Mar 2 at 19:51
• @Suever Great ideas both! Thank you! Mar 2 at 21:29

# Python3, 333 bytes:

E=enumerate
def f(n):
t=[*map(bin,range(1,n))]
k=[i[2:][::-1]+'0'*(max(map(len,t))-len(i))for i in t]
q,l=[(x,y)for x,r in E(k)for y,u in E(r)if'1'==u],[]
while q:
Q,s=[q.pop(0)],1
while Q:
x,y=Q.pop(0)
for X,Y in[(0,1),(0,-1),(1,0),(-1,0)]:
C=(x+X,y+Y)
if C in q:Q+=[C];q.remove(C);s+=1
l+=[s]
return max(l)


Try it online!

• -2 with C=x+X,y+Y Mar 3 at 23:53
• And 2 others if you put t, k and q on the same line by using semicolons Mar 3 at 23:56
• -1 with *t,=map(bin,range(1,n)) Mar 4 at 0:05

# Python, 95 93 92 88 bytes

m=n=0
while g:=lambda k:k and(k&k+1<1)+g(k>>1):print(m:=max(m,s:=n&(n:=n+1)<1or g(n)+s))


Attempt This Online!

Outputs True instead of 1. +2 bytes to fix this

-2 thanks to @Arnauld
-4 thanks to @97.100.97.109

• Mar 2 at 20:28
• @97.100.97.109 thanks, updated Mar 2 at 20:35

# Charcoal, 28 bytes

ＦＮ«≔⁺∧＆ι⊕ιθＬ§⪪⍘⊕ι²0⁰θ⊞υθ⟦Ｉ⌈υ


Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation:

ＦＮ«


Repeat n times.

≔⁺∧＆ι⊕ιθＬ§⪪⍘⊕ι²0⁰θ


If the effective 1-based index is a power of 2, then start the new area from 1, otherwise add the number of leading 1s to it.

⊞υθ


Save the size of the latest area.

⟦Ｉ⌈υ


Output the size of the largest area.

I did find some relevant sequences in the OEIS:

• A000225 is the list of indices where the size of the largest contiguous area equals the index.
• A090996 is the number of leading 1s.
• A267604 appears to be list of indices where the new area overtakes the old area in size.

Unfortunately I was unable to use any of these sequences to reduce my byte count.

# Jelly,  12  11 bytes

B«\)LÐṀFS)Ṁ


A monadic Link that accepts $$\n\$$ and yields the largest binary area when arranging the numbers $$\1\$$ to $$\n\$$ inclusive.

Try it online!

### How?

B«\)LÐṀFS)Ṁ - Link: positive integer, n
)  - for each (i in [1..n]):
)        -   for each (j in [1..i]):
B           -     convert (j) to binary
\         -     cumulative reduce by:
«          -       minimum (i.e. zero any bits after the first 0)
ÐṀ     -   keep those maximal under:
L       -     length (e.g. j = 27 -> [zeroed(binary(16))..zeroed(binary(27))])
F    -   flatten
S   -   sum
Ṁ - maximum


# Python 3.8, 85 bytes

lambda n:max((j:=2**len(bin(n))>>3)-1,sum(bin(i*2)[2:].find('0')for i in range(j,n)))


An anonymous function that accepts a positive integer, n, and returns the largest binary area formed using the numbers less than n.

Try it online!