fork download 
  1. # Recreate the provided heuristic and run it for a demonstration.
  2. import numpy as np
  3.  
  4. def heuristic(n, rng=None):
  5.     """
  6.     Builds a large Salem–Spencer set using a residue-based partitioning and greedy approach.
  7.  
  8.     Args:
  9.         n: A positive integer specifying the universe {1..n}.
  10.         rng: A random seed or a numpy Generator.
  11.  
  12.     Returns:
  13.         A Python set of unique integers in [1..n] that is 3-AP-free.
  14.     """
  15.     if rng is None:
  16.         rng = np.random.default_rng()
  17.     elif isinstance(rng, (int, float)):
  18.         rng = np.random.default_rng(rng)
  19.  
  20.     S = set()
  21.  
  22.     # Choose modulus as a power of 2; smallest k with 2^k > n/2 (as described).
  23.     k = 0
  24.     while (1 << (k + 1)) <= n // 2:
  25.         k += 1
  26.     modulus = 1 << k if k > 0 else 1  # guard for small n
  27.  
  28.     # Group numbers by residue mod modulus
  29.     candidate_groups = {residue: [] for residue in range(modulus)}
  30.     for x in range(1, n + 1):
  31.         residue = x % modulus
  32.         candidate_groups[residue].append(x)
  33.  
  34.     # Shuffle within each residue group with a deterministic RNG derived from rng
  35.     local_rng_shuffle = np.random.default_rng(int(rng.integers(2**32 - 1)))
  36.     for residue in candidate_groups:
  37.         local_rng_shuffle.shuffle(candidate_groups[residue])
  38.  
  39.     # Collect numbers whose quotient (x // modulus) is even
  40.     potential_additions = []
  41.     for residue in range(modulus):
  42.         for num in candidate_groups[residue]:
  43.             quotient = num // modulus
  44.             if quotient % 2 == 0:
  45.                 potential_additions.append(num)
  46.  
  47.     # Add even-quotient numbers greedily while preserving 3-AP freeness
  48.     for x in potential_additions:
  49.         is_valid = True
  50.         for s_val in S:
  51.             if (2 * x - s_val) in S or (2 * s_val - x) in S:
  52.                 is_valid = False
  53.                 break
  54.         if is_valid:
  55.             S.add(x)
  56.  
  57.     # Then greedily try to add remaining numbers (descending)
  58.     remaining_candidates = sorted([x for x in range(1, n + 1) if x not in S], reverse=True)
  59.     for x in remaining_candidates:
  60.         is_valid = True
  61.         for s_val in S:
  62.             if (2 * x - s_val) in S or (2 * s_val - x) in S:
  63.                 is_valid = False
  64.                 break
  65.         if is_valid:
  66.             S.add(x)
  67.  
  68.     return S
  69.  
  70. def is_three_ap_free(S):
  71.     """Return True if S contains no 3-term arithmetic progression a<b<c with a+c=2b."""
  72.     Sset = set(S)
  73.     arr = sorted(Sset)
  74.     n = len(arr)
  75.     # For each middle element b, check if there exists a and c = 2b - a in S with a<b<c
  76.     for j in range(n):
  77.         b = arr[j]
  78.         for i in range(j):
  79.             a = arr[i]
  80.             c = 2*b - a
  81.             if c > b and c in Sset:
  82.                 return False, (a, b, c)
  83.     return True, None
  84.  
  85. # Run an example with n=100 and fixed seed for reproducibility
  86. for seed in range(100):
  87. 	n = 82
  88. 	S = heuristic(n, rng=seed)
  89. 	is_free, witness = is_three_ap_free(S)
  90.  
  91. 	if (is_free):
  92. 		print(f"seed: {seed}, len: {len(S)}, {sorted(S)}")
  93. # seed = 42
  94.  
  95. len_S = len(S)
  96. sorted_S = sorted(S)
  97.  
  98. len_S, is_free, witness, sorted_S[:10], sorted_S[-10:]
  99.  
Success #stdin #stdout 0.84s 41652KB
comments (?)
stdin 
Standard input is empty
stdout 
seed: 0, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 1, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 2, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 3, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 4, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 5, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 6, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 7, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 8, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 9, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 10, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 11, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 12, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 13, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 14, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 15, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 16, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 17, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 18, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 19, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 20, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 21, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 22, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 23, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 24, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 25, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 26, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 27, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 28, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 29, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 30, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 31, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 32, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 33, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 34, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 35, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 36, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 37, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 38, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 39, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 40, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 41, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 42, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 43, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 44, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 45, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 46, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 47, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 48, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 49, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 50, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 51, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 52, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 53, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 54, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 55, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 56, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 57, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 58, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 59, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 60, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 61, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 62, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 63, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 64, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 65, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 66, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 67, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 68, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 69, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 70, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 71, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 72, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 73, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 74, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 75, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 76, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 77, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 78, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 79, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 80, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 81, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 82, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 83, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 84, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 85, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 86, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 87, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 88, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 89, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 90, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 91, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 92, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 93, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 94, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 95, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 96, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 97, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 98, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
seed: 99, len: 20, [1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 50, 64, 65, 67, 68, 73, 74, 76, 77]
https://ideone.com/r7KkKj
language:
Python 3 (python  3.12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!