Problem 273

[Jochen_P]

Thank you,

hmm, let's take 5*13*17 : the proper divisors are [1, 5, 13, 17, 65, 85, 221]
And now take the sentence "Find S(N), for all squarefree N only divisible by primes of the form 4k+1 with 4k+1 150."

That would disqualify 5*13*17 and all above... ehm, ... oh well, it would also disqualify all other products as 1 is always a divisor and definetly not prime. So the sentence should be read like "Find S(N), for all squarefree N only divisible by primes of the form 4k+1 with 4k+1 150."

All right, all clear now, I rest my case

[Smaug]

That is a good point IMO - the wording should be changed from

... for all squarefree N only divisible by primes of the form ...

to: '... for all squarefree N whose only prime factors are of the form... '

[Slartibartfast]

Thanks for the clarification Jochen_P. I was doing the same as quilan until you pointed out that the product of more than two primes is divisible by a non-prime (doh!).
I got the 16 primes, that's easy. Was initially checking 120 numbers 'til I realised that the additional 16 were the individual primes (doh!^duh!: that's a very big number -- almost as large as the product of all 16 primes).
So, now I have all 136 numbers but I think they are all square free. Am I right?
I am assuming a square free number can not be divided by a square number. e.g. 10 is square free, 18 is not (can be divided by a square number: 9).
Program runs in a second or two but gets wrong answer.
I would like to suggest a slight change to Smaug's wording:
... for all squarefree N whose only factors are primes of the form 4k+1 where 4k+1 < 150.

[TripleM]

Thanks for the clarification Jochen_P.

Jochen_P was not making a clarification on the problem statement; it was on a wrong interpretation of the problem statement!

Smaug's wording is correct; yours leads to the wrong assumption that numbers like 5*13*17 are invalid. They are valid.

[Jochen_P]

Yep,

sorry for the confusion...
I'm afraid that you'll have to work with 2^16-1 figures

[quilan]

So it's been ages since I picked up this problem, and I've got what SHOULD be a water-tight solution written but... as is wont to be the case, it's no-go. Can I get a ninja quick confirmation that the process (as discussed above) for say... all primes 4k+1 [le] 20, we'd be solving for:

answer = S(5) + S(5*13) + S(5*13*17) + S(5*17) + S(13) + S(13*17) + S(17)
= S(5) + S(65) + S(1105) + S(85) + S(13) + S(221) + S(17)

If not, what would I be solving for? If so... I've got a nightmare of a debugging session ahead of me.

[elendiastarman]

That seems to me to be correct.

[quilan]

Haha! Just kidding! I've had the correct algorithm for... oh, a month & a half now. Just had the dumbest bug ever. I love life.

[elendiastarman]

The stupidest bugs are always the hardest ones to find...

[pain]

First I misunderstood the question and solve it for only 5 , 13 , 17.... and 5*13, 5*17...
but now how to handle the numbers like 5*13*17...*149... i am stucked.... in c++ as the order of the number is quite large...
Please Help...

[mrain]

with the description "all squarefree N only divisible by primes of the form 4k+1 with 4k+1 < 150
N is going to be unbounded. because for every integer i, 5^i is a valid squarefree number.

[TripleM]

http://en.wikipedia.org/wiki/Squarefree

[Oliver1978]

I suspect these are elements 1 to 5 of N ... [1, 5, 13, 17, 29]?

[PhilLeTaxi]

I agree with you for these elements.
As said above, there are 65535 number N for primes below 150.
I wonder how to speed up the process.

[Oliver1978]

@PhilLeTaxi: I'm trying to avoid big integers, which may not be necessary at all. Some old Indian certainly knew the answer I'm sticking with his way right now.

[PhilLeTaxi]

Thanks Olivier for your response.
I solved the problem yesterday.

I coded it in Python.
May be in another langage like Java, you will need BigInteger
as the greatest possible N has 28 digits.

[Junglemath]

There's an 's' missing in 'integer' in the first line of the problem statement.

And the same missing 's' in the same word on line 4.

[jaap]

There's an 's' missing in 'integer' in the first line of the problem statement.

And the same missing 's' in the same word on line 4.

You could add an s, but it is also correct as is, since integer is being used here as an adjective rather than a noun (like "whole" instead of "whole number").