3
$\begingroup$

I have an IT problem to solve, but I came into a blind spot when it came to mathematics..

Ill give a compact background, maybe it helps. The sequence, that I'll have to reverse, is the size of the subsequent collection of elements formed from the input data x, y, where 1 < x <= y. With dimension x*y 400x400, the algorhitm operate on millions of items and its just too much for my hardware. Therefore I must plan its max capacity before calculations (to avoid restructuring of the HashSet - which is causing heap overflow).

I am wondering if its possible to reverse the approximate formula just from heuristics, without getting deeper explanation of alghoritm itself...

ill give some exapmle output for lesser input dimensions:

for 6 elements, where x=3, y=5 (the 6 quantity is from x+y-2)

2 8 17 26 30 22 (for such small dimension, I dont need its compatibility with formula yet)

for [10] elements, where x=5, y=7

2 8 20 40 65 90 108 110 94 58

for [14] elements, where x=5, y=11

2 8 20 40 65 90 115 140 165 190 204 194 158 94

for [14] elements, where x=6, y=10

2 8 20 40 70 106 142 178 214 240 244 224 178 104

for [17] elements, where x=9, y=10

2 8 20 40 70 112 168 240 321 392 441 466 465 436 377 286 161

for [18] elements, where x=10, y=10

2 8 20 40 70 112 168 240 330 420 488 532 550 540 500 428 322 180

for [19] elements, where x=10, y=11

2 8 20 40 70 112 168 240 330 430 519 584 623 634 615 564 479 358 199

for [19] elements, where x=9, y=12

2 8 20 40 70 112 168 240 321 402 483 552 595 610 595 548 467 350 195

for [19] elements, where x=8, y=13

2 8 20 40 70 112 168 232 296 360 424 488 539 562 555 516 443 334 187

there is some identity here, so any pattern, that close those values below (at least the part where it grows) would rescue me.

enter image description here

in addition, ive invented (while looking at alghoritm) how to calculate last three numbers, which is valid for every case:

last = ((x-1)*y) + (x*(y-1)) = 2xy-y-1

last-1 = ((x-2)*y) + ((y-2)*x) + ((x-1)*2*(y-1)) = 4xy-4x-4y+2

last-2 = ((x-2)*2*(y-1)) + ((y-2)*2*(x-1)) + ((x-3)*y) + ((y-3)*x) = 6xy-9x-9y+8


Now, using wolframalpha.com, I am analyzing only the decrease for now (last three numbers is known allready)

for [17] elements, where x=9, y=10

2 8 20 40 70 112 168 240 321 392 441 {466 465 436 377 286 161} enter image description here

for [18] elements, where x=10, y=10

2 8 20 40 70 112 168 240 330 420 488 532 {550 540 500 428 322 180} enter image description here

for [19] elements, where x=10, y=11

2 8 20 40 70 112 168 240 330 430 519 584 623 {634 615 564 479 358 199} enter image description here

for [19] elements, where x=9, y=12

2 8 20 40 70 112 168 240 321 402 483 552 595 {610 595 548 467 350 195} enter image description here

for [19] elements, where x=8, y=13

2 8 20 40 70 112 168 232 296 360 424 488 539 {562 555 516 443 334 187} enter image description here

for [20] elements, where x=9, y=13

2 8 20 40 70 112 168 240 321 402 483 564 632 672 {682 660 604 512 382 212} enter image description here

  • values of third elements within brackets seems to be repeatable with hard to guess condition (76; 112..)
  • since last value within brackets is dividable by 3 in every case, i am looking to try to reverse creation of this value, but have no clue how:

f(9,10) = 441

f(10,10) = 532

f(10,11) = 623

f(9,12) = 595

f(8,13) = 539

f(9,13) = 672

My progress with general formula for the decrease for now:

enter image description here


Ok, i am in blind spot.. I've found in web this function: enter image description here

please, give me link to good lightweight program where I can visualize functions on graph to play with pattern and adjust it to my needs..

$\endgroup$
1
  • $\begingroup$ Off the cuff, your graph very much resembles a Maxwell-Boltzmann distribution. $\endgroup$
    – David H
    Oct 26 '14 at 12:12
3
$\begingroup$

The expressions of your three last terms (excellent observation btw! +1) admit the generalization :
(the $m+1-n\,$ indice with $m=x+y-2$ allows to revert the order since starting from the end) $$\tag{1}a_{m+1-n}:=\sum_{k=0}^{n-1} (x-n+k)(y-k) + (y-n+k)(x-k)$$

But this is not the general formula wished since for $\;x=8,\,y=13,\,m=19$ (terms) the result is :

$-1349, -1122, -901, -688, -485, -294, -117, 44, 187, 310, 411, 488, 539, 562, 555, 516, 443, 334, 187$

while you needed $2, 8, 20, 40, 70, 112, 168, 232, 296,360 ,424 ,488, 539, 562, 555, 516, 443, 334, 187$.

The formula $(1)$ broke down (starting from the end) when at least one of the products became negative. An alternative formula with the terms replaced by their absolute value was only slightly better but simply ignoring the negative values appeared very promising : $$\tag{2}b_{m+1-n}:=\sum_{k=0}^{n-1} \max(0,(x-n+k)(y-k)) + \max(0,(y-n+k)(x-k))$$ For $\;x=8,\,y=13,\,m=19\;$ I obtained as wished : $2, 8, 20, 40, 70, 112, 168, 232, 296, 360, 424, 488, 539, 562, 555, 516, 443, 334, 187$

For $\;x=6,\,y=10,\,m=14\;$ I got too the correct :
$2, 8, 20, 40, 70, 106, 142, 178, 214, 240, 244, 224, 178, 104$


Rewriting $(1)$ as $$a_{m+1-n}=n/3\,(n^2-3\,n (x+y)+6\, x y-1),\quad\text{for}\;n\le x$$ (this may be obtained by subtracting the formula $(1)$ applied to $n$ and $n-1$ and computing the sum over $n$ of these differences or... by using Alpha) you may conclude by combining this with your observations that : \begin{align} a_n &= \frac{1}3(n^3+3n^2+2n),\quad\text{for}\; n \in [ 1,x )\\ \text{and}\\ a_n &= \frac{1}3(x^3-x)+(n+1-x)\,x^2,\quad\text{for}\; n \in [x,y)\\ \end{align}

If I didn't add further errors...

$\endgroup$
5
  • $\begingroup$ I am amazed with your computations! your output is exact.. however (since I dont have well math knowledge) I had minor difficulties to get exact output. I believe u wanted to parse x=8, y=**13**, m=19? I was also working on generalization and made some progress, $$ \begin{equation} a_n(n) = \begin{cases} \frac{1}3(n^3+3n^2+2n) & \text{if } n \in [ 1,x ), \\ a_{n-1} + x^2 & \text{if } n \in [x,y), \\ \frac{1}3(-k^3+(42-8x+y)k^2+. . . & \text{if } n \geq\, y\Rightarrow k := \{ n : n-y+1 \}. \end{cases} \end{equation} $$ where last sentence in equation is almost done $\endgroup$
    – s1w_
    Oct 27 '14 at 4:11
  • $\begingroup$ @s1w_ : yes it should have been $y=13$. Note that my answer $(1)$ may be rewritten as $n/3\,(n^2-3\,n (x+y)+6\, x y-1)\;$ which could be your wished (incomplete) answer for the terms at the right! (where $n=1$ is the term most at the right). I'll update my answer later (I don't know yet the correct expression at the middle and rather busy elsewhere...) $\endgroup$ Oct 27 '14 at 9:03
  • $\begingroup$ As u see, I have solved middle $ a_n := a_{n-1} + x^2 $ :) ill check your pattern for right side $\endgroup$
    – s1w_
    Oct 27 '14 at 12:15
  • $\begingroup$ I am shocked! its working for worst case data that i am compiling for tests. I am wondering how did u found out it so fast, while i have scribbled half of my squared book to get this results ;) +1 ! $\endgroup$
    – s1w_
    Oct 27 '14 at 18:31
  • $\begingroup$ @s1w_: Luck of course (and Alpha ;-)) ! Cheers, $\endgroup$ Oct 27 '14 at 23:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.