Hello!↵
↵
Some time ago I created a problem for local programming competition. Unfortunately it turned out that I had incomplete proof of one lemma, that I can not show even to this day.↵
↵
**Lemma:**↵
Given an increasing array of $N$ arbitrary large numbers we define its cost as sum of lengths of all non-trivial, maximal arithmetic progressions starting at the first element. The cost of any array is $\mathcal{O}(N\log{N})$.↵
↵
For example for array $[0, 2, 3, 4, 6, 8, 9]$ — the total cost is $|[0, 2, 4, 6, 8]| + |[0, 3, 6, 9]| + |[0, 4, 8]| + |[0, 6]| + |[0, 8]| + |[0, 9]| = 5 + 4 + 3 + 2 + 2 + 2= 168$.↵
↵
It is easy to see, that if we simply take $N$ consecutive natural numbers we get $\mathcal{O}(N\log{N})$ cost, but I was not able to prove that this is the worst case scenario.↵
↵
Best complexity I can show is $\mathcal{o}(N^2)$, but still far from the goal...↵
↵
Can anyone show if the lemma is true or false?
↵
Some time ago I created a problem for local programming competition. Unfortunately it turned out that I had incomplete proof of one lemma, that I can not show even to this day.↵
↵
**Lemma:**↵
Given an increasing array of $N$ arbitrary large numbers we define its cost as sum of lengths of all non-trivial, maximal arithmetic progressions starting at the first element. The cost of any array is $\mathcal{O}(N\log{N})$.↵
↵
For example for array $[0, 2, 3, 4, 6, 8, 9]$ — the total cost is $|[0, 2, 4, 6, 8]| + |[0, 3, 6, 9]| + |[0, 4, 8]| + |[0, 6]| + |[0, 8]| + |[0, 9]| = 5 + 4 + 3 + 2 + 2 + 2= 1
↵
It is easy to see, that if we simply take $N$ consecutive natural numbers we get $\mathcal{O}(N\log{N})$ cost, but I was not able to prove that this is the worst case scenario.↵
↵
Best complexity I can show is $\mathcal{o}(N^2)$, but still far from the goal...↵
↵
Can anyone show if the lemma is true or false?
