Wlpert1 Posted March 19, 2015 Posted March 19, 2015 http://meecles.net/puzzles/challenges.html ^ I stumbled upon this really well puzzel that deals with hard things! I know the answer is 80 numbers long. If you figure it out leave the answer in the comments! If you get it you are super smart andddd Ill give u a cookie! 1
md65536 Posted March 20, 2015 Posted March 20, 2015 This was posted in Homework Help... is it an assignment? Why do you want just the answer? If it's for homework, please explain what you've got so far. How do you know it's 80 numbers long? I came up with an answer but it's fewer than 80 digits and the website says its wrong...
Commander Posted March 21, 2015 Posted March 21, 2015 (edited) I am trying to solve this Puzzle. Quite interesting. Perhaps I am going by the correct steps but it is quite time consuming. I hope the answer will be the lowest such a solution. Maybe only 25% progress has been made after so many hours of effort. >>>>>>>>>>>>>> PS : I am giving up as most of my processing software are saying that the number is beyond their power. May be a super computer is needed ! Edited March 21, 2015 by Commander
imatfaal Posted March 21, 2015 Posted March 21, 2015 This was posted in Homework Help... is it an assignment? Why do you want just the answer? If it's for homework, please explain what you've got so far. How do you know it's 80 numbers long? I came up with an answer but it's fewer than 80 digits and the website says its wrong... Re - how you could know length without knowing answer. Chinese remainder theorem can put a lower limit on answer. You know your answer is the sum of a group of multiplications the smallest of which will be of the magnitude of (Product of all the mod bases multipled together) / (the smallest mod base). Frankly - I cannot be bothered to work through the CRT to get the answer [latex] x= a_i mod (m_i) [/latex] as long as the m_i are co prime then [latex]x = \sum^n_{i=1}a_i \cdot b_i \cdot b'_imod(M)[/latex] with [latex]M=\prod^n_{i=1}m_i[/latex] [latex]b_i=\frac{M}{m_i}[/latex] [latex]b'_i=b_i^{-1}mod(m_i)[/latex] 1
md65536 Posted March 22, 2015 Posted March 22, 2015 (edited) PS : I am giving up as most of my processing software are saying that the number is beyond their power. May be a super computer is needed ! It should only take a few minutes of computation. You'll need to do "multiple precision" or "big int" calculations, eg. gmp c library. However you can also offload the calculations to wolframalpha! Re - how you could know length without knowing answer. Chinese remainder theorem can put a lower limit on answer. You know your answer is the sum of a group of multiplications the smallest of which will be of the magnitude of (Product of all the mod bases multipled together) / (the smallest mod base). I came across CRT, I think that's essentially the way I tried... x mod 2 = 1, x mod 3 = 2, x mod 5 = 2 I just realized that you can enter this into wolfram alpha directly and it will give you an integer solution equation. However, I converted it to a set of equations: x=2a+1, x=3b+2, x=5c+2 and wolframalpha will solve these too. These are "linear Diophantine equations", ie. linear equations with integer solutions. It can be solved I think using the extended Euler algorithm, as per CRT??? While wolframalpha will solve this, the input is too big and takes too much time for the free website. However it can be split up into several groups of equations, using the partial solution from one set as an input to the next. I ended up splitting it into 3 wolfram inputs. The answer I got is 11199...90177 (removed middle for now just in case it's actually a homework assignment). Though it says I'm wrong... Does the CRT apply here, since 2 and 600008 are not coprime? Is that okay, or perhaps 600008 is a typo? Edited March 22, 2015 by md65536
Commander Posted March 22, 2015 Posted March 22, 2015 (edited) It should only take a few minutes of computation. You'll need to do "multiple precision" or "big int" calculations, eg. gmp c library. However you can also offload the calculations to wolframalpha! I came across CRT, I think that's essentially the way I tried... x mod 2 = 1, x mod 3 = 2, x mod 5 = 2 I just realized that you can enter this into wolfram alpha directly and it will give you an integer solution equation. However, I converted it to a set of equations: x=2a+1, x=3b+2, x=5c+2 and wolframalpha will solve these too. These are "linear Diophantine equations", ie. linear equations with integer solutions. It can be solved I think using the extended Euler algorithm, as per CRT??? While wolframalpha will solve this, the input is too big and takes too much time for the free website. However it can be split up into several groups of equations, using the partial solution from one set as an input to the next. I ended up splitting it into 3 wolfram inputs. The answer I got is 11199...90177 (removed middle for now just in case it's actually a homework assignment). Though it says I'm wrong... Does the CRT apply here, since 2 and 600008 are not coprime? Is that okay, or perhaps 600008 is a typo? I used Excel and Wolfram too but after about 8/9 steps the numbers were getting too large. Imatfaal has given rigorous info on this modulo arithmetic. My take on this : I had processed up to x mod 397 = 343 and I can share details later [as they are in the other Comp] If say x= N at the current step N mod 2 , N mod 3 etc upto N mod 397 = 343 are satisfied then the next step is : Find N such that apart from satisfying sll mod equations so far it also satisfies N mod 691 = 652. N is added with multiples of LCM [2,3,5,13,..397] to get the nexr N Etc for all the 22 steps. Your solution may not be lowest because 2 and 600008 having common factor will reduce the LCM and thereby N. More later .... >>>>>>>>>>>>>>>> PS : Also at each step the number N could be reduced by optimization Edited March 22, 2015 by Commander
md65536 Posted March 22, 2015 Posted March 22, 2015 (edited) I used Excel and Wolfram too but after about 8/9 steps the numbers were getting too large. Imatfaal has given rigorous info on this modulo arithmetic. My take on this : I had processed up to x mod 397 = 343 and I can share details later [as they are in the other Comp] If say x= N at the current step N mod 2 , N mod 3 etc upto N mod 397 = 343 are satisfied then the next step is : Find N such that apart from satisfying sll mod equations so far it also satisfies N mod 691 = 652. N is added with multiples of LCM [2,3,5,13,..397] to get the nexr N Etc for all the 22 steps. Your solution may not be lowest because 2 and 600008 having common factor will reduce the LCM and thereby N. More later .... Wolfram has no trouble with these equations and 80-digit numbers. On second thought I don't think it matters that 2 and 600008 have a common factor. "x mod 600008 = 318753" already implies that "x mod 2 = 1". They're consistent and the latter is superfluous. I don't see how its inclusion could screw up the answer. Wolfram alpha with an input of x mod 2=1,x mod 3=2,x mod 5=2,x mod 13=8,x mod 29=4,x mod 31=18,x mod 191=130,x mod 397=343 gives an integer solution of x = 26585704470 n + 20740059257 The smallest solution is when n=0. Is 20740059257 the answer you got up to that point? All of those input equations are true if the output equation is true. So you can replace all those with the the output, and continue with additional inputs. I'm assuming that WolframAlpha is giving the correct answer. I don't see how it could give a solution that wasn't optimal (in which case its solution is only a partial solution). I'm also assuming that using its output to replace the many inputs doesn't change the result, simply because I don't see any room for a smaller solution to slip by. I might be mistaken, but tests with smaller inputs don't show any problem. Edited March 22, 2015 by md65536 1
Commander Posted March 22, 2015 Posted March 22, 2015 (edited) Wolfram has no trouble with these equations and 80-digit numbers. On second thought I don't think it matters that 2 and 600008 have a common factor. "x mod 600008 = 318753" already implies that "x mod 2 = 1". They're consistent and the latter is superfluous. I don't see how its inclusion could screw up the answer. Wolfram alpha with an input of x mod 2=1,x mod 3=2,x mod 5=2,x mod 13=8,x mod 29=4,x mod 31=18,x mod 191=130,x mod 397=343 gives an integer solution of x = 26585704470 n + 20740059257 The smallest solution is when n=0. Is 20740059257 the answer you got up to that point? All of those input equations are true if the output equation is true. So you can replace all those with the the output, and continue with additional inputs. I'm assuming that WolframAlpha is giving the correct answer. I don't see how it could give a solution that wasn't optimal (in which case its solution is only a partial solution). I'm also assuming that using its output to replace the many inputs doesn't change the result, simply because I don't see any room for a smaller solution to slip by. I might be mistaken, but tests with smaller inputs don't show any problem. The answer I got at that point is : cut and paste 20740059257 Let me again see whether any optimization possible. Mod Arith Puzzle.doc That 2 and 600008 factor comes later PS : I couldn't see any optimization possible upto this. >>>>>>>>>>>>....... Just about to complete processing 600008 and Wolfram Alpha says Standard time over and is not allowing my calculations from any computer on my IP Address Edited March 22, 2015 by Commander
Sensei Posted March 23, 2015 Posted March 23, 2015 (edited) The answer I got at that point is : cut and paste 20740059257 Website is asking for the LOWEST possible. After entering yours, we can see "The answer is incorrect! That is not the lowest possible value for X". I wrote C/C++ app (in less time than writing this reply), and it's crunching stuff. So far working for 104 minutes, and didn't find answer yet (and there is chance never will).. I attached it, so you can review, compile and run on your machine. ModPuzzle.zip Would be better to convert it to multi-threading. This would accelerate 8 times on Core i7. Edited March 23, 2015 by Sensei 1
md65536 Posted March 23, 2015 Posted March 23, 2015 (edited) Website is asking for the LOWEST possible. After entering yours, we can see "The answer is incorrect! That is not the lowest possible value for X". 20740059257 considers only the first few equations in the puzzle. The full answer I have is 73 digits long. I believe it's right (go wolfram alpha!) but if it's not, the answer will be smaller than that. I suspect that OP says the answer is 80 digits because the web page input allows up to 80 characters. However, brute force calculations and hardware-precision numbers aren't going to work. Note that considering ONLY the last equation, you know that x mod 800009 = 438462, so the smallest possible answer is 438462, and the next smallest is 800009+438462, so it is a waste to check every number in between. Even so, with optimizations like that I think you'll end up running a brute force algorithm for many magnitudes of time greater than the expected age of the universe. Edited March 23, 2015 by md65536 1
Commander Posted March 23, 2015 Posted March 23, 2015 (edited) http://meecles.net/puzzles/challenges.html ^ I stumbled upon this really well puzzel that deals with hard things! I know the answer is 80 numbers long. If you figure it out leave the answer in the comments! If you get it you are super smart andddd Ill give u a cookie! +1 to you for a hard puzzle put up. It should only take a few minutes of computation. You'll need to do "multiple precision" or "big int" calculations, eg. gmp c library. However you can also offload the calculations to wolframalpha! I came across CRT, I think that's essentially the way I tried... x mod 2 = 1, x mod 3 = 2, x mod 5 = 2 I just realized that you can enter this into wolfram alpha directly and it will give you an integer solution equation. However, I converted it to a set of equations: x=2a+1, x=3b+2, x=5c+2 and wolframalpha will solve these too. These are "linear Diophantine equations", ie. linear equations with integer solutions. It can be solved I think using the extended Euler algorithm, as per CRT??? While wolframalpha will solve this, the input is too big and takes too much time for the free website. However it can be split up into several groups of equations, using the partial solution from one set as an input to the next. I ended up splitting it into 3 wolfram inputs. The answer I got is 11199...90177 (removed middle for now just in case it's actually a homework assignment). Though it says I'm wrong... Does the CRT apply here, since 2 and 600008 are not coprime? Is that okay, or perhaps 600008 is a typo? +1 to you for the Good Effort [given in the other post] Website is asking for the LOWEST possible. After entering yours, we can see "The answer is incorrect! That is not the lowest possible value for X". I wrote C/C++ app (in less time than writing this reply), and it's crunching stuff. So far working for 104 minutes, and didn't find answer yet (and there is chance never will).. I attached it, so you can review, compile and run on your machine. ModPuzzle.zip Would be better to convert it to multi-threading. This would accelerate 8 times on Core i7. Hi Sensei, Thank you. Having been a Software Engineer/Researcher myself it should be possible for me to work on a suitable program. However my heydays are from IBM 360 onwards and Programming in ASM, C, C++ and upto Java in handson mode and thereafter on as and when required mode and therefore it will not be easy for me to indulge into it. +1 for your response 20740059257 considers only the first few equations in the puzzle. The full answer I have is 73 digits long. I believe it's right (go wolfram alpha!) but if it's not, the answer will be smaller than that. I suspect that OP says the answer is 80 digits because the web page input allows up to 80 characters. However, brute force calculations and hardware-precision numbers aren't going to work. Note that considering ONLY the last equation, you know that x mod 800009 = 438462, so the smallest possible answer is 438462, and the next smallest is 800009+438462, so it is a waste to check every number in between. Even so, with optimizations like that I think you'll end up running a brute force algorithm for many magnitudes of time greater than the expected age of the universe. md65536, One more +1 to you. As I said WolframAlpha has ditched me on the last steps. Have you got 73 Digit Solution - Has it given the Right Answer tag ? 438462 to 438462+800009 may be the range for the lowest possible solution. The number must perhaps end with 7 which makes search easier. Right now I have the number which will solve upto : Welcome to the new challenge set! Find the lowest possible value for X Good luck! (You may want to learn about modular arithmetic for this) x mod 2 = 1 x mod 3 = 2 x mod 5 = 2 x mod 13 = 8 x mod 29 = 4 x mod 31 = 18 x mod 191 = 130 x mod 397 = 343 x mod 691 = 652 x mod 1009 = 858 x mod 2039 = 689 x mod 4099 = 1184 x mod 7001 = 2027 x mod 10009 = 5119 x mod 19997 = 15165 x mod 30013 = 15340 x mod 70009 = 29303 x mod 160009 = 42873 x mod 200009 = 158045 x mod 430009 = 267339 Let us see whether this number can be lowered or whether it is valid and lowest upto this point. I will PM this number to those who give me a +1 Also, soon I will go through the next two steps and perhaps find the solution and verify and report whether it is right ! Then again I will PM it to those who give me +1 for the Effort ! All good responses will get +1 from me in return ! >>>>>>>>>>>>>>>> This itself can be taken as another Split Puzzle as an off shoot. What is the lowest number which will satisfy the first 20 steps as given above ? Re - how you could know length without knowing answer. Chinese remainder theorem can put a lower limit on answer. You know your answer is the sum of a group of multiplications the smallest of which will be of the magnitude of (Product of all the mod bases multipled together) / (the smallest mod base). Frankly - I cannot be bothered to work through the CRT to get the answer [latex] x= a_i mod (m_i) [/latex] as long as the m_i are co prime then [latex]x = \sum^n_{i=1}a_i \cdot b_i \cdot b'_imod(M)[/latex] with [latex]M=\prod^n_{i=1}m_i[/latex] [latex]b_i=\frac{M}{m_i}[/latex] [latex]b'_i=b_i^{-1}mod(m_i)[/latex] It is wise not to attack this time consuming puzzle ! +1 to you Edited March 23, 2015 by Commander
Lightmeow Posted March 23, 2015 Posted March 23, 2015 Has anyone actually gotten to the answer? And put the answer into the site and found the correct answer? I was looking at the source code for the puzzle, and got this: <html> <title>Puzzle</title> <center> <h1>Welcome to the new challenge set!</h1> <h2>Find the lowest possible value for X Good luck!</h2> <h3>(<i>You may want to learn about modular arithmetic for this</i>)</h3> <form action="http://meecles.net/cgi-bin/check/step2.cgi" method="POST"> <input type="text" name="s" maxlength="80"><input type="submit" Value="Check answer here"> </form> <h4> <p>x mod 2 = 1 </p> <p>x mod 3 = 2 </p> <p>x mod 5 = 2 </p> <p>x mod 13 = 8 </p> <p>x mod 29 = 4 </p> <p>x mod 31 = 18 </p> <p>x mod 191 = 130 </p> <p>x mod 397 = 343 </p> <p>x mod 691 = 652 </p> <p>x mod 1009 = 858 </p> <p>x mod 2039 = 689 </p> <p>x mod 4099 = 1184 </p> <p>x mod 7001 = 2027 </p> <p>x mod 10009 = 5119 </p> <p>x mod 19997 = 15165 </p> <p>x mod 30013 = 15340 </p> <p>x mod 70009 = 29303 </p> <p>x mod 160009 = 42873 </p> <p>x mod 200009 = 158045 </p> <p>x mod 430009 = 267339 </p> <p>x mod 600008 = 318753 </p> <p>x mod 800009 = 438462 </p> </h4> <h5><i><b>Hint: </b>You probably can't do this calculation by hand.</i></h5> </center> </html> The one link is the link to the you got the question wrong. Therefor I don't see any end to the puzzle.
Commander Posted March 23, 2015 Posted March 23, 2015 Wolfram Alpha is unable to solve : ( 1415861012097390882135382831783030209750137216528176436194427 + 6277155992786205212756401191971675112746773483185328925726970 * x) mod 600008 = 318753
md65536 Posted March 23, 2015 Posted March 23, 2015 The one link is the link to the you got the question wrong. Therefor I don't see any end to the puzzle. The link is a .cgi, which means "common gateway interface", which means that it is a program on the web server that dynamically generates the web page that you get. I assume the program checks the input and gives you a "correct" or "incorrect" message depending. Nowadays, most websites contain dynamic content so you can't assume that a webpage that you get is the only one that you'll ever get. However, I've come up with the same 73-digit answer twice, which the website says is wrong. Wolfram alpha solved it for me , but I might be making a mistake. There are always bugs possible, but I'd bet on a bug in the puzzle website before a bug in wolfram alpha's solution. Wolfram Alpha is unable to solve : ( 1415861012097390882135382831783030209750137216528176436194427 + 6277155992786205212756401191971675112746773483185328925726970 * x) mod 600008 = 318753 Can you split that into 2 equations of the form "x mod d = r"? Wolfram alpha will solve that. Note that x in your input means something different.
Commander Posted March 24, 2015 Posted March 24, 2015 However, I've come up with the same 73-digit answer twice, which the website says is wrong. Wolfram alpha solved it for me , but I might be making a mistake. There are always bugs possible, but I'd bet on a bug in the puzzle website before a bug in wolfram alpha's solution. Can you split that into 2 equations of the form "x mod d = r"? Wolfram alpha will solve that. Note that x in your input means something different. This x is just a variable and I need to find the lowest answer say x19 and solution to x which will be of the form x = n*60008 + x19 where n can be any positive number. x19 will be the Multiplier used to define the number X in the 20th Level say X 20 as X 20 = X 19 Let X be the Actual answer we are trying to work out step by step and on the 20th step we have : X = 1415861012097390882135382831783030209750137216528176436194427 satisfying : X mod [2=1, 3=2, 5=2,13=8 etc upto 430009= 267339 ie the first 20 steps] This X at 20th level say X 20 is made up of X 20 = X 19 + LCM(m1, m2, .. m19) * x19 which in this case is nothing but : 1415861012097390882135382831783030209750137216528176436194427 = 12420797378952639823185332549543391009135702825716011397 + 14597731658607622660819660034956652332269262929811536330 * 96991 At each level X will be reduced to the lowest value as and when possible but no reduction could be done upto X20 as only Prime numbers were mod factors upto m20 but m21 and m22 are not Primes and could lead to reduction on the 21st and 22nd Levels. Also it is derived iteratively as X 20 = (((X 1 + LCM(m1) * x1)) + LCM(m1,m2)*x2) + ……until x19 Multiplier x has been worked out upto 19th Level and shown in the table in the attached file. The actual values will be 1415861012097390882135382831783030209750137216528176436194427 = ((( 3 + 2*1)+ 6*2)+30*1 …… until x19 Mod Arith Puzzle.doc
Lightmeow Posted March 24, 2015 Posted March 24, 2015 The link is a .cgi, which means "common gateway interface", which means that it is a program on the web server that dynamically generates the web page that you get. I assume the program checks the input and gives you a "correct" or "incorrect" message depending. Nowadays, most websites contain dynamic content so you can't assume that a webpage that you get is the only one that you'll ever get. However, I've come up with the same 73-digit answer twice, which the website says is wrong. Wolfram alpha solved it for me , but I might be making a mistake. There are always bugs possible, but I'd bet on a bug in the puzzle website before a bug in wolfram alpha's solution. Can you split that into 2 equations of the form "x mod d = r"? Wolfram alpha will solve that. Note that x in your input means something different. I didn't know what that link meant. I assumed that it was basically another html page. That makes sense. Thanks
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now