Page 1 of 1
Problem 439
Posted: Tue Oct 08, 2013 1:23 am
by Maybeso83
Problem 439 (
View Problem)
I've been working on S(N) for N < 100, and occasionally trying the test case 10
3 and larger N. The times were getting bad too fast so I wrote a skeleton program
Code: Select all
nMax = 10^11
nMod = 10^9
// Prog1
f = 1234
for n = 1 to nMax
c = n*f mod nMod
// Prog2
for n = 1 to nMax
for f = 1 to n
c = n*f mod nMod
and got these timings
Code: Select all
nMax Prog1 Prog2
10^3 0.001 s 0.497 s
10^4 0.009 s 48.622 s
10^5 0.110 s 5534.003 s
10^6 1.119 s
10^7 11.015 s
10^8 110.096 s
My current not-too-brilliant version:
10^3 563576517282 60.325 s
The solution is probably less complex than prog2, but can it really beat prog1?
I'm thinking there's a problem with my machine or my machine+language is not sufficient to solve this problem.
Re: Problem 439
Posted: Wed Oct 09, 2013 1:32 am
by mpiotte
Maybeso83 wrote:...The solution is probably less complex than prog2, but can it really beat prog1?...
Yes. There are sublinear solutions to this problem.
Re: Problem 439
Posted: Sat Oct 12, 2013 10:05 pm
by jpatou
I'm really struggling with this one. Can someone check if S(10^8) mod (10^9)= 575796594 ?
Thanks
Re: Problem 439
Posted: Sun Oct 13, 2013 5:33 pm
by thundre
jpatou wrote:I'm really struggling with this one. Can someone check if S(10^8)
I'm still struggling too. But I haven't asked for intermediate results because there are only 31 solvers so far.
https://projecteuler.net/fastest=439
Re: Problem 439
Posted: Thu Dec 05, 2013 7:12 am
by ffff0
I hope this is not too much to ask, but does this problem need a lot of memory? It obviously can't be O(n^2), but I suppose it's not O(1) either.
Re: Problem 439
Posted: Thu Dec 05, 2013 9:51 am
by hk
That depends on your implementation.
Re: Problem 439
Posted: Tue Dec 10, 2013 10:03 pm
by luechtdiode
thundre wrote:jpatou wrote:I'm really struggling with this one. Can someone check if S(10^8)
for me, it's still a miracle. My impl gives me the right results for the given examples. Also with S(10^8) I get the same result.
Just my final result with S(10^11) isn't accepted on PE-Page. The summed divisors are stored/calculated with BitInteger-Classes.
Re: Problem 439
Posted: Wed Dec 11, 2013 2:35 pm
by Marcus_Andrews
If you are fairly certain that there is no overflow, then it could be a modular arithmetic issue instead. I'll try not to spoil this, but keep in mind that the modulus for this problem is 10^9.
Problem 439
Posted: Thu May 11, 2017 3:31 am
by benevolentdespot
I have a very limited experience with series and I was wondering what the equation of S(N) actually means. It doesn't have the top and parts like most series I see. I haven't taken Calculus if that is a prerequisite to solving the problem.
Re: Problem 439
Posted: Thu May 11, 2017 9:48 am
by mdean
benevolentdespot wrote: Thu May 11, 2017 3:31 am
I have a very limited experience with series and I was wondering what the equation of S(N) actually means. It doesn't have the top and parts like most series I see. I haven't taken Calculus if that is a prerequisite to solving the problem.
Are you more familiar with
$$\sum_{i=1}^N \sum_{j=1}^Nd(ij)$$
Not sure if this is what you meant by "the top". The sigmas are of course a summation. The inner summation for all integers j less than or equal to N and the outer for all integers i less than or equal to N.
Re: Problem 439
Posted: Thu May 11, 2017 1:35 pm
by benevolentdespot
Thank you, that clears it up.