Revision history [back]

What you are looking for in named the 2-adic valuation, which you can use as follows:

sage: a = 1260789648629655684939243820863888673792
sage: a.valuation(2)
10

You can see that it is much faster than factor:

sage: %timeit a.valuation(2)
The slowest run took 19.54 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 1.17 µs per loop

sage: %timeit a.factor()
10 loops, best of 3: 90.6 ms per loop

What you are looking for in In general, the largest k such that p^k divides n is named the 2-adic p-adic valuation, if n (when p is prime), which you can use as follows:

sage: a = 1260789648629655684939243820863888673792
sage: a.valuation(2)
10

You can see that it is much faster than factor:

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 282 ns per loop

sage: %timeit a.valuation(2)
The slowest run took 19.54 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 1.17 µs per loop

sage: %timeit a.factor()
10 loops, best of 3: 90.6 ms per loop

sage: a.odd_part()
1231239891239898129823480293812391283
sage: a/2^10
1231239891239898129823480293812391283

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 282 ns per loop

In general, the largest k such that p^k divides n is named the p-adic valuation if n (when p is prime), which you can use as follows:

sage: a = 1260789648629655684939243820863888673792
sage: a.valuation(2)
10

You can see that it is much faster than factor:

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 282 ns per loop

sage: %timeit a.valuation(2)
The slowest run took 19.54 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 1.17 µs per loop

sage: %timeit a.factor()
10 loops, best of 3: 90.6 ms per loop

In your specific case where p=2, since numbers are representes in binary in the computer, there is an even faster method that just has to remove trailing zeroes:

sage: a.odd_part()
1231239891239898129823480293812391283
sage: a/2^10
1231239891239898129823480293812391283

Which is even faster:

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 282 ns per loop

In general, the largest k such that p^k divides n is named the p-adic valuation if n (when p is prime), which you can use as follows:

sage: a = 1260789648629655684939243820863888673792
sage: a.valuation(2)
10

You can see that it is much faster than factor:

sage: %timeit a.valuation(2)
The slowest run took 19.54 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 1.17 µs per loop

sage: %timeit a.factor()
10 loops, best of 3: 90.6 ms per loop

In your specific case where p=2, since numbers are representes represented in binary in the computer, there is an even faster method that just has to remove trailing zeroes:zeros:

sage: a.odd_part()
1231239891239898129823480293812391283
sage: a/2^10
1231239891239898129823480293812391283

Which is even looks slightly faster:

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 282 ns per loop

In general, the largest k such that p^k divides n is named the p-adic valuation if n (when p is prime), which you can use as follows:

sage: a = 1260789648629655684939243820863888673792
sage: a.valuation(2)
10

You can see that it is much faster than factor:

sage: %timeit a.valuation(2)
The slowest run took 19.54 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 1.17 µs per loop

sage: %timeit a.factor()
10 loops, best of 3: 90.6 ms per loop

In your specific case where p=2, since numbers are represented in binary in the computer, there is an even faster method that just has to remove trailing zeros:

sage: a.odd_part()
1231239891239898129823480293812391283
sage: a/2^10
1231239891239898129823480293812391283

Which looks slightly faster:

faster that shifting the binary internal representation of a:
 
sage: %timeit a >> a.valuation(2)
The slowest run took 23.46 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 1.45 µs per loop

sage: %timeit a.odd_part()
The slowest run took 70.98 times longer than the fastest. This could mean that an intermediate result is being cached 
1000000 loops, best of 3: 282 ns per loop