Problem 193

Dennen · Post by **Dennen** » Tue May 13, 2008 2:01 am

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.

rayfil · Post by **rayfil** » Tue May 13, 2008 5:24 am

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

Dennen · Post by **Dennen** » Tue May 13, 2008 6:05 am

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.

daniel.is.fischer · Post by **daniel.is.fischer** » Tue May 13, 2008 1:31 pm

I'm afraid any hint would be too big.

Dennen · Post by **Dennen** » Tue May 13, 2008 3:29 pm

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)

daniel.is.fischer · Post by **daniel.is.fischer** » Tue May 13, 2008 4:49 pm

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

Dennen · Post by **Dennen** » Tue May 13, 2008 5:09 pm

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

sedefcho · Post by **sedefcho** » Mon Jun 02, 2008 12:26 am

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.

stijn263 · Post by **stijn263** » Mon Jun 02, 2008 10:26 am

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

sedefcho · Post by **sedefcho** » Mon Jun 02, 2008 12:03 pm

Thank you.

Assato · Post by **Assato** » Sat Apr 25, 2009 2:16 am

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...

Assato · Post by **Assato** » Sat Apr 25, 2009 2:20 am

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?

Tommy137 · Post by **Tommy137** » Sat Apr 25, 2009 10:47 am

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

axelbrz · Post by **axelbrz** » Tue Sep 08, 2009 5:56 am

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!

stijn263 · Post by **stijn263** » Tue Sep 08, 2009 10:07 am

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

axelbrz · Post by **axelbrz** » Tue Sep 08, 2009 2:31 pm

Yes! It was overflow!

Thank you!

Project Euler Forum

Problem 193

P193 Hint on squarefree numbers

Re: Hint on squarefree numbers

Re: Hint on squarefree numbers

Re: Hint on squarefree numbers

Re: Hint on squarefree numbers

Re: Hint on squarefree numbers

Re: Hint on squarefree numbers

Problem 193

Re: square free

Re: square free

Re: Problem 193

Re: Problem 193

Re: Problem 193

Re: Problem 193

Re: Problem 193

Re: Problem 193