Project Euler Forum

Could I get a hint on problem 193 (find all square free numbers below 2^50). I've tried to come up with lots of solutions (combinatorics / dynamic programming / recurrenses) but nothing seems to be fast enough.

Just do it as fast as you possibly can and then learn from the forum how you could do it faster.

Well it's probably too slow to do within any reasonable time (about a day or so). Just wondered if anyone had any small hint.

I'm afraid any hint would be too big.

Well, at least, should I continue on the same way as before? Or try to come up with something new? I've thinking about doing something with the primes below 2^25 but it stills gets too slow. I suppose I need to use some combinatorics, since the number of squarefree integers is pretty large (I cant "create" them)

You could PM me an outline of your ideas and I'd look which are useful.

Thanks, Ima write them down as soon as I can and send them!

I am still far from solving problem 193

But I hope it is OK to ask the following.

Can someone confirm that the count
of the squarefree numbers below
k = 40000000 (below 40 million) is 24317053.

And is the count of squarefree numbers
below k = 15000000 (below 15 million) 9118889 ?

Thanks in advance.

I can confirm both of your findings, so your on the right track

Thank you.

My program gives the right answer for 4e7 and 15e6 (as posted above), as well as for some other small numbers I tested (and counted the number of squarefrees manually), but it doesn't work for 2^50...

can anyone confirm these?

652756723 for 2^30
668422917419 for 2^40

Thanks...

Nevermind, it worked... turns out result was off by 1.
Can anyone still confirm the numbers above? Not sure what caused them to be off by 1 sometimes and sometimes not...

EDIT: I think I found it... The 2^30 was also off by 1 (652756722) right?

Yes, 652756722 for 2³⁰ and 668422917419 for 2⁴⁰ are correct.

Hi, I got 652756722 for 2³⁰ and 668422917419 for 2⁴⁰ too, but I'm getting a wrong answer for 2⁵⁰.

Can anybody tell me if is 21389533354941 correct for 2⁴⁵?

Thanks!

That's not what I get. Think about what could go wrong with your method for higher limits. Overflow? Or something else? Good luck!

Yes! It was overflow!

Thank you!