Problem 439

[Maybeso83]

Problem 439 (View Problem)
I've been working on S(N) for N < 100, and occasionally trying the test case 10³ 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.

[mpiotte]

...The solution is probably less complex than prog2, but can it really beat prog1?...

Yes. There are sublinear solutions to this problem.

[jpatou]

I'm really struggling with this one. Can someone check if S(10^8) mod (10^9)= 575796594 ?
Thanks

[thundre]

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

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

[hk]

That depends on your implementation.

[luechtdiode]

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.

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

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

[mdean]

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.

[benevolentdespot]

Thank you, that clears it up.