AB Skipping ‘Forensic Semiotic Sieve’

I think it makes more sense to call the Boolean-Peircean Sieve a “Forensic Semiotic Sieve” instead. Theorem-based optimization to optimize consideration of AB composites as prime candidates.

Theorem: No prime number greater than 3 can be expressed in the form AB = (6x + 5)(6y + 7), where x and y are integers.

Proof by Contradiction:

1. Assumption: Assume, for the sake of contradiction, that there exists a prime number p greater than 3 that can be expressed as AB = (6x + 5)(6y + 7) for some integers x and y.
2. Factorization: Since p is prime, it can only be factored into 1 and itself. Therefore, either:
   1. (6x + 5) = 1 and (6y + 7) = p
   1. (6x + 5) = p and (6y + 7) = 1
3. Analyze Cases:
   1. Case 1: (6x + 5) = 1. Solving for x, we get x = -2/3, which is not an integer. This contradicts our assumption that x is an integer.
   1. Case 2: (6y + 7) = 1. Solving for y, we get y = -1, which is an integer. However, substituting y = -1 into the AB equation gives us:
      AB = (6x + 5)(6(-1) + 7) = (6x + 5)(1) = 6x + 5
      This means p = 6x + 5, which places p in set A. But we assumed p was in the AB set. This is a contradiction.
4. Conclusion: Both cases lead to contradictions. Therefore, our initial assumption that a prime number p greater than 3 can be expressed in the form AB = (6x + 5)(6y + 7) must be false.

Overview of new features based on AB exclusion theorem

Here’s a breakdown of how it works:

1. Initial Composite Generation: The code generates composites in AA and BB sets using nested loops. These composites are added to the composites set.
2. AB Composite Marking: Later, in a separate loop, the code iterates through potential numbers in AB using nested loops. For each ab value:
   • If ab is less than or equal to n, it’s added to the composites set.
   • If ab is greater than n, the loop breaks because all potential AB composites within the range have already been marked.
3. Prime Identification: When identifying primes, the code checks if a number is present in the composites set. This is where the exclusion of AB comes into play:
   • Single Primes: The code directly checks if numbers in A and B (satisfying the 6k ± 1 form) are in the composites set. If not, they are considered prime.
   • Twin Primes: The code checks if both p (from A) and p + 2 (from B) are not in the composites set to determine if they form a twin prime pair.

Key Points:

• The code doesn’t avoid generating AB numbers, it just marks them as composites later.
• By marking all numbers in AB as composites, it ensures that during the prime identification process, any number that is not in the composites set must be prime according to the Hotchkiss Prime Theorem.

Effectively, the code implicitly excludes AB from the prime consideration by marking all numbers in AB as composites.

Updated Semiotic Sieve

import time

def find_largest_prime_within_time(n, duration_seconds):
  """
  Finds the largest prime within a specified duration using a modified Forensic Semiotic Sieve based on Hotchkiss Prime Theorem:

  """
  start_time = time.time()
  composites = set()
  largest_prime = 3  # Initialize with 3

  # Composite generation loop with time constraint
  while time.time() - start_time < duration_seconds:
    for x in range(0, n):
      for y in range(0, n):
        aa = (6 * x + 5) * (6 * y + 5)
        bb = (6 * x + 7) * (6 * y + 7)
        ab = (6 * x + 5) * (6 * y + 7)

        if aa <= n:
          composites.add(aa)
        if bb <= n:
          composites.add(bb)
        if ab <= n:
          composites.add(ab)

  # Find the largest prime within the remaining numbers
  for k in range(0, (n // 6) + 2):
    a = 6 * k + 5
    b = 6 * k + 7
    if a <= n and a not in composites and a > largest_prime:
      largest_prime = a
    if b <= n and b not in composites and b > largest_prime:
      largest_prime = b

  return largest_prime

# Get user input
n = int(input("Enter the upper limit (N): "))
duration = float(input("Enter the time limit in seconds: "))

# Calculate and display results
largest_prime = find_largest_prime_within_time(n, duration)
print(f"Largest prime found within {duration} seconds: {largest_prime}")

Explanation:

1. Time Tracking: The code uses time.time() to keep track of the start time and the elapsed time.
2. Composite Generation Loop:
   • The code iterates through the potential composites in AA, BB, and AB using nested loops.
   • It uses time.time() – start_time to check if the duration has been exceeded.
   • If the time limit is reached, the loop breaks.
3. Finding the Largest Prime:
   • After composite generation, the code iterates through potential primes using the 6k ± 1 form.
   • It checks if a number is not in the composites set and if it’s larger than the current largest_prime.
   • If both conditions are met, the largest_prime is updated.

Key Points:

• This code efficiently generates composites within a specified time limit.
• It then checks for the largest prime number within the remaining numbers that are not marked as composites.
• The time limit allows you to experiment with finding the largest prime within different durations.