Problem 273

[TripleM]

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.

[quilan]

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

[zwuupeape]

It doesn't need more than high school algebra

[Shahzaad]

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

[quilan]

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.

[Jochen_P]

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

[hk]

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?

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

[elendiastarman]

Would this be better?

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

I second this.

[stijn263]

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

[elendiastarman]

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

[hk]

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

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

[stijn263]

Problem 273 (View Problem)

[Diadem]

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.

[hk]

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.

[elendiastarman]

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

[Diadem]

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

[LarryBlake]

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

[Doraki]

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

[Jochen_P]

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 ]

[LarryBlake]

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