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

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

• Possible duplicate of this or this (although both ask for more than just the sequence). Sep 6, 2017 at 10:34
• Using the sandbox helps too :) Sep 6, 2017 at 10:40
• @StewieGriffin Is returning floats allowed? E.g.: [0.0, 1.0, 0.0, 2.0, 0.0, 1.0, 0.0, 3.0, 0.0, 1.0, 0.0, 2.0, 0.0, 1.0, 0.0] Sep 6, 2017 at 10:54
• @Mr.Xcoder no the question specifies integers. It doesn't matter what datatype the numbers have, as long as they're displayed as integers. (Relevant for MATLAB / Octave since they treat all numbers as doubles by default). Sep 6, 2017 at 11:04
• @RobertoGraham I am almost 100% sure Stewie will say yes - most code-golf challenges have flexible IO unless there is good reason to restrict it, any easily parsable and consistent delimitation in your output should be fine. Sep 6, 2017 at 13:49

# 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 log2(k - (k & (k - 1))). That's quite fluffy, but fortunately it can be shortened significantly. In Python, floor(log2(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).

• FWIW t+1-(t&-~t) is the same length with less tadpoles. Sep 6, 2017 at 14:01
• @JonathanAllan Heh, I wonder how I missed that. I still like tildes and I will keep it that way though. Sep 6, 2017 at 14:01
• Or simply bin(t+1&~t). Sep 6, 2017 at 14:35

# 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


# Mathematica, 29 bytes

#~IntegerExponent~2&~Array~#&


Try it online!

# R, 605955 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!

($l).take l=0:do x<-l;[x+1,0]  Try it online! Recursively generate the infinite list l. # C (gcc), 49 44 bytes f(n){n-1&&f(n-1);printf("%.f ",log2(n&-n));}  Try it online! # 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)) • This should work for 41 bytes: f=n=>--n&&f(n)+[,(g=n=>n&1&&1+g(n/2))(n)] and applying the same trick to your alt. reduces it to 39 bytes: f=n=>--n&&f(n)+[,31-Math.clz32(++n&-n)]. Sep 6, 2017 at 16:30 # 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 2m 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 log2(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. # 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(""); } } }  • +1. Using an array is better than my printf approach. Combined with my new log2 solution, you could get this to 40 bytes. Sep 6, 2017 at 13:30 • Was that link supposed to point at some code? Or are we supposed to follow one of the links (which one?). It would probably be simpler to show what you meant in a comment... Sep 6, 2017 at 14:15 • I have doubts about log2() - it needs to be passed a double, or to be declared, both of which cost more bytes than would be saved. Sep 6, 2017 at 14:18 • Yes, this only works because log2 is a gcc builtin. Also the predecrement is technically undefined behavior. But the general rule for code golf is that the language implementation counts, not the spec. Sep 6, 2017 at 14:23 • I forgot that log2 is builtin in GCC - that really helps! Where's the predecrement you're referring to? I have a postdecrement (n--). Sep 6, 2017 at 14:27 # 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ḣ. • Seems optimal to me, had m#2mpḣ. Sep 6, 2017 at 12:43 • Or mo#2pḣ. Two ms seems wasteful Sep 6, 2017 at 14:01 • @H.PWiz o is confusing though, you're probably lucky it works there... Sep 6, 2017 at 14:03 • @EriktheOutgolfer, not lucky. It's fairly standard function composition Sep 6, 2017 at 14:07 # 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.  • There's also an atom ÆE which gives the exponent of each prime factor, making RÆEḢ€ Sep 6, 2017 at 15:39 • @miles Cool, thanks Sep 6, 2017 at 15:39 # Jelly, 3 bytes ọ€2  Try it online! # Pari/GP, 29 bytes n->[valuation(x,2)|x<-[1..n]]  Try it online! # 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. • 37 Sep 6, 2017 at 11:39 • @StewieGriffin Huh, I didn't know that could be done. Thanks! Sep 6, 2017 at 11:43 # Retina, 34 bytes .+$*
\B1
¶$1 +(1+)\1$+0
%r0\G


Try it online! Explanation:

.+
$*  Convert to unary. \B1 ¶$1


Create a triangle.

+(1+)\1
$+0  Start converting each row to base 2... %r0\G  ...but instead of completing the conversion, just count the trailing zeros. # 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¢  # Java 8, 86 + 267581797776 74 bytes n->{for(int i=0;i<n;System.out.println(n.toString(++i&-i,2).length()-1));}  Try it online! • Apparently you aren't allowed to output floats/doubles and have to output integers, so Math.log(i&-i++)/Math.log(2) should be (int)(Math.log(i&-i++)/Math.log(2)) instead. One thing you can golf however: i<n+1 can be i<=n. Sep 6, 2017 at 11:16 # 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. • õ_k +1 for cute faces. Sep 6, 2017 at 13:13 # Perl 6, 2717 15 bytes -2 bytes thanks to Brad Gilbert b2gills {(1..$_)».lsb}


Try it online!

• {(1..$_)».lsb} / {(1..$_)>>.lsb} Sep 6, 2017 at 18:17
• @BradGilbertb2gills Thanks! Sep 6, 2017 at 18:24

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! # 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 log2(k - (k & (k - 1))), if we were to work with [1, Q]. By mapping over [0, Q) instead, we modify the formula accordingly, log2(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.  # Pyth, 10 bytes mlec.Bd\1S  Try it here. # 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.  # 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)  # Perl 50 + 2 bytes perl -E'say+sprintf("%b",$_)=~s/.*1//r=~y===c for 1..shift'

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