15
\$\begingroup\$

This question already has an answer here:

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.

\$\endgroup\$

marked as duplicate by Sriotchilism O'Zaic, Mego code-golf Sep 7 '17 at 20:43

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    \$\begingroup\$ Possible duplicate of this or this (although both ask for more than just the sequence). \$\endgroup\$ – Erik the Outgolfer Sep 6 '17 at 10:34
  • 1
    \$\begingroup\$ Using the sandbox helps too :) \$\endgroup\$ – Erik the Outgolfer Sep 6 '17 at 10:40
  • 1
    \$\begingroup\$ @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] \$\endgroup\$ – Mr. Xcoder Sep 6 '17 at 10:54
  • 1
    \$\begingroup\$ @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). \$\endgroup\$ – Stewie Griffin Sep 6 '17 at 11:04
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Jonathan Allan Sep 6 '17 at 13:49

25 Answers 25

10
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ FWIW t+1-(t&-~t) is the same length with less tadpoles. \$\endgroup\$ – Jonathan Allan Sep 6 '17 at 14:01
  • \$\begingroup\$ @JonathanAllan Heh, I wonder how I missed that. I still like tildes and I will keep it that way though. \$\endgroup\$ – Mr. Xcoder Sep 6 '17 at 14:01
  • \$\begingroup\$ Or simply bin(t+1&~t). \$\endgroup\$ – nwellnhof Sep 6 '17 at 14:35
8
\$\begingroup\$

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

Mathematica, 29 bytes

#~IntegerExponent~2&~Array~#&

Try it online!

\$\endgroup\$
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

Haskell, 29 bytes

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

Try it online!

Recursively generate the infinite list l.

\$\endgroup\$
5
\$\begingroup\$

C (gcc), 49 44 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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)]. \$\endgroup\$ – Shaggy Sep 6 '17 at 16:30
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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("");
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ +1. Using an array is better than my printf approach. Combined with my new log2 solution, you could get this to 40 bytes. \$\endgroup\$ – nwellnhof Sep 6 '17 at 13:30
  • \$\begingroup\$ 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... \$\endgroup\$ – Toby Speight Sep 6 '17 at 14:15
  • \$\begingroup\$ 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. \$\endgroup\$ – Toby Speight Sep 6 '17 at 14:18
  • \$\begingroup\$ 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. \$\endgroup\$ – nwellnhof Sep 6 '17 at 14:23
  • \$\begingroup\$ I forgot that log2 is builtin in GCC - that really helps! Where's the predecrement you're referring to? I have a postdecrement (n--). \$\endgroup\$ – Toby Speight Sep 6 '17 at 14:27
4
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Seems optimal to me, had m#2mpḣ. \$\endgroup\$ – Erik the Outgolfer Sep 6 '17 at 12:43
  • \$\begingroup\$ Or mo#2pḣ. Two ms seems wasteful \$\endgroup\$ – H.PWiz Sep 6 '17 at 14:01
  • \$\begingroup\$ @H.PWiz o is confusing though, you're probably lucky it works there... \$\endgroup\$ – Erik the Outgolfer Sep 6 '17 at 14:03
  • \$\begingroup\$ @EriktheOutgolfer, not lucky. It's fairly standard function composition \$\endgroup\$ – H.PWiz Sep 6 '17 at 14:07
4
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ There's also an atom ÆE which gives the exponent of each prime factor, making RÆEḢ€ \$\endgroup\$ – miles Sep 6 '17 at 15:39
  • \$\begingroup\$ @miles Cool, thanks \$\endgroup\$ – Mr. Xcoder Sep 6 '17 at 15:39
3
\$\begingroup\$

Jelly, 3 bytes

ọ€2

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 29 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 37 \$\endgroup\$ – Stewie Griffin Sep 6 '17 at 11:39
  • \$\begingroup\$ @StewieGriffin Huh, I didn't know that could be done. Thanks! \$\endgroup\$ – Luis Mendo Sep 6 '17 at 11:43
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

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!

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Sep 6 '17 at 11:16
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ õ_k +1 for cute faces. \$\endgroup\$ – Mr. Xcoder Sep 6 '17 at 13:13
3
\$\begingroup\$

Perl 6, 27 17 15 bytes

-2 bytes thanks to Brad Gilbert b2gills

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

Try it online!

\$\endgroup\$
  • \$\begingroup\$ {(1..$_)».lsb} / {(1..$_)>>.lsb} \$\endgroup\$ – Brad Gilbert b2gills Sep 6 '17 at 18:17
  • \$\begingroup\$ @BradGilbertb2gills Thanks! \$\endgroup\$ – nwellnhof Sep 6 '17 at 18:24
2
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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

Pyth, 10 bytes

mlec.Bd\1S

Try it here.

\$\endgroup\$
0
\$\begingroup\$

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

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

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

\$\endgroup\$

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