Answers to: WITMATH - Editorialhttps://discuss.codechef.com/questions/9723/witmath-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/WITMATH">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/WITMATH">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES</h1>
<p>Primality Testing</p>
<h1>PROBLEM</h1>
<p>Given some <b>N</b>, find the <b>i</b> for which <b>φ(i)/i</b> is the largest among all <b>2≤i≤N</b>.</p>
<p><b>φ(i)</b> is the <b>Euler Totient Function</b>.</p>
<h1>QUICK EXPLANATION</h1>
<p><b>φ(i)</b> is equal to the number of positive integers less than <b>i</b>, which are <b>co-prime</b> to <b>i</b>. The largest value of <b>φ(i)/i</b> is always achieved at prime values of <b>i</b> (primes of course are <b>co-prime</b> to all values less than them). Note that for a prime <b>i</b>, <b>φ(i) = i-1</b>.</p>
<p>Thus, for some <b>N</b>, we need to find the largest prime number we can find, which is less than <b>N</b>.</p>
<p><b>N</b> can be up to <b>10<sup>18</sup></b>. If we test primality via <b>Trial Division</b>, the minimum number of divisions we do for testing the primality of a single number is about <b>10<sup>9</sup></b>. Considering we have to consider several numbers and try to pluck the prime one (and do so for several cases) we are forced to find a faster way to test primality.</p>
<p><a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller Rabin</a> is such a test.</p>
<h1>EXPLANATION</h1>
<p>Although a <b>probabilistic</b> test, <b>Miller</b> <b>Rabin</b> has been successfully executed up till large enough numbers to show that performing the test while taking the first <b>9</b> prime numbers <b>{ 2, 3, 5, 7, 11, 13, 17, 19, 23 }</b> as the bases is sufficient to accurately test for primality of all numbers less than <b>10<sup>18</sup></b>.</p>
<p>If you end up falling in love with <b>Miller</b> <b>Rabin</b> (the algorithm of course), you will find <a href="http://oeis.org/A014233">this</a> link very useful to decide how many of the first few prime numbers to use as bases. It is not necessary to use small primes of course. Random bases can be chosen as well. But you might have to choose more than <b>9</b> of them to reduce the probability of a falty answer to a comfortably low level (testing with k random bases reduces the probability of a composite being reported as prime by a factor of 1/4<sup>k</sup>)</p>
<p>There are possibly two hurdles that you may face in implementing Miller Rabin.</p>
<p><b>1. Finding a<sup>r</sup> mod n, for a large r</b></p>
<p>This step must be performed using <b>repeated squaring</b>.</p>
<p><b>2. Multiplying two large integers mod n</b></p>
<p>The product of the two large integers would overflow the <b>64-bit</b> integer data type as well. The only way to get around this is to use some arbitrary precision math.</p>
<p>We can assume that the two integers, say <b>a</b> and <b>b</b>, are less than <b>n</b>. One way to perform the multiplication is as follows</p>
<pre> 1. a_low = a % 10<sup>9</sup>
2. a_high = a / 10<sup>9</sup>
3.
4. b_low = b % 10<sup>9</sup>
5. b_high = b / 10<sup>9</sup>
6.
7. result = (a_high * b_high) % n
8.
9. repeat 9 times
10. result = (result * 10) % n
11.
12. result = (result + a_low*b_high + b_low*a_high) % n
13.
14. repeat 9 times
15. result = (result * 10) % n
16.
17. result = (result + a_low*b_low) % n
</pre>
<p>The reason the above procedure would work is</p>
<ul>
<li>The product in line 7, 12 and 17 are betwee two 30-bit integers and will not overflow 64-bit integers.</li>
<li>The product in line 10 and 15 are between a 60-bit integer and 4-bit integer and will not overflow 64-bit integers. (although we must use unsigned)</li>
</ul>
<h1>SETTER'S SOLUTION</h1>
<p>Setter's solution will be updated soon.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/WITMATH.java">here</a>.</p>enMon, 27 May 2013 00:12:26 +0530Answer by swapniel99https://discuss.codechef.com/questions/9723/witmath-editorial/11432<p>Admin can u plz chk <a href="http://www.codechef.com/viewsolution/2181171">http://www.codechef.com/viewsolution/2181171</a> Even after using miller rabin and optimised modular exponation and product, I m getting TLE..</p>
<p>Before my code used to take 3-4 sec in my cases. Now only 31 ms. Still TLE :(</p>
<p>Please chk..</p>swapniel99Mon, 27 May 2013 00:12:26 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/11432Answer by gamabuntahttps://discuss.codechef.com/questions/9723/witmath-editorial/10240<p><a href="/users/15636/timepass123"><a href="/users/15636/timepass123">@timepass123</a></a></p>
<p>Let N = p<sub>1</sub><sup>r<sub>1</sub></sup>p<sub>2</sub><sup>r<sub>2</sub></sup>...p<sub>k</sub><sup>r<sub>k</sub></sup></p>
<p>φ(N)/N = ((p<sub>1</sub> - 1) / p<sub>1</sub>)((p<sub>2</sub> - 1) / p<sub>2</sub>)...((p<sub>k</sub> - 1) / p<sub>k</sub>)</p>
<p>For some N, let P be the largest prime less than or equal to N, and C be some composite number less than or equal to N.</p>
<p>But by definition of P (largest prime less than N), C must be a product of primes less than or equal to P.</p>
<p>C = q<sub>1</sub><sup>s<sub>1</sub></sup>q<sub>2</sub><sup>s<sub>2</sub></sup>...q<sub>t</sub><sup>s<sub>t</sub></sup></p>
<p>Where each q<sub>i</sub> ≤ P</p>
<p>φ(C)/C = ((q<sub>1</sub> - 1) / q<sub>1</sub>)((q<sub>2</sub> - 1) / q<sub>2</sub>)...((q<sub>k</sub> - 1) / q<sub>k</sub>)</p>
<p>We know that</p>
<p>((a - 1) / a) ≤ ((b - 1) / b) if a ≤ b</p>
<p>Thus</p>
<p>φ(C)/C ≤ ((P - 1) / P)<sup>t</sup> ... (because there were t terms)</p>
<p>where t ≥ 2</p>
<p>Lastly, we know that since ((P - 1) / P) < 1</p>
<p>((P - 1) / P) > ((P - 1) / P)<sup>t</sup> ... for any t ≥ 2</p>
<p>Thus</p>
<p>φ(C)/C < ((P - 1) / P)</p>
<p>or</p>
<p>φ(C)/C < φ(P)/P</p>
<p>Hence the answer will always be the largest prime less than (or equal to) N.</p>gamabuntaFri, 17 May 2013 13:37:37 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/10240Answer by timepass123https://discuss.codechef.com/questions/9723/witmath-editorial/10227<p>I was able to figure out that v should find out the largest prime number <= the given number. How ever I dint know to get rid of tle. Also I was not able to prove that fi(i)/i is max for only prime numbers. 4/5 < 97/99.</p>timepass123Fri, 17 May 2013 10:44:24 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/10227Answer by aayushagarwalhttps://discuss.codechef.com/questions/9723/witmath-editorial/10093<p>I submitted my code in python of WITMATH during the contest and got AC. When i was submitting the same using C++ it was giving TLE though i had taken all steps to prevent overflow. Please can anyone help. Here's my part of the code where repeated squarring is done: </p>
<pre>#include<cstdio>
#include<cstdlib>
using namespace std;
unsigned long long int mult (
unsigned long long int a,
unsigned long long int b,
unsigned long long int c
)
{
unsigned long long int x=0,y=a%c;
while(b>0)
{
if(b%2==1)
{
x=(x+y);
if(x>c) x=x%c;
}
y=(y*2);
if(y>c) y=y%c;
b/=2;
}
return x%c;
}
unsigned long long int modulo (
unsigned long long int a,
unsigned long long int b,
unsigned long long int c
)
{
unsigned long long int x = 1;
unsigned long long int y = a;
while (b>0)
{
if (b%2==1) x = mult(x,y,c);
y = mult(y,y,c);
b = b/2;
}
return x%c;
}
</pre>aayushagarwalWed, 15 May 2013 19:39:34 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/10093Answer by tijoforyouhttps://discuss.codechef.com/questions/9723/witmath-editorial/9792<p>I too used <a href="http://oeis.org/A014233">http://oeis.org/A014233</a> (mentioned in the editorial) during my approach. But that page says, "the primality of numbers < 2<sup>64</sup> can be determined by asserting strong pseudo-primality to all prime bases ≤ 37 (12<sup>th</sup> prime)".</p>
<p>10<sup>18</sup> is almost 2<sup>60</sup>. Is it because of this small a difference, that testing with 9 primes will suffice? Or, am I missing something??</p>
<p><a href="http://ww2.codechef.com/viewplaintext/2113853">Here</a> is my AC solution in Python (which tests with 12 primes of course).</p>tijoforyouTue, 14 May 2013 16:48:07 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/9792Answer by aayushagarwalhttps://discuss.codechef.com/questions/9723/witmath-editorial/9782<p><a href="/users/387/gamabunta">@gamabunta</a> : when we are multiplying two large numbers which can be upto 10^18 cant we instead
multiplying by breaking them into parts ... use (a<em>b)%MOD=(a%MOD</em>b%MOD)%MOD. here also the ans will remain within 64 bit in the intermediate results.</p>aayushagarwalTue, 14 May 2013 16:40:41 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/9782Answer by vineetpaliwalhttps://discuss.codechef.com/questions/9723/witmath-editorial/9738<p>where are you getting the links to editorials from ????
There are no links on May Challenge page and neither there are links on the Wiki page .
The Wiki page is so outdated that it does not have links to Editorials after January contest .
<a href="/users/1/admin"><a href="/users/1/admin">@admin</a></a> : please update wiki page .
<a href="/users/1/admin"><a href="/users/1/admin">@admin</a></a> : Please tell me how others get to know about editorials page and their links earlier than even when these links are posted on contest page .
<a href="/users/1169/betlista">@betlista</a> : Can you please tell where you got link to this editorial .</p>vineetpaliwalTue, 14 May 2013 15:43:41 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/9738Answer by betlistahttps://discuss.codechef.com/questions/9723/witmath-editorial/9735<p>This is one of such cases when Java beats C/C++ O:-)</p>
<p>My AC solution - <a href="http://ww2.codechef.com/viewsolution/2081192">http://ww2.codechef.com/viewsolution/2081192</a></p>betlistaTue, 14 May 2013 15:40:48 +0530https://discuss.codechef.com/questions/9723/witmath-editorial/9735