StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The computation of phi(k) has to be done using the prime factorization of k, which is the only sensible way of doing it. If you need a refresher on that, <a href="http://en.wikipedia.org/wiki/Euler%27s_totient_function#Computing_Euler.27s_function" rel="nofollow noreferrer">wikipedia carries the formula</a>.</p> <p>If you now have to compute all prime divisors of every number between 1 and a large N, you'll die of old age before seeing any result, so I'd go the other way around, i.e. build all numbers below N, using their possible prime factors, i.e. all primes less than or equal to N.</p> <p>Your problem is therefore going to be similar to computing all divisors of a number, only you do not know what is the maximum number of times you may find a certain prime in the factorization beforehand. Tweaking an iterator originally written by Tim Peters on the python list (something <a href="http://numericalrecipes.wordpress.com/2009/05/13/divisors/" rel="nofollow noreferrer">I've blogged about</a>...) to include the totient function, a possible implementation in python that yields k, phi(k) pairs could be as follows:</p> <pre><code>def composites(factors, N) : """ Generates all number-totient pairs below N, unordered, from the prime factors. """ ps = sorted(set(factors)) omega = len(ps) def rec_gen(n = 0) : if n == omega : yield (1,1) else : pows = [(1,1)] val = ps[n] while val <= N : pows += [(val, val - pows[-1][0])] val *= ps[n] for q, phi_q in rec_gen(n + 1) : for p, phi_p in pows : if p * q > N : break else : yield p * q, phi_p * phi_q for p in rec_gen() : yield p </code></pre> <p>If you need help on computing all prime factors below N, I've also <a href="http://numericalrecipes.wordpress.com/2009/03/16/prime-numbers-2-the-sieve-of-erathostenes/" rel="nofollow noreferrer">blogged about it</a>... Keep in mind, though that computing all primes below 10<sup>12</sup> is in itself quite a remarkable feat...</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload