Problem 793, and others

[Torpaz]

Let $S_i$ be an integer sequence produced with the following pseudo-random number generator:

$S_0 = 290797$</li>
$S_{i+1} = S_i ^2 \bmod 50515093$</li>

Let $M(n)$ be the median of the pairwise products $ S_i S_j $ for $0 \le i \lt j \lt n$.

You are given $M(3) = 3878983057768$ and $M(103) = 492700616748525$.

Find $M(1\,000\,003)$.


Hello,

I started taking a look into Euler problems few months ago, went over the first 100+ ones. Every week I take a look at the newly published Euler problem. The time complexity seems unreachable for me on those latter problems. While I have fun solving 50+ % difficulty problems published 10 years ago, I don't have a clue on how to solve the last problems, even tho some look really easy, but they just seems too much.

For example, last problem 793 seems very easy, some have solved it in 4 minutes. And yet I don't see any solution that wouldn't require $O(1\,000\,003^2)$ products. I don't know about you, but that's hours, if not days, of time-computing on my PC.

And this seems to be true for most recent Euler problems. Time computations just seem out of my mind.

So I'm kinda confused. To be clear, I don't want this specific, or any other, problem solution. I just want the situation to be clarified :
1) First, am I wrong or this specific problem definitely requires to find a way to efficiently compute $1\,000\,003^2$ operations ?
2) If so, is it feasible on a normal computer ? Have Euler problems adapted to people using parallel computer networks by upraising their time-computations required to solve problems ? Or do I just need to program better ?

Thanks in advance if anyone can enlighten me.

[pjt33]

1) First, am I wrong or this specific problem definitely requires to find a way to efficiently compute $1\,000\,003^2$ operations ?
2) If so, is it feasible on a normal computer ?

1) You are wrong. There's enough structure that not all of the products need to be computed.
2) My rule of thumb is that a PE problem won't require more than about $10^9$ operations, so if the input is $10^6$ then a quadratic algorithm is only worth creating if it will help me explore small cases and understand the problem better, because the final solution will be at worst $\tilde{O}(n^{3/2})$.

[neverforget]

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

I have yet to encounter a problem that violates the one-minute rule (including #793), although if you are using an interpreted language you may need special interpreter that can perform compiler optimizations in order to actually be under a minute (e.g. I've been having a lot of success with pypy for Python).

And to clarify, "modestly powered computer" is really quite modest (e.g. 3GHz single core with 2GB RAM).

Also, I would caution against reading too much into fast/slow solve times as an indication for how difficult a problem actually is, let alone its difficulty for you personally. As a rough estimate it's fine, but from looking at leaderboards for the last several years, I can say with confidence everyone has wildly different strengths and weaknesses.

[PeterCullenBurbery]

What is a pairwise product?
I don't understand what the median of pairwise products is.

[mdean]

It's exactly as it sounds in the form shown. You take any pair of numbers from the sequence and multiply them to obtain their product. So if the sequence were 1,2,3; the pairwise products would be 2,3, and 6 and the median would be 3.

[Torpaz]

Okay, thanks a lot for these anwers, that was a much needed clarification !