Timeline for Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 21, 2014 at 18:14 | comment | added | InformedA | @YuvalFilmus I have, but I am not sure. | |
| Oct 20, 2014 at 11:46 | comment | added | Yuval Filmus | Have you empirically tested your algorithm? Do you have a candidate proof? | |
| Oct 20, 2014 at 7:56 | history | tweeted | twitter.com/#!/StackCompSci/status/524106763738841089 | ||
| Oct 20, 2014 at 4:17 | comment | added | InformedA | @YuvalFilmus I have a sketch, but I am not sure if that will be correct, so I refrain from writing it here. I have learnt the hard way that the real world is not like a school exam. You don't say anything to get partial credit. In the real world, wrong answers are not something with which you can be easy. | |
| Oct 20, 2014 at 4:06 | comment | added | Yuval Filmus | If you have a sketch you should share it with us. Otherwise it's pointless to think about the question. This is not a puzzle site. | |
| Oct 20, 2014 at 1:12 | answer | added | D.W.♦ | timeline score: 4 | |
| Oct 18, 2014 at 16:49 | history | edited | InformedA | CC BY-SA 3.0 | added 9 characters in body |
| Oct 18, 2014 at 16:31 | history | edited | InformedA | CC BY-SA 3.0 | added 25 characters in body |
| Oct 18, 2014 at 16:30 | comment | added | InformedA | @LukeMathieson Fair suggestion. I am hoping to get it in time that is not exponential to the representation of $a$ and $b$ | |
| Oct 18, 2014 at 14:11 | history | edited | InformedA | CC BY-SA 3.0 | edited body |
| Oct 18, 2014 at 11:22 | comment | added | Luke Mathieson | I don't see how it could be done in constant time. As $a$ and $b$ get large, even producing the output would not be constant in time or memory. More speculatively, I don't think there is a simple relationship that would allow the determination of the answer quickly, my first-approximation guess is that this would take pseudopolynomial time (polynomial in the magnitude of $a$ and $b$, but maybe exponential in the size of their representation). | |
| Oct 18, 2014 at 7:02 | history | asked | InformedA | CC BY-SA 3.0 |