# Introduction

The ruler sequence is the sequence of the largest possible numbers $$\a_n\$$ such that $$\2^{a_n}\mid n\$$. It is so-called because its pin plot looks similar to a ruler's markings: However, with a slight modification, we can also get a similar sequence. This sequence is $$\\{a_1,a_2,a_3,…\}\$$ where $$\a_n\$$ is the largest power of 2 such that $$\a_n\mid n\$$ (relevant OEIS).

The first 100 terms of this sequence are:

1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 64, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4


# Challenge

Your challenge is to do one of these three things:

• Take a positive integer $$\n\$$ as input and return the $$\n\$$th term of this sequence.
• Take a positive integer $$\n\$$ as input and return the first $$\n\$$ terms of this sequence.
• Output the sequence infinitely.

# Test Cases

12 -> 4
64 -> 64
93 -> 1
8 -> 8
0 -> (undefined behavior)


# Rules

• You may output the sequence in any convenient format - e.g. as a list or some other iterable or separated by any non-digit separator, as long as it is constant between all terms.
• You may output the term(s) in any convenient format - e.g. as an integer, as an integer string, as a float with the decimal part consisting of only zeros, ditto but as a string, or as a Boolean (True) if and only if the term is 1.
• You may choose to use either zero- or one-indexing.
• Standard loopholes are forbidden.
• Trailing whitespace is allowed.
• Please explain your answer. This is not necessary, but it makes it easier for others to understand.
• This is , so shortest code in bytes wins!
• Can you edit the set of terms so that it doesn't include the '0th' term? Doesn't seem like you've included it in your list of first 100 terms. Mar 11, 2021 at 2:57
• Good point. I'm on it Mar 11, 2021 at 2:59
• If you convert the number to binary, and count the index (starting at 0) from the right to the first 1 and then raise this index to the power of 2. Should work? Mar 11, 2021 at 3:20
• Close, you actually raise 2 to the power of the result. Other than that, that's actually the exact method used in my comment here. Two raised to the power of k (index) of the first 1 from the Right in the implicit input in binary Mar 11, 2021 at 3:23
• Though this challenge is well-written, I think it would be better if it didn't define and plot the ruler sequence $a_n$, then say actually you need to output $2^{a_n}$. Best to say the actual task itself at the start.
– xnor
Mar 11, 2021 at 7:21

# Python 2, 13 bytes

Takes a positive integer $$\ n \$$ as input and returns the $$\ n \$$th term of the sequence.

lambda n:n&-n


Try it online!

The largest power of $$\ 2 \$$ that divides $$\ n \$$ is also the lowest set bit. The bitwise magic is a bit difficult to explain, but it uses the fact that ~n + 1 in its binary representation produces the same lowest set bit as n.

### Python 2, 26 bytes

Outputs the sequence infinitely.

n=1
while 1:print-n&n;n+=1


Try it online!

### Python 2, 33 bytes

Takes a positive integer $$\ n \$$ as input and returns the first $$\ n \$$ terms of the sequence.

f=lambda n:n*and f(n-1)+[n&-n]


Try it online!

• Why this works
– user100947
Mar 13, 2021 at 3:09

# Regex (ECMAScript), 13 bytes

(x+?)(\1\1)*$ Try it online! Works by finding the smallest positive natural number that divides the input yielding an odd quotient. As such, this algorithm is generally applicable to any power of $$\p\$$, where $$\p\$$ is prime: find the smallest number that divides the input yielding a quotient that is not divisible by $$\p\$$. Takes its input in unary, as a sequence of x characters in which the length represents the number. The output is returned in capture group 1.  # No anchor needed, since every input N>=1 returns an output (x+?) # \1 = the smallest number >= 1 for which: (\1\1)*$  # \1 divides N and N / \1 is odd


Below is a demonstration showing how the algorithm above generalizes to other prime powers:

Largest power of $$\3\$$ that divides $$\n\$$ (17 bytes): (x+?)\1?(\1{3})*$ - Try it online! Largest power of $$\5\$$ that divides $$\n\$$ (21 bytes): (x+?)\1{0,3}(\1{5})*$ - Try it online!

Largest power of $$\17\$$ that divides $$\n\$$ (23 bytes): (x+?)\1{0,15}(\1{17})*$ - Try it online! # Haskell, 19 bytes l=1:do x<-l;[2*x,1]  Try it online! Generates an infinite list. This list is defined recursively using the property that the list is unchanged if we double each value and intersperse 1's at every other position including at the start. So, we start the list with a 1, then iterate through the list itself, each time producing the doubled number followed by a 1. Haskell's laziness allows this kind of self-reference. 1 <- initial value 2 \ 1 doubled 1 / 4 \ 2 doubled 1 / 2 \ 1 doubled 1 / 8 \ 4 doubled 1 / 2 \ 1 doubled 1 / ...  # Haskell, 10 bytes gcd=<<(2^)  Try it online! Outputs the n'th term. Equivalent to f n=gcd n(2^n). We take the greatest common divisor of n and a large power of 2. • Being only familiar with Haskell, I understand what l=1:do x<-l;[2*x,1] is doing conceptually, but not syntactically. Do you mind elaborating on the mechanics? Mar 11, 2021 at 14:05 # 05AB1E, 5 bytes LoÖOo  Try it online! Takes $$\n\$$ as input, outputs the $$\n\$$th term ## How it works LoÖOo - Full program. Input n L - Range from 1 to n o - Raise 2 to the power of each Ö - Yield 1 if divisible by n, for each O - Sum, counting the 1s o - Raise 2 to the power  # 05AB1E, 2 bytes (&  Try it online! Boring bitwise solution. Calculates the bitwise AND of $$\n\$$ and $$\-n\$$ • you need to use the bathroom? Mar 11, 2021 at 3:08 • @Lyxal NoÖOo :P Mar 11, 2021 at 3:10 • Nice job! My idea was bR1ko, but this deserves more attention for its audible appeal. +1 Mar 11, 2021 at 3:10 • @Makonede I did know, but my phone doesn't, so insists on em dashes :/ Mar 11, 2021 at 3:16 • Óнo works for 3 bytes (2**the exponent of 2 in the prime factorization). And, borrowing from xnor's Haskell answer, o¿ is another 2-byter. – ovs Mar 11, 2021 at 12:43 # Jelly, 2 bytes N&  Try it online! Takes $$\n\$$ as input, outputs the $$\n\$$th term ## How it works • Nice! The shortest possible 05AB1E answer seems to be 5 bytes too. Mar 11, 2021 at 2:44 • nvm, it's 2 bytes that's the shortest in 05AB1E... also, this is pretty much identical to the 05AB1E 2-byter. Mar 11, 2021 at 3:14 # JavaScript (V8), 18 bytes f=n=>n&1||2*f(n/2)  Try it online! # C (gcc) x86, 14 bytes Takes a positive integer $$\n\$$ as input and returns the $$\n\$$th term of the sequence. f(n){n&=-*&n;}  Try it online! f(n){*&n&=-n;}  Try it online! Same bitwise formula as used ChartZ Belatedly, dingledooper, and many more. Thanks to Noodle9 for the nice idea of showing ✓ or ✕ in the TIO code depending on correctness; I haven't done that before, but might use it some more in the future. Uses the very common code golf hack of avoiding the non-golfy return keyword (by taking advantage of the fact that results to most calculations get stored in the accumulator, the same register that is used for return values), but without resorting to use of global variables or fake function parameters. This is done by taking the address of n and then dereferencing that address. This of course requires the default optimization level -O0. Using -O1 will break gcc return avoidance hacks (and in clang, they don't even work at -O0). In 32-bit x86, this compiles to the following ([ebp+0x8] is the n parameter):  mov eax,DWORD PTR [ebp+0x8] neg eax mov edx,eax mov eax,DWORD PTR [ebp+0x8] and eax,edx mov DWORD PTR [ebp+0x8],eax  Whereas f(n){n&=-n;} doesn't work because it compiles to the following, which acts like f(n){return-n;}:  mov eax,DWORD PTR [ebp+0x8] neg eax and DWORD PTR [ebp+0x8],eax  An essentially equivalent result occurs in x86-64 and MSP430. # C (gcc) - many other platforms, 12 bytes f(n){n&=-n;}  On many architectures other than x86, this actually works: This is case in point for why I hate the gcc return avoidance hack so much. It's not merely reliant on -O0, and not only uses undefined behavior in general, but it's not even portable within different architecture targets of gcc itself. Here it is failing to work as desired on x86 and MSP430, contrasted with the *& forcing it to work: There is no guarantee that the same undefined behaviors will still behave the same way in future versions of gcc (and/or the toolset) even on the same architecture. This is why I prefer to post "C (clang)" or "C (gcc -O1)" answers instead of "C (gcc)". If the fragile undefined behavior hacks work, you have to use them in "C (gcc)" answers to stay competitive with other "C (gcc)" answers. In any case, people posting answers that use this hack should probably call the language "C (gcc) x86" instead of "C (gcc)". # C (gcc), 37 bytes Outputs the sequence infinitely. main(n){for(;;)printf("%d ",-n&n++);}  Try it online! Saves 1 byte by using tab (which can be used literally) instead of newline (which would require \n). Takes another shortcut by using the first parameter of main(), the command line argument count, which is 1 when there are no command line arguments (because the pathname of the executable is treated as the first argument, at index 0). # C (gcc), 52 bytes Takes a positive integer $$\n\$$ as input and outputs the first $$\n\$$ terms of the sequence. main(n){for(scanf("%d",&n);n;)printf("%d ",-n&n--);}  Try it online! Abuses a loophole by printing the first $$\n\$$ terms in descending instead of ascending order. Without this, it would be 57 56 bytes: main(i,n){for(scanf("%d",&n);n--;)printf("%d ",-i&i++);}  Try it online! # C (gcc), 53 bytes Takes a positive integer $$\n\$$ as input and returns the first $$\n\$$ terms of the sequence. f(n){int*m=malloc(n*4);for(;n;)m[n]=-n&n--;n=(int)m;}  Try it online! 4 is sizeof(int). m[n]=-n&n--; works because by the time m[n] evaluates, n has already been decremented; it's equivalent to m[n-1]=-n&n;--n;. The array returned is allocated by this function, and must be free()ed after use. # Octave / MATLAB, 28 23 bytes 5 bytes off thanks to @Giuseppe! @(n)2^sum(factor(n)==2)  Try it online! ### Explanation @(n) % Define anonymous function of n factor(n) % Vector of prime factors of n, possibly repeated ==2 % Compare each element with 2. Gives 1 (true) or 0 (false) sum( ) % Sum 2^ % 2 raised to that  # J, 6 4 bytes AND-  Try it online! -2 thanks to FrownyFrog Just because expressing dingledooper's idea in J is nice.... • ...- The whole thing is a J hook, so that the verb ... will receive the input and its negative as the left and right argument. • AND Elementwise "and" on the bits. • You can also do AND- Mar 25, 2021 at 0:53 # PowerShell, 19 bytes param($n)$n-band-$n


Try it online!

It does:

• Take a positive integer $$\n\$$ as input and return the $$\n\$$th term of this sequence.

Thanks to @xnor

# Scala, 8 bytes

n=>n& -n


Try it online!

dingledooper's idea works also in Scala

• Apparently an alternate 8 byte solution is n=> -n&n. Why don't n=>-n&n and n=>n&-n work? Are =>- and &- being parsed as different operators? Mar 11, 2021 at 9:27
• When Scala finds a sequence of characters that can be part of an operator, it tries to make one operator of it. You need a space to separate them. Mar 11, 2021 at 9:30

# R, 3433 32 bytes

Edit: -1 byte thanks to Giuseppe

function(n,t=2^(n:0))t[!n%%t]


Try it online!

Constructs a series t of powers of 2 in reverse (t=2^(n:0)), then gets the first element () for which n MOD t is zero ([!n%%t]).

This works in principle for any n, but is limited by floating-point accuracy and - more obviously - calculation time and memory. A faster and less memory-hungry (but 7 byte longer) version using the same approach would be: function(n,t=2^(0:log2(n)))max(t[!n%%t]) (try it).

# R, 34 bytes

f=function(n)if(n%%2,1,2*f(n/2))


Try it online!

An alternative recursive approach (ported from user81655's answer) is 1 byte longer, but runs significantly faster and so can actually be tested for very large numbers.

# Wolfram Language (Mathematica), 11 bytes

GCD[2^#,#]&


Try it online!

# 05AB1E, 8 6 bytes

ÝoʒÖ}θ


Try it online!

Turns out I'm way too used to Vyxal. -2 thanks to Makonede

## Explained

ÝoʒÖ}θ
Ýo      # 2 ** range(0, input) // vectorised
ʒÖ}   # filter(lambda x: x % input == 0, ^)
θ  # ^[-1]

• You can golf off 2 bytes by removing the Is. You're pushing the input to the top and swapping the current element in the list to the top, however implicit input's default behavior is acting as if it was on the bottom of the stack if there are less than <arity of operator> elements on the stack. Mar 11, 2021 at 2:58
• @Makonede that's a result of functions in Vyxal re-using arguments as implicit input if nothing is avaliable Mar 11, 2021 at 3:01
• Beat you to 5 Mar 11, 2021 at 3:06
• lol. BTW, you made a couple typos; use should be used, and 2 ** range(0, input) should be (2**i for i in range(input()+1)) or map(lambda x:2**x,range(input()+1)). Mar 11, 2021 at 3:07
• @Makonede 2 ** range... is intentional. It assumes vectorisation Mar 11, 2021 at 3:08

# Vyxal, 2 bytes

N⍲


Try it Online!

Just a port of the bitwise stuff.

# JavaScript (Node.js), 7 bytes

n=>n&-n


Try it online!

dingledooper's solution (for Python) adapted to JavaScript.

# Java (JDK), 7 bytes

n->n&-n


Try it online!

dingledooper's solution (for Python) adapted to Java

# R, 24 bytes

function(n)bitwAnd(n,-n)


Try it online!

While it's good to have a variety of answers using different techniques, the actual shortest in each language should be represented too. As is the case in most languages, I think the bitwise hack is the shortest here.

• This is probably indeed the shortest, but I think it's worth pointing-out that it doesn't actually work for large numbers: try it. Any number that is internally represented as a floating-point number will fail... Mar 11, 2021 at 10:43
• @DominicvanEssen That's an interesting point. I'd also point out that your 33 byte answer doesn't just fail due to slowness, it runs out of memory. Though I suppose it would still work with unlimited memory, whereas the bitwise version here wouldn't. Mar 11, 2021 at 10:46
• Yes, you're right: I've updated my answer to point this out, too. Mar 11, 2021 at 10:52

# Groovy, 8 bytes

{it&-it}


Try it online!

dingledooper's Python solution, translated to Groovy

# Julia, 18 bytes (recursive approach)

!n=n%2>0||2*!(n/2)


Try it online!

# Julia, 7 bytes (bitwise approach)

n->n&-n


Try it online!

# C (gcc), 15 bytes

a;f(n){a=n&-n;}


Try it online!

Inputs a positive integer $$\n\$$ and returns $$\2^a\$$ which is the largest power of $$\2\$$ such that $$\2^a\mid n\$$.

• Why not f(n,a){a=n&-n;}? That is a bit cleaner, avoiding the use of global variables. Mar 11, 2021 at 9:42
• @Deadcode Same length and purely a matter of personal preference whether you consider a fake function parameter "cleaner" than using a global variable. And who worries about cleanliness anyway in code golfing? T_T Mar 11, 2021 at 9:45
• -1 byte avoiding the need for either global variables or fake parameters. Mar 11, 2021 at 10:49
• @Deadcode So you took my answer and my TIO tests and reposted them with your -1 byte golf? T_T Mar 11, 2021 at 12:50
• Oops! You're quite right, and now I understand why you reacted how you did. I should've said something like "I found a way to get -1 byte without a global value or fake parameter, and felt it was worth posting my own answer:" Mar 11, 2021 at 15:58

# Japt, 3 bytes

U is the first input, same bitwise approach as many other answers already covered.

&-U


Try it out here.

• &n for 2 bytes. Mar 11, 2021 at 19:18

# Perl 5, 15 bytes

sub($n){$n&-\$n}


Try it online!

dingledooper's Python solution, translated to Perl 5

# SNOBOL4 (CSNOBOL4), 72 bytes

	N =INPUT
X =1
I	J =N / X
X =X * 2	EQ(REMDR(J,2))	:S(I)
OUTPUT =X
END


Try it online!

	N =INPUT				;* read input
X =1					;* set X =1
I	J =N / X				;* set J to N / X
X =X * 2	EQ(REMDR(J,2))	:S(I)	;* If J is divisible by 2, double X and goto I, else
OUTPUT =X				;* print X and exit
END


# Factor, 14 bytes

[ dup 2^ gcd ]


Try it online!

J42161217's and xnor's approach: GCD with a large power of 2.

# Factor, 18 bytes

[ dup neg bitand ]


Try it online!

# Factor, 18 bytes

[ factor-2s . 2^ ]


Try it online!

There's a built-in that is supposed to do most of the job: factor-2s, which takes a positive integer n and returns [ exponent-of-2 odd-part ] on the stack. Unfortunately the power of 2 is the secondary return value (so you need to discard the top with .) and it is the exponent (not the power of 2 itself) so 2^ is needed.

# Factor, 5650 46 bytes

• Saved 6 bytes thanks to @Bubbler!
• Saved 4 bytes thanks to @chunes!
[ 2 over [0,b] n^v [ 2 * mod 0 > ] with find ]


Try it online!

# Factor, 53 bytes

[ 0.5 [ [ 2 / ] [ 2 * ] bi* over dup floor = ] loop ]


Try it online!

• I don't think this is valid as it outputs errors to STDOUT, and therefore doesn't give valid output. Mar 25, 2021 at 0:49
• Both math.functions and math.ranges are available by default. 2^ is a shorthand for 2 swap ^. Mar 25, 2021 at 0:50
• @Makonede It is just a problem with the TIO environment, and stray output on STDOUT is not a problem since it is a function submission (everything is OK as long as the result is returned on the top of the stack). Mar 25, 2021 at 0:52
• @OriginalOriginalOriginalVI The second one is not valid as-is. (Did you forget to move 6 and call . to header/footer?) Also, to suppress the Quotation's stack effect does not match call site error at the end of the program, you can put clear at the end of the footer. Mar 25, 2021 at 0:54
• 2 over [0,b] n^v is shorter than dup [0,b] [ 2^ ] map. Apr 2, 2021 at 1:07

# Excel, 29 24 bytes

-5 bytes thanks to @TaylorScott

A port of Dingledooper's answer to Excel.

=BITAND(2^47+A1,2^47-A1)


## Original much worse answers, 29 bytes

[A2]=2^47+A1*{1;-1}
[A4]=BITAND(A2,A3)


Had to use 2 cells because BITAND requires 2 arguments. The formula in A2 spills to A3. Works up to 2^47 - 1. Can save a byte changing 2^47 to 8^9. This lowers the range to 2^27-1.

## Excel (one cell), 35 bytes

=2^SUM(1*(MOD(A1,2^(ROW(1:47)))=0))


This is what I came up with on my own. Works up to 2^41.

Try them online

• Why not =BitAnd(2^47+A1,2^47-A1)? Apr 3, 2021 at 1:40
• That is a good point. I guess sometimes you just get stuck on a train of thought. Apr 3, 2021 at 5:21

# Scala, 43 bytes

n=>Stream.iterate(1)(_*2).find(n%_>0).get/2


Try it in Scastie!

# 05AB1E, 2 bytes

o¿


Try it online!

o¿  # full program
¿  # greatest common divisor of...
# implicit input...
¿  # and...
o   # 2 to the power of...
# implicit input
# implicit output


# APL (Dyalog Unicode), 16 bytes

Nth Term

{2*(⊥⍨~)2⊥⍣¯1⊢⍵}
2* ⍝ exponentiation
⊥⍨~ ⍝ number of trailing zeros
2⊥⍣¯1⊢ ⍝ bit vector conversion
⍵ ⍝ argument


Try it online!

# APL (Dyalog Unicode), 21 bytes

First N Terms

{2*(⊥⍨~)∘(2⊥⍣¯1⊢)¨⍳⍵}
2* ⍝ exponentiation
⊥⍨~ ⍝ number of trailing zeros
∘ ⍝ curry
2⊥⍣¯1⊢ ⍝ bit vector conversion
¨ ⍝ each
⍳⍵ ⍝ range of 1–n


Try it online!

• This is 16 bytes, not 14. Apr 2, 2021 at 22:17
• And your second one is 21… Apr 2, 2021 at 22:28
• Sorry, I was under the impression that the enclosing brackets or parentheses didn't count towards the total. Genuinely wasn't trying to pull a fast one on anyone. Guess I'm going to have to update all of my other answers as well. Apr 2, 2021 at 22:28
• @Makonede Thanks for pointing that out, no one had mentioned it on my other answers. Apr 2, 2021 at 23:27
• No problem. [filler] Apr 2, 2021 at 23:28