Сколько числа ниже N coprimes к N?
Я тупой - я исправил это. Я не уверен, почему он отображается как сверху в отладчике представления, но это было позади другого UIView.
4 ответа
[Edit] Последняя мысль, которая (IMO) достаточно важна, чтобы я поставил ее в начале: если вы собираете кучу тотализаторов в один раз вы можете избежать лишней работы. Не беспокойтесь, начиная с больших чисел, чтобы найти их меньшие множители - вместо этого перебирайте меньшие множители и накапливайте результаты для больших чисел.
class Totient:
def __init__(self, n):
self.totients = [1 for i in range(n)]
for i in range(2, n):
if self.totients[i] == 1:
for j in range(i, n, i):
self.totients[j] *= i - 1
k = j / i
while k % i == 0:
self.totients[j] *= i
k /= i
def __call__(self, i):
return self.totients[i]
if __name__ == '__main__':
from itertools import imap
totient = Totient(10000)
print sum(imap(totient, range(10000)))
Это занимает всего 8 мсек на моем рабочем столе.
Страница Википедии на
class Totient:
def __init__(self, n):
self.totients = [1 for i in range(n)]
for i in range(2, n):
if self.totients[i] == 1:
for j in range(i, n, i):
self.totients[j] *= i - 1
k = j / i
while k % i == 0:
self.totients[j] *= i
k /= i
def __call__(self, i):
return self.totients[i]
if __name__ == '__main__':
from itertools import imap
totient = Totient(10000)
print sum(imap(totient, range(10000)))
1115322] Тотальная функция Эйлера дает хорошие математические результаты.
подсчитывает числа, взаимно простые и меньшие, чем каждый делитель
: это тривиальное * отображение для подсчета целых чисел от
до
, поэтому общая сумма составляет
. без деления
def totient4(n):
return reduce(mul, ((p-1) * p ** (exp-1) for p, exp in factorize(n)), 1)
Используя этот код для вычисления totients всех чисел от 1 до 9999 на моем рабочем столе, усредняя за 5 прогонов,
totient1занимает вечностьtotient2занимает 10 секундtotient3занимает 1,3 секундыtotient4занимает 1,3 секунды
Это функция Эйлера , phi.
Она обладает захватывающим свойством мультипликативности: если gcd (m, n) = 1, то phi (mn ) = фи (м) фи (п). А phi легко вычислить для степеней простых чисел, так как все, что ниже них, взаимно просто, за исключением кратных меньших степеней одного и того же простого числа.
Очевидно, что факторизация все еще не является тривиальной проблемой, но даже sqrt (n) пробное деление ( достаточно, чтобы найти все простые множители) лучше всего из n-1 применений алгоритма Евклида.
Если вы запомните, вы можете снизить средние затраты на вычисление большого количества из них.
Вот простая и понятная реализация формулы, приведенной на странице википедии, с использованием gmpy для легкой факторизации (я предвзято, но вам, вероятно, понадобится gmpy, если вы хотите поиграть с забавными целочисленными вещами в Python ...; -):
import gmpy
def prime_factors(x):
prime = gmpy.mpz(2)
x = gmpy.mpz(x)
factors = {}
while x >= prime:
newx, mult = x.remove(prime)
if mult:
factors[prime] = mult
x = newx
prime = prime.next_prime()
return factors
def euler_phi(x):
fac = prime_factors(x)
result = 1
for factor in fac:
result *= (factor-1) * (factor**(fac[factor]-1))
return result
Например, на моей скромной рабочей станции вычисление euler_phi (123456789) [для которого я получаю 82260072] занимает 937 микросекунд (с Python 2.5; 897 с 2.4), что кажется довольно сложным разумная производительность.
Вот несколько ссылок на другие обсуждения по этому поводу, включая некоторые другие языковые реализации:
http://www.velocityreviews.com/forums/t459467-computing-eulers-totient-function .html
http://www.google.com/codesearch?q=Euler%27s+totient&hl=en&btnG=Code