Max power of 2 such that 2^m divides n. (The ruler sequence) [duplicate]

Question

Input:

A positive integer N.

Challenge:

Suppose you have a list of integers n = 1, 2 ... N. Output a list of integers, where each number is the maximum power of 2, m, such that 2^m divides each number of n.

---

Test cases:

1
0

15
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0

100
0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2

This is OEIS A007814.

Answer 1

Python 2, 46 bytes

Saved a couple of bytes thanks to nwellnhof.

lambda k:[len(bin(t+1&~t))-3for t in range(k)]

Try it online!

---

Python 2, 51 bytes

lambda k:[len(bin(t-~-(t&-~t)))-3for t in range(k)]

Try it online!

How?

The formula for a(k) is log₂(k - (k & (k - 1))). That's quite fluffy, but fortunately it can be shortened significantly. In Python, floor(log₂(N)) = len(bin(N)) - 3, because bin() appends 0b to the binary representation of an integer. As a side note, len(bin(N))-3 can be replaced by N.bit_length()-1, but that is not really beneficial for golfing purposes. That gives us the opportunity to get rid of the import math and the use of math.log. Another part that can be shortened is k & (k-1). Using more bitwise operations, we get k&~-k instead, and then we subtract this from the actual k. But that would make us iterate over the range [1, k], which would waste bytes because Python lacks inclusive ranges. In order to save a few bytes, we iterate over the integers in [0, k) instead and modify the formula, obtaining k+1-(k&-~k) = k-~-(k&-~k). However, than can be simplified further to k+1&~k (as @nwellnhof pointed out).

Answer 2

Pyth, 6 bytes

m/Pd2S

Try it online: Demonstration

Explanation:

m/Pd2S
     S   range [1, 2, ..., input]
m        map each number to
 /  2       the count of two in
  Pd        its prime factorization 

Answer 3

Mathematica, 29 bytes

#~IntegerExponent~2&~Array~#&

Try it online!

Answer 4

R, 60 59 55 40 bytes

n=1:scan();cat(log2(n-(bitwAnd(n,n-1))))

Reads from stdin, writes to stdout. Implements the formula referenced in Mr. Xcoder's solution, which fortunately vectorizes nicely in R.

Try it online!

Answer 5

Haskell, 29 bytes

($l).take
l=0:do x<-l;[x+1,0]

Try it online!

Recursively generate the infinite list l.

Answer 6

C (gcc), 49 44 bytes

f(n){n-1&&f(n-1);printf("%.f ",log2(n&-n));}

Try it online!

Answer 7

JavaScript (ES6), 42 39 bytes

Saved 3 bytes thanks to @Shaggy

A straight-forward version using Math.clz32(). Returns a comma-delimited string.

f=n=>--n&&f(n)+[,31-Math.clz32(++n&-n)]

Test cases

f=n=>--n&&f(n)+[,31-Math.clz32(++n&-n)]

console.log(f(1))
console.log(f(15))
console.log(f(100))

---

Alternate version, 42 41 bytes

Saved 1 byte thanks to @Shaggy

f=n=>--n&&f(n)+[,(g=n=>n&1&&1+g(n/2))(n)]

How?

This is based on the recursive formula:

a(n) =
  0 if n is odd
  a(n / 2) + 1 if n is even

For golfing purposes, the function g is actually doing almost the opposite:

g(n) =
  g(n / 2) + 1 if the least significant bit of n is set
  0 if the least significant bit of n is clear

We do it that way because n has already been decremented when g is invoked, so it's off by 1. This generates floats, but testing the LSB rather than computing a modulo ensures that the decimal part is ignored.

The function f is just a wrapper that invokes g for all values from n - 1 to 1, appending the results in reverse order, and eventually appending a leading 0 when the recursion stops.

Test cases

f=n=>--n&&f(n)+[,(g=n=>n&1&&1+g(n/2))(n)]

console.log(f(1))
console.log(f(15))
console.log(f(100))

Answer 8

x86 Machine Code, 10 bytes

0F BC C1
49
89 04 8A
75 F7
C3

The above bytes of machine code define a function that takes an array of length n as input, and then replaces the value at each index with the maximum power of 2, m, such that 2^m divides each number of n. each number is the maximum power of 2, m, such that 2^m divides each number of n.

It follows the __fastcall register-based calling convention, passing the first parameter (the length of the array, n) in the ECX register and the second parameter (a pointer to the beginning of the array) in the EDX register. I posit that this is legal because, like C, arrays/lists are represented at the machine-code level as a pointer to the first element and a length.

As stipulated in the challenge, n is assumed to be a strictly positive integer.

Ungolfed assembly mnemonics:

                ; void RulerSequence(unsigned len, unsigned * pSequence);
                ;                                     ECX  = len
                ;                                     EDX  = pSequence
             Top:
0F BC C1        bsf   eax, ecx                      ; EAX  = log2(ECX)
49              dec   ecx                           ; ECX -= 1
89 04 8A        mov   DWORD PTR [edx+ecx*4], eax    ; pSequence[ECX] = EAX
75 F7           jnz   Top                           ; loop to 'Top' if ECX != 0
C3              ret

As you can see, the logic is embarrassingly simple. The only thing even slightly tricky is the use of the BSF instruction, which obtains the index of the least-significant set bit. This is the shortest and fastest way to compute log₂(n).

Try it online!

---

Bonus alternate solution, also 10 bytes

                ; void RulerSequence_Alt(unsigned len, unsigned * pSequence);
                ;     ECX = len
                ;     EDX = pSequence
             Top:
0F BC C1        bsf   eax, ecx
89 44 8A FC     mov   DWORD PTR [edx+ecx*4-4], eax
E2 F7           loop  Top
C3              ret

Instead of separate DEC+JNZ instructions, we use the long-obsolete CISC-style LOOP instruction, which decrements ECX and loops to the specified label as long as ECX != 0. LOOP takes the same 2 bytes to encode as JNZ, so this saves us 1 byte from DEC. However, to compensate for the decrement being done after the array offset calculation, we need to add an additional subtraction to the indexing, which costs us an additional byte. So it's a wash.

Answer 9

C, 48 bytes

Using GCC's builtin to count trailing zeros:

f(v,n)int*v;{while(n--)v[n]=__builtin_ctz(n+1);}

Input in integer n, and output to the supplied array v (which must be at least n long).

Test program:

#include <stdlib.h>
#include <stdio.h>
int main(int argc, char **argv)
{
    while (*++argv) {
        int n = atoi(*argv);
        if (n>0) {
            int *v = malloc(sizeof *v * n);
            if (!v) continue;
            f(v,n);
            printf("\n%d:\n", n);
            for (int i = 0;  i < n;  ++i)
                printf("%d ", v[i]);
            free(v);
            puts("");
        }
    }
}

Answer 10

Husk, 6 bytes

†#2†pḣ

Try it online!

How?

It's my first "non-trivial" attempt in Husk, so patient with me :-)

†#2†pḣ   - Full program.

     ḣ   - The range [1, input].
   †p    - Map with prime factorisation.
†#2      - Count the 2's in each.
         - Implicitly output.

Alternative, suggested by Erik the Outgolfer: m#2mpḣ.

Answer 11

Jelly, 5 bytes

RÆEḢ€

Try it online!

*Saved 1 byte thanks to miles!

Definitely not as short as the built-in answer with Order, multiplicity, valuation, but I think it's worth it posting.

How?

RÆEḢ€  - Full program.

R      - The range [1, input].
 ÆE    - Compute the array of exponents of the prime factorization, including 0's.
    €  - For €ach.
   Ḣ   - Head. 
       - Implicitly output the result.

Answer 12

Jelly, 3 bytes

ọ€2

Try it online!

Answer 13

Pari/GP, 29 bytes

n->[valuation(x,2)|x<-[1..n]]

Try it online!

Answer 14

Octave, 42 37 bytes

5 bytes removed thanks to @StewieGriffin!

@(n)([~,y]=max(mod(x=1:n,2.^x')>0))-1

Try it online!

Explanation

Let n be the input. The code computes each number k in the range 1, ..., n modulo each number d in 1, 2, 4, ..., 2^n. This gives an n×n matrix, where k is the column index and each d corresponds to a row.

This matrix is compared for inequality with 0. As a result, nonzeros are transformed into 1, and zeros remain as 0.

For each column k, finding the (1-based) row index of the maximum value and subtracting 1 gives the solution. In other words, the number of initial zeros in each column is the desired m for each k.

Answer 15

Retina, 34 bytes

.+
$*
\B1
¶$`1
+`(1+)\1
$+0
%r`0\G

Try it online! Explanation:

.+
$*

Convert to unary.

\B1
¶$`1

Create a triangle.

+`(1+)\1
$+0

Start converting each row to base 2...

%r`0\G

...but instead of completing the conversion, just count the trailing zeros.

Answer 16

05AB1E, 5 bytes

Patched a bug thanks to Emigna (Ý -> L).

LÒε2¢

Try it online!

How?

LÒε2¢   - Full program.

L       - The range [1, input].
 Ò      - Prime factors with duplicates.
  ε     - For εach.
   2¢   - Count the 2's.
        - Output (implicitly).

Alternative:

LεÒ2¢

Answer 17

Java 8, 86 + 26 75 81 79 77 76 74 bytes

n->{for(int i=0;i<n;System.out.println(n.toString(++i&-i,2).length()-1));}

Try it online!

Answer 18

Japt, 7 bytes

A port of Jakube's solution.

õ_k è¶2

Try it

---

Explanation

Implicit input of integer U.

õ_

Generate an array of integers from 1 to U and pass each through a function.

k

Get an array of the prime factors of the current element.

è¶2

Count (è) the number of elements that are strictly equal to (¶) 2.

Answer 19

Perl 6, 27 17 15 bytes

-2 bytes thanks to Brad Gilbert b2gills

{(1..$_)».lsb}

Try it online!

Answer 20

Haskell, 36 bytes

a 0=[0]
a n|q<-a$n-1=q++n:q
take<*>a

An adaption of my answer from a similar challenge.

Try it online!

Answer 21

Pyth, 9 bytes

msl-hd.&h

Verify the test cases.

If returning as floats was allowed, then 8 bytes:

ml-hd.&h

Explanation

msl-hd.&h  - Full program. Q means input.

m          - Map over the implicit range [0, Q) with a variable d.
 sl        - The integer part of logarithm base 2 of...
   -hd.&h  - ... The Logical OR between d and d + 1, subtracted from d + 1.
           - Output implicitly.

The formula for a(k) is log₂(k - (k & (k - 1))), if we were to work with [1, Q]. By mapping over [0, Q) instead, we modify the formula accordingly, log₂(k + 1 - (k & (k + 1)). This allows us to abuse implicit ranges at the end of the program.

Pyth, 6 bytes

/R2PMS

An alternative to Jakube's approach.

/R2PMS   - Full program. Q means input.

     S   - The range [1, Q].
   PM    - Get prime factors of each.
/R2      - Count the number of 2's.

Answer 22

Pyth, 10 bytes

mlec.Bd\1S

Try it here.

Answer 23

Pyke, 5 bytes

Port of Jakube's Pyth answer, and my 05AB1E answer.

SFP2/

Try it here!

How?

S     - The range [1, input]
 F    - For each.
  P   - Prime factors.
   2/ - Count the number of 2's.
      - Output implicitly.

Answer 24

J, 10 bytes

_{.@q:1+i.

Try it online!

Explanation

_{.@q:1+i.  Input: n
        i.  Range, [0, n)
      1+    Add 1
_   q:      Exponents of each prime in the factorization of each
 {.@        Head each (Get the exponent of 2)

Answer 25

Perl 50 + 2 bytes

perl -E'say+sprintf("%b",$_)=~s/.*1//r=~y===c for 1..shift'

50 bytes for the program proper, and 2 for the command line switch.

The largest m such that 2^m divides n is just the number of trailing 0s in the binary representation of n. We get the latter by removing everything up to the last 1 of the binary representation, and taking the length of that. y===c happens to do that (it replaces every character by itself, returning the number characters it replaced).