Project Euler Forum

Problem 273 (View Problem)

The last sentence is pretty ambiguous in this problem:

... for all squarefree N only divisible by primes of the form 4k+1 less than 150.

This could mean N has to be less than 150, or each prime divisor must be less than 150. I presume the latter is what is being asked, but both are valid interpretations.

This would be (slightly) better (though still not perfect):

... for all squarefree N only divisible by primes that are of the form 4k+1 and less than 150.

Aye, that's what I understood it to mean. Of course, this also means I've gotta use MATHS to figure out how to handle the mammoth S(2515181402329213060851342805). Not going so well so far...

It doesn't need more than high school algebra

You only have to check 2 ^ 16 - 1 values though...

Oooh, this is interesting. Apparently I've overlooked something trivial, because I'm going super-crazy on advanced analysis, etc. Time to re-evaluate things.

Edit: Well uhh... I only wish I could have been as intelligent as that dude from 7th-century AD. He certainly makes this problem easy, now doesn't he? I'll solve it in the morning.

... all squarefree N only divisible by primes of the form 4k+1 less than 150.

IMO there are only 136 such numbers, the smallest is 5 and the largest is 137*149=20413

OR are none-prime factors considered irrelevant ?

TripleM wrote:Problem 273 (View Problem)

The last sentence is pretty ambiguous in this problem:

... for all squarefree N only divisible by primes of the form 4k+1 less than 150.

This could mean N has to be less than 150, or each prime divisor must be less than 150. I presume the latter is what is being asked, but both are valid interpretations.

This would be (slightly) better (though still not perfect):

... for all squarefree N only divisible by primes that are of the form 4k+1 and less than 150.

Would this be better?

hk wrote:Would this be better?

for all squarefree N only divisible by primes of the form 4k+1 with 4k+1<150.

I second this.

Either one is fine by me, but 150 is nicer than 38...

stijn263 wrote:

for all squarefree N only divisible by primes of the form 4k+1 with k < 38.

Changed it in "with 4k+1<150".

Problem 273 (View Problem)

I read the problem this morning, and interpreted it in the first meaning, thinking "Huh, that's easy. Even super-naieve brute force would require only 150^3 steps". I come back tonight to actually do it (having been away during the day) and suddenly the problem got a lot harder. A lot more interesting too though.

It seems that this http://mathworld.wolfram.com/k-Subset.html might be helpful to you for both Problem 268 (View Problem) and this one.

Actually...all I used was the 7th century AD guy's result and got the answer in about 1-2 minutes with ~1.2 gigs of memory used. I maxed out my memory when I didn't treat the last prime as the last... :/ It was a fun one and I definitely learned something new.

I came shockingly close to the difficulty of this problem when I explained the difficulty scale... O.O

hk wrote:It seems that this http://mathworld.wolfram.com/k-Subset.html might be helpful to you for both Problem 268 (View Problem) and this one.

I'm familiar with that. But I don't see how it applies for either problem. There are 16 primes below 150 of the form 4k+1. So the number of products of 3 such primes is 16 choose 3. But that doesn't help you much because they are not equal. 5*13*17 != 29 * 37 * 41. Same story with the products of primes for 268.

There are only 2^16 products in total. One can easily sum over those. But the biggest ones go well over the int64 limit. So then brute forcing for integer (a,b) such that a^2 + b^2 = n is not going to work.

So you'll need a smarter method. I think I have the right one (going to implement it now) but I can't discuss that without giving away too much of the solution

Jochen_P wrote:

... all squarefree N only divisible by primes of the form 4k+1 less than 150.

IMO there are only 136 such numbers, the smallest is 5 and the largest is 137*149=20413

OR are none-prime factors considered irrelevant ?

That would be the largest N of two factors. However, I understood it be any number of factors of the qualifying primes. Am I correct?

Also, Jochen's question: are non-prime factors allowed?

We don't care about non-prime divisors :

It's all the squarefree N whose prime factors are all of the form 4k+1 with 4k+1 < 150

I think what I meant was the meaning of "only divisible by primes of the form 4k+1".
Any other number product of at least 3 of this primes has other factors which are none-prime.
So, my question was aimed in the direction does "only divisible by primes of" mean it is ok if they are divisible by non-primes or is it strictly meaning "only Prime factors of the form 4k+1 are allowed".

In latter case it would indeed be only 136 numbers to check and not 2^16-1.


[hope my English skills are good enough to make my question not totally confusing

[edit: Doraki answered the question in the mean time ]

Okay, but the largest N is not 137 * 149. It's 5 * 13 * 17 * 29 ... 137 * 149, which is very large.

Your English is fine. Viel besser aus mein Deutsch. (That sentence probably shows it.)