Largest Binary Area

Question

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.

sequence 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 code-golf, shortest answer wins.

Answer 1

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

Answer 2

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

Answer 3

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!

Answer 4

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

Port of Arnauld's JS answer.

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

Answer 5

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.

Answer 6

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

Answer 7

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!