<!DOCTYPE html> <html lang="en"> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> <meta charset="utf-8"> <title>Problem 411 - Project Euler</title> <link rel="shortcut icon" href="favicon.ico"> <link rel="stylesheet" type="text/css" href="pe_template_style.css"> <script type="text/x-mathjax-config"> MathJax.Hub.Config({ jax: ["input/TeX", "output/HTML-CSS"], tex2jax: { inlineMath: [ ["$","$"], ["\\(","\\)"] ], displayMath: [ ["$$","$$"], ["\\[","\\]"] ], processEscapes: true }, "HTML-CSS": { availableFonts: ["TeX"] } }); </script> <script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS_HTML"> </script> <script type="text/javascript" src="md5.min.js"></script> <script type="text/javascript"> function check_ans(ans) { if (md5(ans) === "351762bf2220ca13966a93f6c84f") { alert("Correct!"); } else { alert("Sorry, that is incorrect!"); }; }; </script> </head> <body> <div id="container"> <div id="nav" class="noprint"> <ul> <li><a href="about.html" title="About">About</a></li> <li id="current"><a href="problems.html" title="Problems">Problems</a></li> <li><a href="news.html" title="News">News</a></li> <li><a href="http://forum.projecteuler.net" title="Project Euler Forum">Forum</a></li> </ul> <div style="text-align:right;padding:30px 10px 0 0;"> <a href="rss2_euler.xml"><img src="images/icon_rss.png" alt="RSS Feed" title="RSS Feed"></a> </div> </div> <div id="logo" class="noprint"> <img src="images/pe_banner.png" alt="Project Euler .net"> </div> <div id="content"> <div id="notification">This website is a semi-functional mirror of the original <a href="https://projecteuler.net/">Project Euler</a>. More information is available on <a href="https://github.com/wackyapples/ProjectEulerMirror/blob/gh-pages/README.md">GitHub</a>.</div> <div style="text-align:center;" class="print"><img src="images/pe_banner.png" alt="projecteuler.net" style="border:none;"></div> <h2>Uphill paths</h2> <h3>Problem 411</h3> <div style="font-size:80%;color:#999;">Published on 19 January 2013 at 10:00 pm [Server Time]</div> <div class="problem_content" role="problem"> <p> Let <var>n</var> be a positive integer. Suppose there are stations at the coordinates (<var>x</var>, <var>y</var>) = (2<sup><var>i</var></sup> mod <var>n</var>, 3<sup><var>i</var></sup> mod <var>n</var>) for 0 ≤ <var>i</var> ≤ 2<var>n</var>. We will consider stations with the same coordinates as the same station. </p> <p> We wish to form a path from (0, 0) to (<var>n</var>, <var>n</var>) such that the x and y coordinates never decrease.<br> Let S(<var>n</var>) be the maximum number of stations such a path can pass through. </p> <p> For example, if <var>n</var> = 22, there are 11 distinct stations, and a valid path can pass through at most 5 stations. Therefore, S(22) = 5. The case is illustrated below, with an example of an optimal path: </p> <p align="center"><img src="project/images/p411_longpath.png"></p> <p> It can also be verified that S(123) = 14 and S(10000) = 48. </p> <p> Find ∑ S(<var>k</var><sup>5</sup>) for 1 ≤ <var>k</var> ≤ 30. </p> </div> <br> <div style="text-align:center;" class="noprint"> Answer: <input type="text" name="answer" id="answer" style="border:1px solid #999;width:100px;"> <button onclick="check_ans(document.getElementById('answer').value);">Check</button> </div> <script type="text/javascript">document.getElementById('answer').focus();</script><div>Go to back to <a href="problems%3Bpage=9.html">Problems</a> </div> </div> <div id="footer" class="noprint">© Project Euler</div> <!--/Creative Commons License--><!-- <rdf:RDF xmlns="http://web.resource.org/cc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#" xmlns:rdfs="http://www.w3.org/2000/01/rdf-schema#"> <Work rdf:about=""> <license rdf:resource="http://creativecommons.org/licenses/by-nc-sa/2.0/uk/" /> <dc:type rdf:resource="http://purl.org/dc/dcmitype/Text" /> </Work> <License rdf:about="http://creativecommons.org/licenses/by-nc-sa/2.0/uk/"><permits rdf:resource="http://web.resource.org/cc/Reproduction"/><permits rdf:resource="http://web.resource.org/cc/Distribution"/><requires rdf:resource="http://web.resource.org/cc/Notice"/><requires rdf:resource="http://web.resource.org/cc/Attribution"/><prohibits rdf:resource="http://web.resource.org/cc/CommercialUse"/><permits rdf:resource="http://web.resource.org/cc/DerivativeWorks"/><requires rdf:resource="http://web.resource.org/cc/ShareAlike"/></License></rdf:RDF> --> </div> <div style="height:1px;"> </div> </body> </html>