I wrote a program in Python 3 to check all tuples of the form
t are positive integers satisfying three conditions:
- The inequalities
s <= t^2and
t <= s^2hold, and the value
- The value of
- The inequalities both
s * [math.ceil( math.ceil( (t^2)/(s+1) ) * ((s+1)/t) )] > s(s+t)and
s > thold.
I'm interested in how often a tuple
(s,t) satisfies each of these conditions in turn; that is, how often a tuple meets condition (1), versus meeting both (1) and (2), versus meeting (1) - (3).
import math def IsPrime(n): # This returns True if a number is prime, and False if the number is composite. if n % 2 == 0 and n > 2: return False return all(n % i for i in range(3, int(math.sqrt(n)) + 1, 2)) def IsGQ(s,t): # This checks the divisibility condition. return (s*t*(s+1)*(t+1)) % (s+t) == 0 and s <= t**2 and t <= s**2 def IsNotTransitive(s,t): n = math.ceil((t**2)/(s+1)) k = math.ceil(n*((s+1)/t)) return (s*k) > t*(t+s) and s > t rng = 1000 # The upper limit that `t` will iterate up to quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) and (2) prime_quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) - (3) intransitive_quads = 0 # Counter for tuples (s,t) that satisfy conditions (1) - (4) # The next 5 lines place all prime numbers up to rng^2 into a list. # Ideally, this cuts down on how many times s+1 has to be checked to be a prime. primes =  for i in range(1, rng**2): if IsPrime(i): primes.append(i) for t in range(4, rng + 1): # Due to project details, I don't care about t<4. if t % 50 == 0: print("We have reached t = " + str(t) + ".") for s in range(2, t**2 + 1): # To satisfy condition (1), I don't want s to iterate above t^2 if IsGQ(s,t): # Condition (1) and (2)? quads += 1 if s+1 in primes: # Condition (3)? prime_quads += 1 if IsNotTransitive(s,t): # Condition (4)? intransitive_quads += 1 print(str(quads)) print(str(prime_quads)) print(str(intransitive_quads))
Currently, this runs to completion in over 10 minutes for
rng = 1000. Ideally, running this for
rng = 10000 in a reasonable amount of time is my current goal; computing these numbers for the value
rng = 100000 is my most optimistic goal.
Is there any way to reorder my iteration or change my method of checking for primeness that could be more efficient? It seems that the time for
s+1 in primes to complete grows quadratically with
rng. Since, after a certain point,
s+1 will be less than every value in
primes that hasn't been checked yet, would it be better to write my own "in" function along the lines of
def CheckPrime(s, primes): for n in primes: if s+1 == n: return True elif s+1 < n: return False
or would this still be slower than the current code?
Note: IsPrime comes from this Stack Overflow answer.