[Community Puzzle] Regular polygons

https://www.codingame.com/training/medium/regular-polygons

Created by @Witman,validated by @nicola1,@Master_Zain and @Razovsky.
If you have any issues, feel free to ping them.

Nice puzzle, when b gets big, I get a time exceeded msg. No idea how to optimize !

We can think about eliminate power 2 elements using this form of div 2:
j>>=(int)(log2(j & -j));
as this will avoid one loop, it will help to resolve medium range test but not the last test.

try to make a library of distinct products of fermat prime numbers and then use it to count its multiply in provided range. (think out of the box)
vector dist_Fermat_primes={1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765};

The powers of 2 are solutions to the problem, so I already did that. Itâ€™s the last test that I can not pass !!

I already did that. I think the problem is in the way i loop over each number between a and b !!

After 3 days of thinking about the problem, I finally got all the tests workingâ€¦
My initial mistake was that although I read up about Fermat Primes (and that there are only 5 of them) I had the feeling that hard-coding them in my solution is somehow cheating So I tried checking numbers to see if they are Fermat primes. And although I did everything to avoid checking the same number twice it was still pretty slow.
Hardcoding the 5 Fermat primes in a Set and checking for every number between a and b whether it is divisible only by those 5 numbers and 2, got me through the medium test, but it was still awfully slow for the long range.
And as you suggest, the problem is looping through everything in between a and b. So my last version (and this one passes all the tests), constructs all the possible 31 product of Fermat primes and saves them in a Set (plus the number 1) and then I just go over each of them and keep them multiplying by 2 as long as the product is less than b. So instead of checking numbers, I actually just generate the correct ones.

2 Likes

Yes, that is what I mean, instead of checking, create all multiplies of fermat primes in provided range and then just count what was created, congratulation THaruca.

Now I see what you meant omarekik. That worked, thank you
But what if the last condition b<2^31 was to change? Can we calculate the product of Fermatâ€™s primes dynamically? hmmm

I pass test 1,2 ,3 and 4, but not the last test.
I find 483 instead of 494.
Anybody who can help?

Hi, there is something i donâ€™t understand.
The statement says :

A Fermat prime is a prime number of the form 2^(2^m)+1 . Where m is a natural number.

So imo the fermat primes are :
3 (m=0)
5 (m=1)
17 (m=2)
257 (m=3)
65537 (m=4)
4294967297 (m=5) but it is not a prime number.

And in the first test, we can see that 4 is the product of a power of 2 and a fermat prime.

Did I miss something ?

The description does not say all numbers of the form 2^(2^m)+1 are Fermat primes. My interpretation of what it wants to say is that if a number is prime and in the form 2^(2^m)+1, then it is a Fermat prime.

1 Like

My problem is : we have to found numbers which are product of a power of two and a Fermat prime.

â€ś4â€ť seems to be one of those numbers, I donâ€™t understand why.

The puzzle statement says:

the product of a power of 2 and any number of distinct Fermat primes (including none).

1 Like

Ok so it is a product of a power of two and a Fermat prime OR just a power of two ?
Thank you, I misunderstood that.

There is something else i misunderstood (thank you google translate !) : â€śanyâ€ť.
I understood â€śanyone of themâ€ť but with google it seems to mean â€śone or severalâ€ť.