[v3] 1-liner: count odd divisors (the naive way) clear solution for Count Consecutive Summers by Phil15 - python coding challenges

Enable Javascript in your browser and then refresh this page, for a much enhanced experience.

[v3] 1-liner: count odd divisors (the naive way) solution in Clear category for Count Consecutive Summers by Phil15

# Third version: count odd divisors
# Well I saw that what we want is equal to the number of odd divisors of n so...
count_consecutive_summers = lambda n: sum(not n%k for k in range(1, n+1, 2))

Dec. 5, 2018

Comments:

megaexception on Feb. 2, 2019, 3:31 p.m.
wow, it's really unexpected, but clearly very cool. your solution is very brief, concise, and about five times faster than mine. kudos!

fenryxo on Feb. 7, 2019, 9:57 a.m.
I really smart solution :-)

vlad.bezden on Feb. 16, 2019, 8:29 p.m.
Indeed, very smart. The only disadvantage of it that it has O(n/2), and for large numbers it's slow. In my solution <a href="https://py.checkio.org/mission/count-consecutive-summers/publications/vlad.bezden/python-3/first/">https://py.checkio.org/mission/count-consecutive-summers/publications/vlad.bezden/python-3/first/</a> running profiler I'm getting between 10-20 times performance boost for num = 1000, for num = 10000 I'm getting 30 times performance boost.

Phil15 on Feb. 21, 2019, 9:24 a.m.
I agree, this is why there is `(the naive way)` in the title and why this solution is not in speedy category. I proposed another solution in speedy category (also based on counting odd divisors, but in a better way), much better for large composite numbers.

Masakhwe on March 12, 2019, 9:16 p.m.
I think a faster solution based on the same idea would be use of list compression i.e return len([x for x in range(num + 1) if x % 2 != 0 and num % x == 0])

Phil15 on March 13, 2019, 8:29 a.m.
What's next is totally equivalent to the next line, so you compute the entire list before to take the length of it, so not memory friendly for big numbers. <pre class='brush: python'>L = [x for x in range(num + 1) if x % 2 != 0 and num % x == 0] return len(L) </pre> My solution have limited memory, it's like that, so just integers (and the range object) in memory. <pre class='brush: python'>total = 0 for k in range(1, n+1, 2): total += not n % k </pre> If we want odd numbers, range(1, n+1, 2) is simplier than discard even number from range(n+1). And just to be clear, I use comprehension thing too. It's like <pre class='brush: python'>gen = (not n%k for k in range(1, n+1, 2)) # generator, so it's not a list, I compute element one by one to give them # to what's next, here the sum. return sum(gen) </pre>

Ylliw on April 12, 2019, 4:34 p.m.
Hi Phil15, Hi vlad.bezden, I just published my solution to it. It's definitly a short code (85 chars compared to 49 chars for yours) a and on my Pc it's even faster than the one of vlad.bezden. I do think it's quite memory efficient, even if doing the sum on the go, would save memory, but as I am only using a sqrt(n) table, benefit is negligeable. <a href="https://py.checkio.org/mission/count-consecutive-summers/publications/Ylliw/python-3/85-chars-and-still-probably-fastest-code/">https://py.checkio.org/mission/count-consecutive-summers/publications/Ylliw/python-3/85-chars-and-still-probably-fastest-code/</a> Program runs in about O(n^0.8). Technically I would have expected it to be in O(n^0.5) but computation time increase it a little bit.

froot123 on April 11, 2019, 7:47 p.m.
incredible.. god, is it u?

Chnelik_Sebastian on Sept. 26, 2019, 7:58 p.m.
Great idea! finally, math wins xD . About your fast solution : <pre class='brush: python'>gen = (not n%k for k in range(1, n+1, 2)) # generator, so it's not a list, I compute element one by one to give them # to what's next, here the sum. return sum(gen) </pre> You do not need to check with all the odds either. Just from the first one; 3. So, what do you think about: <pre class='brush: python'>gen = (not n%k for k in range(1, (n+1)//3, 2)) return sum(gen)+(n%2)+(n!=1) </pre>

Phil15 on Sept. 27, 2019, 7:42 a.m.
You didn't test it. I did for all tests on this mission, and for 23 (to have an odd prime number). * Work for 42, 99, 1, 15, 105, 225, 315, 1575, 2835. * Doesn't work for 92, 32, 128, 1024, 4096, 23. List of input/answer here: `[(42, 4), (99, 6), (1, 1), (92, 2), (15, 4), (32, 1), (105, 8), (128, 1), (225, 9), (315, 12), (1024, 1), (1575, 18), (2835, 20), (4096, 1), (23, 2)]`. My fix: <pre class='brush: python'>def count_consecutive_summers(n): gen = (not n%k for k in range(1, n//2 + 1, 2)) # ~~~~~~~~ # n%2 == 1 if and only if n is an odd (divisor of n). # Otherwise, we need to count other divisors, it can be up to n//2 (included), 21 divides 42 for example. return sum(gen)+n%2 # ~~~~~~ </pre> Or to fit your `//3`. <pre class='brush: python'>def count_consecutive_summers(n): gen = (not n%k for k in range(1, n//3 + 1, 2)) # ~~~~~~~~ # 1 if n is odd (n is an odd divisor), else n/2 is a divisor, is it odd? # Then next candidate is n/3, so range up to n//3 included. return sum(gen)+(1 if n%2 else n//2%2) # ~~~~~~~~~~~~~~~~~~~~~~ </pre> We probably can continue this way but it's gonna be not clear at some point. This published solution is not about speed, it is naive. For something faster, click <a href="https://py.checkio.org/mission/count-consecutive-summers/publications/Phil15/python-3/4th-fast/">here</a>. Well, my comment was just to say that `sum(gen)` is better than `sum(list)`, we don't need to list anything, generator is memory friendly, lists are not, that's all. So <pre class='brush: python'>count_consecutive_summers=lambda n:sum(not n%k for k in range(1,n//2+1,2))+n%2 count_consecutive_summers=lambda n:sum(not n%k for k in range(1,n//3+1,2))+(n//2%2,1)[n%2] </pre>

Chnelik_Sebastian on Oct. 7, 2019, 10:40 p.m.
<blockquote> You didn’t test it. I did for all tests on this mission, and for 23 (to have an odd prime number). Work for 42, 99, 1, 15, 105, 225, 315, 1575, 2835. Doesn’t work for 92, 32, 128, 1024, 4096, 23. </blockquote> Oh, i just tried it with the Checkio automatic, seems i was lucky. Thank you ) <blockquote> Well, my comment was just to say that sum(gen) is better than sum(list), we don’t need to list anything, generator is memory friendly, lists are not, that’s all. </blockquote> It was clear. Just wanted to improve the code

MaxLviv on Nov. 8, 2019, 6:24 a.m.
Kind of magic for me. Great code.

-dead-inside- on Nov. 8, 2019, 8:49 a.m.
Awesome, at least now I know what I can just count odd divisors, if numbers are small. :)

tssrkt777 on Oct. 4, 2021, 10:37 a.m.
Solutions of math teachers are always amazing.)

StefanPochmann on April 18, 2024, 11:24 a.m.
What's the explanation for counting odd divisors? Without that, this isn't "clear" at all.

Phil15 on April 18, 2024, 3:27 p.m.
Fair enough but after 5 years I don't remember and I don't know where is this damn paper that I mentioned in another solution ("I proved on paper that what we want is equal the number of odd divisors of n."). I guess it "was too large to fit in the margin". The start is probably something like this. <pre class='brush: python'>num = s + (s+1) + ... + (s+n) = s * (n+1) + (1+2+3+...+n) = s * (n+1) + n*(n+1)/2 n+1 is probably an odd divisor for this to work, but there are edge cases to consider. </pre> I'm sure I did solve this properly but right now I don't know the details and I'm not willing to pass as much time on this as I did before. The code is clear, the explanation is definitely missing and this is not "entirely clear" at all, sure.

StefanPochmann on April 18, 2024, 5:33 p.m.
Hmm, sad. The n+1 in that is the length of the sum, but I don't think the sum lengths are the odd divisors. For example, the odd divisors of 7 are 1 and 7, but the sum lengths are 1 and 2 (the sums are sum([7]) and sum([3,4])).

Mine

0 %

PyCharm The Python IDE for Professional Developers. Enjoy productive Python, web and scientific development with PyCharm. Download it now!