16
\$\begingroup\$

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.

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

7 Answers 7

9
\$\begingroup\$

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

examples

(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
\$\endgroup\$
2
  • \$\begingroup\$ Sad, I was hoping it would take a bit longer before someone found a efficient solution, nice job \$\endgroup\$
    – mousetail
    Mar 2, 2023 at 17:46
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Arnauld
    Mar 2, 2023 at 17:54
7
\$\begingroup\$

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
\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Suever
    Mar 2, 2023 at 19:51
  • \$\begingroup\$ @Suever Great ideas both! Thank you! \$\endgroup\$
    – Luis Mendo
    Mar 2, 2023 at 21:29
2
\$\begingroup\$

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!

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

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

\$\endgroup\$
2
2
\$\begingroup\$

Charcoal, 28 bytes

FN«≔⁺∧&ι⊕ιθL§⪪⍘⊕ι²0⁰θ⊞υθ⟦I⌈υ

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

FN«

Repeat n times.

≔⁺∧&ι⊕ιθL§⪪⍘⊕ι²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.

⟦I⌈υ

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.

\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.