Timeline for What tools should I use for this problem?
Current License: CC BY-SA 4.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2021 at 5:58 | answer | added | fedja | timeline score: 3 | |
| Dec 7, 2021 at 15:46 | history | edited | Diego Santos | CC BY-SA 4.0 |
added 81 characters in body
|
| Dec 7, 2021 at 15:44 | comment | added | Diego Santos | @MattF., you're right, I should be more clear about it. I will edit. Thank you for pointing out. | |
| Dec 6, 2021 at 2:59 | history | edited | Michael Hardy | CC BY-SA 4.0 |
added 5 characters in body
|
| Dec 5, 2021 at 16:31 | answer | added | Karl Fabian | timeline score: 2 | |
| Dec 5, 2021 at 15:54 | comment | added | user44143 | Does an acceptable answer to the problem need to “determine [all] possible values for $p$”, or is it enough to “find nontrivial solutions”? The post should clarify which is required. | |
| Dec 5, 2021 at 15:53 | history | edited | user44143 |
this is about arithmetic progressions, and the biographical connection between this question and teaching linear algebra or differential equations is not a reason to include those tags
|
|
| Dec 2, 2021 at 2:06 | review | Suggested edits | |||
| Dec 2, 2021 at 7:14 | |||||
| Dec 2, 2021 at 0:54 | history | edited | Diego Santos | CC BY-SA 4.0 |
added 199 characters in body
|
| Dec 2, 2021 at 0:50 | comment | added | Diego Santos | @TimothyChow, uau! That was a really great insight!!! Thank so much! Also thank you for the patience to explain in so nice way. Totally makes sense: "It can't be a very "workable expression" if even figuring out the value of p from the expression takes about a trillion operations". And yes: only ever have to deal with at most 20 bars. I would say that at most 15. I will edit to include this observation. | |
| Dec 1, 2021 at 21:47 | comment | added | Timothy Chow | If it's a "workable expression" then presumably you can at least compute $p$ and $q$ from the expression, but the best known algorithms take quadratic time. It can't be a very "workable expression" if even figuring out the value of $p$ from the expression takes about a trillion operations. Can you say anything more about the input data for the problem? Maybe you only ever have to deal with at most 20 bars, and there are certain other constraints on how they are positioned? Also maybe it's good enough to have a good solution rather than the absolute optimal solution? | |
| Dec 1, 2021 at 21:29 | comment | added | Timothy Chow | @DiegoSantos Again, I think this is too optimistic unless you have some strong limitations on what the input can be. Let me try to explain by analogy with the longest arithmetic progressions problem. Say I have a list of 1 million random 10-digit integers $\{a_1, a_2,\ldots, a_{1000000}\}$ and I want to know what the longest arithmetic progression is, meaning a $p$ and a $q$ such that $pn+q$ runs through the progression as $n$ runs through $1,2,\ldots,m$ for some $m$. It is going to be hopeless to write down a "workable expression" for $p$ and $q$ in terms of the 1 million given numbers. | |
| Dec 1, 2021 at 17:44 | comment | added | Diego Santos | @TimothyChow, what is needed is an 'workable expression' . For a numeric approach, although I know nothing about programming, I imagine that is pretty doable. | |
| Dec 1, 2021 at 14:10 | comment | added | Timothy Chow | Jeff Erickson has written a two-page article on Finding Longest Arithmetic Progressions. This is not exactly the same as your problem but I think it's close. In particular, I suspect that dynamic programming will be a good approach to your problem. (But my intuition is that a "closed form" is too much to hope for.) | |
| Dec 1, 2021 at 14:08 | history | edited | Diego Santos | CC BY-SA 4.0 |
added 283 characters in body
|
| Dec 1, 2021 at 13:03 | comment | added | Diego Santos | @StevenStadnicki, I like the way you put as "essentially trying to do is 'miss' a set with arithmetic progressions". But also I need to account for the size of each element of the arithmetic progression. About using integral parameters, it really makes sense, as in practice we could ignore erros little than some value (say $1mm$). But I don't know how to work with that. | |
| Dec 1, 2021 at 12:54 | comment | added | Diego Santos | @LSpice, I appreciate very much your comment! | |
| S Dec 1, 2021 at 6:54 | history | edited | Friedrich Knop | CC BY-SA 4.0 |
Minor English corrections.
|
| S Dec 1, 2021 at 6:54 | history | suggested | CommunityBot | CC BY-SA 4.0 |
Minor English corrections.
|
| Dec 1, 2021 at 3:52 | review | Suggested edits | |||
| S Dec 1, 2021 at 6:54 | |||||
| Dec 1, 2021 at 3:45 | comment | added | Steven Stadnicki | That is to say, try and treat all parameters as integral and look for solutions that way, as what you're essentially trying to do is 'miss' a set with arithmetic progressions. Depending on the number of gaps, you may be able to do a discrete search based on which gaps you believe one (or more) bars will go into — that is, consider discrete configurations and determine which ones allow a valid solution. | |
| Dec 1, 2021 at 3:34 | comment | added | Steven Stadnicki | Since you're asking about what tools: I'm not sure I would consider this as a continuous problem at all. How close to rationally ratio'd are your $k$ and $l$ (and the distances $a_i$, I suppose)? I would treat this as a number theory problem. | |
| Dec 1, 2021 at 3:13 | comment | added | LSpice | Thanks for all the work you put into a well crafted post, including the MMO post to make sure it was best possible. | |
| Dec 1, 2021 at 3:06 | history | asked | Diego Santos | CC BY-SA 4.0 |