Problem 549

[essjayarr]

Hi!

Can someone point out after which n in the list below my answers starts going wrong?
I'm hoping that'll help me find out why it isn't right.

n — S (n)
<values snipped by moderator>
Thanks.
SJR.

[square1001]

Let's calculate for a brute-force code and check for small $n$ cases.

[essjayarr]

Thanks! That helped.

Evidently, I wasn't paying attention to 12 being divisible by 4

regards,
Janakiraman.

[Alex-82w4]

It is impossible to solve this problem by calculating the most factorials directly.

My approach to find the number of common divisors for the smallest divisor and factorial.
I used Legendre's Theorem to do the trick for factorials.
My program runs quickly and correctly for n = 100.
I improved processing time for the first 10000 numbers from 5 minutes to 2 seconds Processing time of the next sequential 10000 records increases exponentially. I ran the program for a day and it calculated S(2160000). I don't know how long it takes to get result for S(10⁸) I guess it is more than a week.

Could someone help me to improve performance of my existing program?

Thanks,
Alex.

[vamsikal3]

<deleted post>

[tigershark22]

I'm having a problem with my S(n) function. I calculated for the values of s(n) given and can't find what's wrong. S(100) gives me 2034 instead of 2012. Can someone tell me what numbers my s(n) is off for? (pm me)

EDIT: Never mind, I need to change my program for those special cases
EDIT 2: I think there's something wrong with my algorithm still, now im getting 1967. Please pm me

[LateStart]

Hello,

I'm having problems understanding the question for problem 549.

S(100)=2012.

Does that mean that smallest factorial divisible by 100 and greater than 100 is 2012!?
What I have found is 300! % 100 ==0.

Can someone explain to me what exactly are we searching for, because it looks like I have misunderstood the question.

[traxex]

S(100)=2012.

Does that mean that smallest factorial divisible by 100 and greater than 100 is 2012!?

No. It means that s(2) + s(3) + ... + s(100) = 2012.

[LateStart]

Thank you, so to double check if I got this right this time..
We have to find the sum of all the smallest divisors, for factorials from 2 to 100 in case s(100)=2012?

[traxex]

We have to find the sum of all the smallest divisors, for factorials from 2 to 100 in case s(100)=2012?

You have it exactly backwards. You are not looking for divisors, they are what is given; you are looking for the smallest factorials that are divisible by the given divisors.

Also note that s(n) and S(n) are different functions. It is the upper case version for which S(100) = 2012.

I suggest you create brute force implementations of s(n) and S(n) and verify the example values given.

[LateStart]

Oh, I got it now because I didn't spot the S and s difference in the first place. Thank you for clarifying this

[LateStart]

Hello,

I think I might have managed to "solve" the problem, but before letting it run (aprox time required 50 hours), I need to be sure that solution is 100% correct.
I have calculated S(2000000) in 1 hour. Really takes too long for large numbers, and it isn't pure brute force solution. I have implemented Kempners function rules, but it still has to check factors for each number except primes.

So please, before I start on any algorithm improvements, can anyone confirm if S(<snipped by moderator>) = <snipped by moderator>?

Regards,
LateStart

[hk]

Asking for answer confirmations to enable a bruteforce solution is not the purpose of this forum.

[LateStart]

I understand your point, but the last thing I am trying to do is cheat
I'm not going to brute force it. Just not sure if rules I've implemented are correct and do apply correctly for larger numbers than 100.

[hk]

I program that will take 50 hours to run is a classical example of bruteforcing.
Please find a solution that runs fast enough.

[LateStart]

I have solved problem in 90 minutes, and I do not consider it bruteforce. As i got very interested into solving this problem, if anyone could check the code, I've posted it on thread page comments, and explain to me why it takes so long for above 10^7 calculations.

[Animus]

Answered via PM.

[merlinnimue]

Quick sanity check: can anyone confirm if S(10^6) = skipped?

[MuthuVeerappanR]

Quick sanity check: can anyone confirm if S(10^6) =xxxxxxxxxxxxxxx?

We are not supposed to post partial answers in this forum. But anyway, the value you posted seems to be wrong. Happy solving!!

[merlinnimue]

Quick sanity check: can anyone confirm if S(10^6) = wrong?

We are not supposed to post partial answers in this forum. But anyway, the value you posted seems to be wrong. Happy solving!!

My apologies -- I thought this was something of a common practice judging from other posts. Thanks for your help!