feat(sieve): add p49 and test - #53

• Implement Project Euler #49 solver to find arithmetic sequences of prime permutations.
• Generate n-digit primes via a segmented sieve for performance on larger digit ranges.
• Add pytest coverage for 4-digit and 5-digit expected sequences.

graph TD
  T["tests/euler/p49_test.py"] --> P["prime_permutations(n, perms)"] --> S["sieve_n_digit_primes(n)"] --> B["base primes sieve"] --> G["group by sorted digits"] --> F["find arithmetic sequences"]

Loading

The following are alternative approaches to this PR:

1. Use a simple sieve up to 10^n (non-segmented)

• ➕ Much simpler implementation and easier to reason about
• ➕ Lower risk of off-by-one and segment marking issues for small n (e.g., 4–6 digits)
• ➖ Higher memory cost as n grows
• ➖ Less scalable if reused for larger digit counts

2. Sequence search via sorted list + set (dedupe-first)

• ➕ Avoids O(m^2) nested start/next loops by iterating pairs systematically (e.g., combinations)
• ➕ Makes it straightforward to deduplicate sequences (store result strings in a set)
• ➖ Slightly more code/structure (sorting per bucket, more explicit iteration)
• ➖ May be marginally slower for very small buckets if not implemented carefully

Recommendation: The segmented sieve approach is reasonable if this module is intended to scale beyond Euler #49. For maintainability and to reduce correctness risk, consider (a) removing or using the currently unused is_prime() helper, (b) avoiding name shadowing of is_prime inside sieve_n_digit_primes(), and (c) deduplicating results in prime_permutations() (e.g., accumulate into a set) to prevent repeated sequences from different (start, next_num) pairs.

Enhancement (1) +99 / -0

p49.pyAdd segmented-sieve prime generator and prime permutation sequence solver +99/-0

Add segmented-sieve prime generator and prime permutation sequence solver

• Introduces sieve_n_digit_primes() to generate n-digit primes using a segmented sieve built from base primes up to sqrt(high). Adds prime_permutations() to group primes by digit signature and find arithmetic sequences of a requested length, returning concatenated sequence strings.

Algorithms/numerical_methods/euler/p49.py

Tests (1) +7 / -0

p49_test.pyAdd pytest coverage for Euler #49 known outputs +7/-0

Add pytest coverage for Euler #49 known outputs

• Adds tests asserting the expected 4-digit (length 3) and 5-digit (length 4) prime-permutation arithmetic sequences returned by prime_permutations().

tests/euler/p49_test.py

Description

prime_permutations() is annotated to return str but actually returns a list of concatenated strings,
which breaks the function’s API contract for type checkers and callers relying on hints.

Code

Algorithms/numerical_methods/euler/p49.py[R65-98]

+def prime_permutations(n: int, perms: int) -> str:
+    """
+    n: number of digits in the prime permutations
+    end in odd
+    perms: number of permutations to consider
+    _ _ _ 1,3,5,7,9
+    """
+    all_primes = sieve_n_digit_primes(n)
+    table = defaultdict(list)
+    for prime in all_primes:
+        key = "".join(sorted(str(prime)))
+        table[key].append(prime)
+
+    res = []
+    for key, nums in table.items():
+        if len(nums) < perms:
+            continue
+        nums_set = set(nums)
+        for start in nums_set:
+            for next_num in nums_set:
+                if next_num <= start:
+                    continue
+                diff = next_num-start
+                seq = [start]
+                curr = start
+                while curr in nums_set and len(seq) < perms:
+                    curr += diff
+                    if curr in nums_set:
+                        seq.append(curr)
+                    else:
+                        break
+                if len(seq) == perms:
+                    res.append("".join([str(v) for v in seq]))
+    return res

Relevance

⭐⭐ Medium

No repo history on fixing return type hints; team often rejects non-essential refactors (PR16).

PR-#16

ⓘ Recommendations generated based on similar findings in past PRs

Evidence

The function’s signature declares -> str but it builds res = [] and returns that list; the tests
call sorted() on the result, which only makes sense if it’s a list/iterable of strings.

Algorithms/numerical_methods/euler/p49.py[65-98]
tests/euler/p49_test.py[1-7]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

### Issue description
`prime_permutations()` is declared as returning `str` but returns `res` which is a list of strings. This makes the public API misleading and can break static analysis / IDE usage.

### Issue Context
Tests already treat the return value as an iterable of strings (`sorted(prime_permutations(...))`).

### Fix Focus Areas
- Algorithms/numerical_methods/euler/p49.py[65-98]

### Proposed fix
- Change the signature to return `list[str]` (or `Sequence[str]`), e.g.:
 - `def prime_permutations(n: int, perms: int) -> list[str]:`
- Optionally update the docstring to reflect that a list is returned.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Description

sieve_n_digit_primes() returns an empty list for n < 1, unlike other Euler utilities in this repo
that raise ValueError for invalid n, which can mask upstream bugs by silently producing no results.

Code

Algorithms/numerical_methods/euler/p49.py[R20-23]

+def sieve_n_digit_primes(n: int):
+    if n < 1:
+        return []
+    

Relevance

⭐⭐ Medium

Euler modules (p2/p48) raise ValueError for n<1, but no evidence team enforces this everywhere.

PR-#51
PR-#52

ⓘ Recommendations generated based on similar findings in past PRs

Evidence

p49’s sieve currently returns [] for invalid n, while other Euler solutions raise ValueError
for n < 1, demonstrating inconsistent input validation semantics within the same module family.

Algorithms/numerical_methods/euler/p49.py[20-23]
Algorithms/numerical_methods/euler/p48.py[2-5]
Algorithms/numerical_methods/euler/p2.py[1-6]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

### Issue description
`sieve_n_digit_primes()` currently returns `[]` when `n < 1`, which silently accepts invalid input and can hide errors.

### Issue Context
Other Euler helpers in this repo raise `ValueError` on `n < 1`, so callers likely expect consistent validation behavior.

### Fix Focus Areas
- Algorithms/numerical_methods/euler/p49.py[20-23]

### Proposed fix
- Replace the early return with a `ValueError`, e.g.:
 ```py
 if n < 1:
     raise ValueError("n must be at least 1")
 ```
- Keep the existing `n == 1` handling (setting `low = 2`).

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Description

tests/euler/p49_test.py is missing a trailing newline, which creates diff noise and can fail
formatting checks in stricter environments.

Code

tests/euler/p49_test.py[R1-7]

+from Algorithms.numerical_methods.euler.p49 import prime_permutations
+
+def test_sol():
+    assert sorted(prime_permutations(n=4, perms=3)) == ['148748178147', '296962999629']
+
+def test_higher_n():
+    assert sorted(prime_permutations(n=5,perms=4)) == ['83987889379388798837']

Relevance

⭐⭐⭐ High

Missing trailing newline fix was definitely accepted previously to remove diff noise (PR49).

PR-#49

ⓘ Recommendations generated based on similar findings in past PRs

Evidence

The added test file content ends at line 7, and the PR diff indicates it lacks a final newline; this
matches a previously accepted formatting issue in the repo history.

tests/euler/p49_test.py[1-7]
PR-#49

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

### Issue description
The new test file ends without a trailing newline (`\ No newline at end of file`).

### Issue Context
This repo has previously accepted fixes for the same formatting issue.

### Fix Focus Areas
- tests/euler/p49_test.py[1-7]

### Proposed fix
- Add a newline character at the end of `tests/euler/p49_test.py`.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Description

The module-level is_prime() uses float sqrt plus a step-1 divisor loop, which is slower than needed
and less robust than using integer sqrt with odd divisors; it’s also not used by this module’s main
logic.

Code

Algorithms/numerical_methods/euler/p49.py[R5-18]

+def is_prime(n: int):
+    if n < 1:
+        raise ValueError("n must be at least 1")
+    elif n == 1:
+        return False
+    elif n == 2:
+        return True
+    elif n % 2 == 0:
+        return False
+    else:
+        for i in range(3, int(math.sqrt(n))+1):
+            if n % i == 0:
+                return False
+        return True

Relevance

⭐⭐ Medium

No similar accepted history; perf refactors like iterative-vs-recursive were rejected in PR49.

PR-#49

ⓘ Recommendations generated based on similar findings in past PRs

Evidence

The implementation explicitly uses math.sqrt(n) and loops over every integer divisor; the module’s
actual solution path calls sieve_n_digit_primes() from prime_permutations(), not is_prime().

Algorithms/numerical_methods/euler/p49.py[5-18]
Algorithms/numerical_methods/euler/p49.py[72-77]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

### Issue description
`is_prime()` computes `int(math.sqrt(n))` and tests every divisor from 3 upward with step 1. This is slower than necessary and relies on floating-point sqrt.

### Issue Context
Within this module, `prime_permutations()` uses `sieve_n_digit_primes()` for primality generation, so this helper is currently redundant unless intended for external callers.

### Fix Focus Areas
- Algorithms/numerical_methods/euler/p49.py[5-18]

### Proposed fix
- Prefer integer sqrt and only test odd divisors:
 ```py
 limit = math.isqrt(n)
 for i in range(3, limit + 1, 2):
     ...
 ```
- Consider removing `is_prime()` if it’s not part of the intended public API for this module.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools