-
Notifications
You must be signed in to change notification settings - Fork 1
/
243.py
54 lines (45 loc) · 1.08 KB
/
243.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#! /usr/bin/env python
from eulerutils import genprime
def totient_sieve(L):
''' return list of totient(i) for i from 0 to n-1.
>>> totient_sieve(12)
[0, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10]
'''
t = range(L+1)
for i in xrange(2,L+1):
if i == t[i]:
for j in xrange(i,L+1,i): t[j]-=t[j]/i
return t
def findR(a,b,start=2):
tots = totient_sieve(b**2)
d = start
while True:
if tots[d]* b < a*(d-1):
return d
if d%1000000==0:
print d
d+=1
#print findR(15499,94744,5000000)
#failed 10**8 out of mem
def findR2(a,b):
# phi = pi(n*(1-1/p))
gp = genprime()
r,l = b,a
d = 1
while True:
p = gp.next()
rn = r*(p-1)
ln = l*p
dn = d*p
# find the most 2*3*5*...value
if rn*dn<ln*(dn-1):
#test small values
for i in xrange(2,p):
if r*d*i < l*(d*i-1):
return d*i
r = rn
l = ln
d = dn
return 0
print findR2(4,10)
print findR2(15499,94744)