fork download
copy 
  1. # import numpy as np
  2.  
  3. # def heuristic(n, rng=None):
  4. #     if rng is None or isinstance(rng, int):
  5. #         rng = np.random.default_rng(rng)
  6. #     S = set()
  7. #     candidates = list(range(1, n+1))
  8. #     # Prioritize numbers with fewer representations as part of an AP
  9. #     # Here, we simply use the count of APs they can form, but more sophisticated methods exist
  10. #     candidates.sort(key=lambda x: sum(1 for y in S if 2*y-x in S or 2*x-y in S or y+x in [2*z for z in S]))
  11. #     for x in candidates:
  12. #         if not any((2*x - y in S and y in S) or (2*y - x in S and y in S) for y in S):
  13. #             S.add(x)
  14. #     return S
  15. import numpy as np
  16.  
  17. def count_3ap_memberships(N: int) -> np.ndarray:
  18.     """
  19.     counts[x] = number of 3-APs (a,b,c) with a<b<c in [1..N] where x is one of {a,b,c}.
  20.     Time: O(N^2) via iterating (middle b, step d).
  21.     """
  22.     counts = np.zeros(N + 1, dtype=np.int64)  # 1-indexed
  23.     for b in range(1, N + 1):
  24.         max_d = min(b - 1, N - b)
  25.         for d in range(1, max_d + 1):
  26.             a = b - d
  27.             c = b + d
  28.             counts[a] += 1
  29.             counts[b] += 1
  30.             counts[c] += 1
  31.     return counts
  32.  
  33. def would_create_3ap(S: set[int], x: int) -> bool:
  34.     """
  35.     Check whether adding x to S would create any 3-term AP entirely in S ∪ {x}.
  36.     Equivalent: exists y in S such that (2*y - x) in S OR (2*x - y) in S.
  37.     """
  38.     for y in S:
  39.         if (2 * y - x) in S:
  40.             return True  # (x, y, 2y-x) with y middle
  41.         if (2 * x - y) in S:
  42.             return True  # (y, x, 2x-y) with x middle
  43.     return False
  44.  
  45. def salem_spencer_greedy(N: int, rng=None, tie_break="random", verbose=False):
  46.     """
  47.     Greedy Salem-Spencer construction on [1..N]:
  48.     - Precompute global 3-AP membership counts for each integer as sorting key.
  49.     - Iterate candidates in ascending key order; add x if it does not create a 3-AP.
  50.  
  51.     tie_break:
  52.       - "random": shuffle within same-key bucket using rng
  53.       - "asc": smaller x first within same-key bucket
  54.       - "desc": larger x first within same-key bucket
  55.     """
  56.     if rng is None or isinstance(rng, int):
  57.         rng = np.random.default_rng(rng)
  58.  
  59.     counts = count_3ap_memberships(N)
  60.     candidates = list(range(1, N + 1))
  61.  
  62.     # Tie-breaking strategy
  63.     if tie_break == "random":
  64.         rng.shuffle(candidates)
  65.         candidates.sort(key=lambda x: counts[x])  # stable sort keeps shuffled order within ties
  66.     elif tie_break == "asc":
  67.         candidates.sort(key=lambda x: (counts[x], x))
  68.     elif tie_break == "desc":
  69.         candidates.sort(key=lambda x: (counts[x], -x))
  70.     else:
  71.         raise ValueError("tie_break must be one of: 'random', 'asc', 'desc'")
  72.  
  73.     if verbose:
  74.         print("candidate -> key(count_3ap_memberships)")
  75.         for x in candidates:
  76.             print(f"{x:>4} -> {counts[x]}")
  77.  
  78.     S: set[int] = set()
  79.     for x in candidates:
  80.         if not would_create_3ap(S, x):
  81.             S.add(x)
  82.  
  83.     return S, counts, candidates
  84.  
  85. # -----------------------
  86. # Example usage
  87. # -----------------------
  88. if __name__ == "__main__":
  89.     N = 5
  90.     S, counts, order = salem_spencer_greedy(N, rng=0, tie_break="asc", verbose=False)
  91.     print("N =", N)
  92.     print("|S| =", len(S))
  93.     print("S (sorted) =", sorted(S))
  94.     # show first 15 candidates with their keys
  95.     print("First 15 candidates (x, key):", [(x, int(counts[x])) for x in order])
  96.  
  97.  
  98.  
  99.  
  100. # X = heuristic(1094)
  101.  
  102. # print(X, len(X))
Success #stdin #stdout 0.81s 41344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N = 5
|S| = 4
S (sorted) = [1, 2, 4, 5]
First 15 candidates (x, key): [(1, 2), (2, 2), (4, 2), (5, 2), (3, 4)]
https://ideone.com/LrkJxW
language:
Python 3 (python  3.12)
created:
6 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!