# Thread: A most fundamental problem of extreme significance

1. ## A most fundamental problem of extreme significance

Object O is moving with step size S along line P. With each step it takes, it's step size increments by 1. So, if S is 1 on the first step it will be 2 on the second and 3 on the third, etc. Line P has "hotspots" starting at location 0 and the space between them increments by 1, also. So, line P location 0,1,3,6,10,15, etc ((n(n+1)/2) with any value for n) will be hotspots. I want to find the next hotspot object O will land on in polynomial time without recursion. Here are a few examples:

O's starting step size is 1 and starting location is 0. It will land on hotspot 1 in 1 step.

O's starting step size is 2 and starting location is 0. It will never land on a hotspot.

O's starting step size is 3 and starting location is 0. It will land on hotspot 3 in 1 step.

O's starting step size is 4 and starting location is 0. It will land on hotspot 15 in 3 step.

Etc.

So, given O's starting step size and location how do you predict the next hotspot it will land on and/or how many jumps.

This problem, despite appearing quite trivial, is, infact, of extreme importance. I truly thank anyone who attempts to help me solve this. If we can, it will change the world.

2. I truly do not want to believe there is no way to predict the next interception point. I can predict *a* interception point. The problem is this is not always the next. As such, it is competely useless for my purpose.

I have attached a visual depiction of the problem using dead angel monkeys (I was bored and frustrated with the numbers side). Anyways, the depiction starts at location -2. Monkey 4 jumps 4 on his first move and falls into hell. Monkey 5 jumps 5 and is safe, for now.

The thing is when you represent the numbers of their distance from the closest hotspot you find the following:

Monkey 5:

Jump:1
StepSize:5
NextHotSpot:10
Distance:3

Jump:2
StepSize:6
NextHotSpot:15
Distance:2

Jump:3
StepSize:7
NextHotSpot:21
Distance:1

Jump:4
StepSize:8
NextHotSpot:28
Distance:0

Now, as you can see the distance from next recedes by 1 with each jump and starts at a distance of 3. I can infer by measurements between jumps 1 and 2 that he will finish on jump 4.

That is all beautifully simple but I am not sure how to handle situations such as the following:

Monkey 10:

Jump:1
StepSize:10
NextHotSpot:15
Distance:3

Jump:2
StepSize:11
NextHotSpot:28
Distance:5

Jump:3
StepSize:12
NextHotSpot:36
Distance:1

Jump:4
StepSize:13
NextHotSpot:55
Distance:7

Jump:5
StepSize:14
NextHotSpot:66
Distance:4

Jump:6
StepSize:15
NextHotSpot:78
Distance:1

Jump:7
StepSize:16
NextHotSpot:105
Distance:12

Jump:8
StepSize:17
NextHotSpot:120
Distance:10

Jump:9
StepSize:18
NextHotSpot:136
Distance:8

Jump:10
StepSize:19
NextHotSpot:153
Distance:6

Jump:11
StepSize:20
NextHotSpot:171
Distance:4

Jump:12
StepSize:21
NextHotSpot:190
Distance:2

Jump:13
StepSize:22
NextHotSpot:210
Distance:0

So, what I want is to say jump 1 is, infact, a distance of 24 from hotspot 36 instead of 3 away from 15. Then, the rest fall into pattern accordingly. Jump 2 would be 22 away from 45, 3 would be 20 away from 55 etc etc until collision. I need to use the distance of 3 from 15 in step 1 and the distance of 5 from 28 in step 2 to arrive at step one's needed hotspot measurement from 36 and not 15.

3. *Duplicate post*

4. I believe we can solve using quadratic Diophantines. We have $\displaystyle \frac{n(n+1)}{2}$ with n ranging over the non-negative integers describing all possible hotspots. Then for example the position of the monkey starting at position 2 with initial step 10 can be described by $\displaystyle \frac{(k+9)(k+10)}{2}-43$ with k ranging over the non-negative integers. You can then set the two expressions equal and put the equation into the form $\displaystyle \,Ax^2+Bxy+Cy^2+Dx+Ey+F=0$. And you can use this tool.

Version 1 - JavaScript - Dario Alpern's Generic Two integer variable equation solver

Version 2 - Java - Dario Alpern's Generic Two integer variable equation solver

I am curious as to the importance of this question. Care to elaborate on what the problem represents and where you found it?

5. I am not familiar with quadratic Diophantines. I will study this field and see if I can implement it for my use. Also, I will give you a thank point for helping me. I am a bit reluctant to share the details of what this problem represents at the time being. I found the problem while trying to solve an equation in a function I am working on. It is, in fact, the last standing hurdle to the completing of this function. At the moment I, unfortunately, do not understand how to put the equation into the form you specified. I will study this tonight and if come morning I can integrate this I will share the remaining details and, if you're interested, some other important things.

I am currently in China so my night is your day. As the time difference is so stark and I am now a father I do not have much time to come to the computer bar to read replies and study. If you are willing to further help me I hope you will be available today.

6. Originally Posted by Herniator
I am not familiar with quadratic Diophantines. I will study this field and see if I can implement it for my use. Also, I will give you a thank point for helping me. I am a bit reluctant to share the details of what this problem represents at the time being. I found the problem while trying to solve an equation in a function I am working on. It is, in fact, the last standing hurdle to the completing of this function. At the moment I, unfortunately, do not understand how to put the equation into the form you specified. I will study this tonight and if come morning I can integrate this I will share the remaining details and, if you're interested, some other important things.

I am currently in China so my night is your day. As the time difference is so stark and I am now a father I do not have much time to come to the computer bar to read replies and study. If you are willing to further help me I hope you will be available today.

Glad to help! A Diophantine equation is just an equation over integers (that is, the variables are only allowed to take on integer values). I don't know how available I will be today, but I check MHF frequently enough so it should work out.

If you only need to do a few of these calculations by hand, then I think Dario Alpern's tool will suit you just fine. (I haven't actually plugged my example in, but everything looks in order.)

If you need to perform many of these calculations in an automated fashion, then possibly you would need to either adapt Dario Alpern's code (hard) or write your own (harder). I've done some work on the latter option but it would probably take a month under relaxed conditions to turn it into something of production value, and more than that since I'm busy. However, those time estimates are in reference to a general quadratic Diophantine solver; it is possible that you will only need special cases (such as the elliptical case). Of course there may be some easier option I've overlooked. You mention polynomial time; I'm not sure whether a more naive algorithm would suit your purposes.

7. Originally Posted by undefined
Glad to help! A Diophantine equation is just an equation over integers (that is, the variables are only allowed to take on integer values). I don't know how available I will be today, but I check MHF frequently enough so it should work out.

If you only need to do a few of these calculations by hand, then I think Dario Alpern's tool will suit you just fine. (I haven't actually plugged my example in, but everything looks in order.)

If you need to perform many of these calculations in an automated fashion, then possibly you would need to either adapt Dario Alpern's code (hard) or write your own (harder). I've done some work on the latter option but it would probably take a month under relaxed conditions to turn it into something of production value, and more than that since I'm busy. However, those time estimates are in reference to a general quadratic Diophantine solver; it is possible that you will only need special cases (such as the elliptical case). Of course there may be some easier option I've overlooked. You mention polynomial time; I'm not sure whether a more naive algorithm would suit your purposes.
I am starting to understand what you are referring to. The number's I am working with are very large and need an automated equation to attach into the current function. If the equation can carry out in polynomial time then it is perfectly reasonable. If not then the time frame per equation would likely render the function useless or near to. The problem I presented previously was the sole purpose I will use the required equation for. Besides the hotspots' locations being fixed on the line and the increment factor of 1 for the jump size the other factors are variable, i.e. starting location, first jump size.