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
sage: a >> a.valuation(2) # shift
1231239891239898129823480293812391283
Which looks slightly 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